unordered_set sortieren?

Nathan

happystudent schrieb:

Caligulaminus schrieb:

Warum nimmst Du dann nicht einfach einen std::vector?

Weil ich gleichzeitig Elemente in O(1) finden können will.

Warte mal, du willst Elemente konstant finden. Und unordered_set sortieren.
Wenn du es sortiert hast, kannst du es aber nicht mehr in konstanter Zeit finden.
In dubio pro std::vector, sag ich nur.

Mechanics

Ok, wenn es wirklich viele Dubletten gibt, dann wär ein set wirklich nicht schneller.

happystudent

Nathan schrieb:

Warte mal, du willst Elemente konstant finden. Und unordered_set sortieren.
Wenn du es sortiert hast, kannst du es aber nicht mehr in konstanter Zeit finden.

Echt? Wieso dass denn? Das wäre ja blöd

Nathan schrieb:

In dubio pro std::vector, sag ich nur.

Naja, vector ist hier glaub ich einfach nicht geeignet. Ich hab folgendes Szenario: Eine sehr lange Liste von Typen die Sortiert sein muss (nennen wir sie LISTE_1). Und eine zweite, ebenfalls sehr lange Liste vom gleichen Typ die nicht sortiert ist und auch nicht sortiert sein muss (das wäre dann LISTE_2).

Ich will jetzt Elemente von LISTE_2 nach LISTE_1 kopieren, aber nur wenn LISTE_1 diese noch nicht enthält. Danach sollen aus LISTE_1 alle Elemente entfernt werden, die nicht in LISTE_2 sind, außer eine gewisse Anzahl an fixen Elementen die nicht gelöscht werden. Nach allen Einfügevorgängen soll LISTE_1 wieder in einem sortieren Zustand vorliegen.

Mit nem vector hätte ich da etwa O(n^2), was ich unbedingt vermeiden will.

Hier ein kleines Beispiel, die fixen Werte sind mit x bezeichnet:

// Ausgangslage
LISTE_1    LISTE_2
b          a
c          d
d
x

// Alle Elemente aus LISTE_2 zu LISTE_1 hinzufügen, die noch nicht in LISTE_1 sind:
LISTE_1    LISTE_2          
b          a
c          d
d
x
a

// Jetzt alle Elemente aus LISTE_1 entfernen, die nicht in LISTE_2 sind, außer fixe Elemente x:
LISTE_1    LISTE_2
d          a
x          d
a

// Abschließend soll LISTE_1 wieder in einen sortieren Zustand gebracht werden:
LISTE_1    LISTE_2
a          a
d          d
x

Das will ich letztendlich erreichen halt möglichst effizient.

cooky451

Kannst du nicht einfach alle x in Liste 2 einfügen?

Also:

vector<int> liste_1, liste_2;
liste_1.erase(remove_if(liste_1.begin(), liste_2.end(), ist_fixes_element));
unordered_set<int> tmp(liste_2.begin(), liste_2.end());
liste_1.insert(liste_1.end(), tmp.begin(), tmp.end());
sort(liste_1.begin(), liste_1.end());

Ethon

happystudent schrieb:

Nathan schrieb:

Warte mal, du willst Elemente konstant finden. Und unordered_set sortieren.
Wenn du es sortiert hast, kannst du es aber nicht mehr in konstanter Zeit finden.

Echt? Wieso dass denn? Das wäre ja blöd

Schau dir mal an wie Hashtables funktionieren.
http://de.wikipedia.org/wiki/Hashtabelle

Bau dir halt für den sortierten Zugriff einen Zeigervektor und sortier den. Dann kannst du über die unordered_map<foo> Elemente in konstanter¹ Zeit finden und sie über den vector<foo*> sortiert betrachten. Oder halt umgekehrt, je nachdem, was besser passt.

¹D.h. average-case-konstanter Zeit. Mit dem konstant komplexen Zugriff in Hashtables ist das so ne Sache; wenn zum Beispiel jemand dir nicht wohlgesonnenes die Schlüssel manipulieren kann, musst du mit linearer Komplexität rechnen.

otze

wie lang sind denn die Listen von denen wir hier reden?

happystudent

cooky451 schrieb:

Kannst du nicht einfach alle x in Liste 2 einfügen?

Könnte ich schon, aber das wäre sehr ungünstig weil Liste 2 in jedem Durchgang neu erstellt wird. Das heißt ich müsste die resultierende Liste auch in jedem Durchgang sortieren, was viel zu aufwändig wäre. Daher mach ich überhaupt erst das hin und her kopieren, dass die resultierende Liste 1 wirklich nur dann sortiert werden muss wenn wirklich nötig.

humm schrieb:

Also:

vector<int> liste_1, liste_2;
liste_1.erase(remove_if(liste_1.begin(), liste_2.end(), ist_fixes_element));
unordered_set<int> tmp(liste_2.begin(), liste_2.end());
liste_1.insert(liste_1.end(), tmp.begin(), tmp.end());
sort(liste_1.begin(), liste_1.end());

Ja, damit kopiert man dann halt wieder etliche Werte hin und her...

otze schrieb:

wie lang sind denn die Listen von denen wir hier reden?

Es sind string Listen wobei Liste 1 ca 7000 fixe Einträge hat (die also nie gelöscht werden). Dazu kommen noch die dynamischen Einträge aus Liste 2, deren Anzahl letztenlich der Benutzer bestimmt. Typische Größenordnung ist hier von ca. 1000 - 5000 Einträge.

Die strings in den Listen selbst sind etwa zwischen 1 und 20 chars lang, im Schnitt etwa 5-6 chars.

Ethon

Nimm std::set bei den paar strings.

happystudent schrieb:

Es sind string Listen.

Gut, dann halt

#include <iterator> // damit du dich nicht über Compiler-Fehler wunderst
vector<string> liste_1, liste_2;
liste_1.erase(remove_if(liste_1.begin(), liste_2.end(), ist_fixes_element));
unordered_set<string> tmp(make_move_iterator(begin(liste_2)), make_move_iterator(end(liste_2.end)));
liste_1.insert(liste_1.end(), make_move_iterator(begin(tmp)), make_move_iterator(end(tmp)));
sort(liste_1.begin(), liste_1.end());

Ich wette mit dir, dass das schneller ist, als alle deine optimierten Selbstversuche.

happystudent

humm schrieb:

Gut, dann halt

#include <iterator> // damit du dich nicht über Compiler-Fehler wunderst
vector<string> liste_1, liste_2;
liste_1.erase(remove_if(liste_1.begin(), liste_2.end(), ist_fixes_element));
unordered_set<string> tmp(make_move_iterator(begin(liste_2)), make_move_iterator(end(liste_2.end)));
liste_1.insert(liste_1.end(), make_move_iterator(begin(tmp)), make_move_iterator(end(tmp)));
sort(liste_1.begin(), liste_1.end());

Ich wette mit dir, dass das schneller ist, als alle deine optimierten Selbstversuche.

Nee, schon allein deswegen nicht weil hier in jedem Schritt alle dynamischen Elemente aus Liste 1 entfernt werden (ich geh mal davon aus du meinst ist_nicht_fixes_element als Filter Funktion, oder?). Daher müsste mit dieser Lösung in jedem Schritt sortiert werden, auch wenn es gar keinen neuen Elemente für Liste 1 gibt.

Also eigentlich will ich Source-Code parsen und Benutzer-Definierte keywords wie Klassennamen etc. zu einer Liste hinzufügen. Das heißt ja dass im Großteil der Fälle in denen der Benutzer tippt auch kein keyword verändert wird und daher die Liste nicht neu aufgestellt werden muss.

Deswegen lauf ich über den Code und adde alle solche Keywords wenn sie noch nicht in der Liste sind. Wenn bereits alle keywords in der Liste sind muss auch nichts verändert und damit nichts sortiert werden.

Problem ist halt wenn der Benutzer was löscht, zum Beispiel den letzten Buchstaben von "MyClasss" (nachdem er sich verschrieben hat zum Beispiel). Dann muss der Algorithmus ja checken dass das keyword "MyClasss" nicht mehr exisitiert und es löschen. Daher hab ich eine zweite Liste, in der alle aktuell tatsächlich gefundenen Einträge gespeichert werden. Diese zweite Liste wird dann mit der ersten Liste abgeglichen.

Ist das die normale Vorgehensweise für dieses Problem oder gibt es bessere Lösungen dafür?

Soweit ich das sehe parst du den gesamten Code, schreibst alle Keywords auf und benutzt dann einen extrem komplizierten Algorithmus um die erste Liste so wie die zweite Liste zu machen. Warum nicht gleich die aktuelle Liste nehmen bzw. einmal swap aufufen?

happystudent schrieb:

Ist das die normale Vorgehensweise für dieses Problem oder gibt es bessere Lösungen dafür?

libclang
Das willst du nicht alles selber schreiben.

happystudent

nwp3 schrieb:

Warum nicht gleich die aktuelle Liste nehmen bzw. einmal swap aufufen?

Weil ich dann keine keywords, die sich nicht mehr im Code befinden, löschen kann!

Klar kann ich die aktuelle Liste nehmen und einfach gefundene keywords hinzufügen. Aber wenn der Benutzer ein bereits vorhandenes keyword verändert, dann soll das alte keyword gelöscht werden.

nwp3 schrieb:

libclang
Das willst du nicht alles selber schreiben.

Ja also so umfangreich zumindest nicht, aber prinzipiell schon. Ich will das halt lernen sowas zu bauen.

happystudent schrieb:

Klar kann ich die aktuelle Liste nehmen und einfach gefundene keywords hinzufügen. Aber wenn der Benutzer ein bereits vorhandenes keyword verändert, dann soll das alte keyword gelöscht werden.

Nicht hinzufügen, ersetzen.

list = parseDocument();
wait_until_user_changed_document();
list = parseDocument();
//Tadaaa! Alle neuen keywords vorhanden und keine alten Keywords mehr drin

Columbo

liste_1.insert(liste_1.end(), make_move_iterator(begin(tmp)), make_move_iterator(end(tmp)));

Und das findest du wirklich schoener als

for( auto& a : tmp )
    liste_1.push_back( move(a) );

happystudent

nwp3 schrieb:

Nicht hinzufügen, ersetzen.

list = parseDocument();
wait_until_user_changed_document();
list = parseDocument();
//Tadaaa! Alle neuen keywords vorhanden und keine alten Keywords mehr drin

Klar geht das so wenn man es sich sehr einfach machen will. Das ist aber extrem ineffizient, da dann nach jedem Tastenanschlag folgendes gemacht werden muss:

void on_document_changed()
{
	std::vector<std::string> list = parse_document();

	std::vector<std::string> tmp = full_list; // Hier muss erstmal die rießige Liste kopiert werden -> teuer

	for (std::vector<std::string>::iterator i = list.begin() + 1, e = list.end(); i != e; ++i) {
		if (previous_is_class(*(i - 1)))
			add_keyword(tmp, *(i - 1));
	}

	// Liste wird in jedem Aufruf verändert und muss daher immer wieder sortiert werden -> teuer
	std::sort(tmp.begin(), tmp.end(), sort_method);

	show_list(tmp);
}

Das ist so zwar total einfach und man hat keine Probleme damit dass irgendwelche keywords nicht passen. Aber es ist halt auch extrem ineffizient.

In 90% der Fälle führt eine Benutzereingabe nicht zu einer Veränderung der keywords. Daher sollte in diesen Fällen die Liste auch nicht angefasst werden.

parse_document() parst nur das Dokument in dem der Nutzer gerade tippt.
full_list enthält alle Keywords aller Dokumente.
temp muss deswegen in full_list integriert werden, damit man nur das aktuelle und nicht alle Dokumente parsen muss.
Soweit richtig?
Ich würde überlegen getrennte Listen pro Dokument zu haben.
Weiterhin nützen dir die Keywords wenig, denn die Bedeutung eines Keywords kann sich mit der Änderung eines anderen Keywords in einem anderen Dokument ändern. Weiterhin willst du bestimmt gar nicht alle Keywords, sondern nur die aktuell definierten. Kannst du nochmal erklären was du mit der Liste tun willst?

happystudent

nwp3 schrieb:

parse_document() parst nur das Dokument in dem der Nutzer gerade tippt.
full_list enthält alle Keywords aller Dokumente.
temp muss deswegen in full_list integriert werden, damit man nur das aktuelle und nicht alle Dokumente parsen muss.
Soweit richtig?

Perfekt richtig.

nwp3 schrieb:

Ich würde überlegen getrennte Listen pro Dokument zu haben.
Weiterhin nützen dir die Keywords wenig, denn die Bedeutung eines Keywords kann sich mit der Änderung eines anderen Keywords in einem anderen Dokument ändern. Weiterhin willst du bestimmt gar nicht alle Keywords, sondern nur die aktuell definierten. Kannst du nochmal erklären was du mit der Liste tun willst?

Ok. Also es gibt eine bestimmte Anzahl fixer keywords die immer da sind. So wie zum Beispiel "if", "for", "while" etc. Davon gibts in der Sprache für die ich das mache aber eine ganze Menge, etwa 7000 native Statements und Typen.

Die Liste wird benutzt um Auto-Completion anzubieten. Das funktioniert auch schon alles sehr gut mit einer fixen keyword Liste. Der Lexer dafür ist auch schon fertig. Probleme gibt es jetzt eben bei dynamischen keywords, was ja ungleich schwieriger ist.

Bevor ich mich allerdings um den Parser und den AST kümmer, wollte ich erstmal eine möglichst effiziente Methode implementieren um keywords hinzuzufügen und wieder zu entfernen. Hier bin ich eben grade am überlegen wie ich das am besten mache. Dabei sollte die keyword Liste wirklich nur dann geupdated werden, wenn nötig, sprich wenn ein neues keyword vorliegt oder ein altes verändert/gelöscht wurde.

Das Ganze wäre natürlich gelöst wenn ich immer nur den vom Nutzer editierten Bereich parsen müsste (was sowieso viel besser wäre), aber momentan ist mir nicht klar wie ich das machen könnte ohne dass ich alle Token bis zum Dokument-Ende updaten muss.

Ein Token ist bei mir momentan nur durch seine Start- und End-Position definiert. Dadurch erspare ich mich in jedem Durchgang tausende string Objekte zu erstellen was die Ganze Sache erheblich beschleunigt. Wenn ich jetzt allerdings am Dokument-Anfang editiere, verändern sich dadurch ja auch alle Positionen der darauf folgenden Token was sehr schlecht ist.

Nach einiger Recherche bin ich auch auf diesen Post von Eric Lippert gestoßen, der ja Intellisense für C# mitentwickelt hat. Laut seiner Aussage kann man genau dieses Problem dadurch vermeiden dass man nicht die Positionen der Token speichert, sondern deren Länge. Das leuchtet auch ein, allerdings kann ich mit der Länge ja meine string nicht aus dem Dokument holen, da ich ja nicht weiß wo im Dokument er anfängt.

Das sind so die Probleme die ich zur Zeit habe/zu lösen versuche

Sowas hatte ich auch mal gemacht. Ich hatte statt Positionen Offsets zum vorherigen Objekt gespeichert. Weiterhin waren bei mir Blöcke Objekte, sodass ich immer ganze Blöcke übersprungen habe. Wenn jemand in einem Block etwas eingetippt hat, dann musste ich alle Objekte bis zu der Position durchgehen und dann ein Object aktualisieren. Wenn global etwas eingefügt wurde musste ich auch nur alle Funktionsblöcke bis zu dieser Stelle durchgehen und dann ein einzelnes Objekt ändern. Vielleicht sollte ich mich da nochmal dran setzen, hatte das damals in grauenhaftem C geschrieben und bin an Funktionspointercasts gescheitert