unordered_set sortieren?

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

happystudent

So quasi als doppelt verkettete Liste dann? Nervig ist dann natürlich dass man alle Whitespace/Tab/Newline/Comment Blöcke auch noch mittracken muss, aber Ok...

Ist dass die Standard Vorgehensweise für so ein Problem? Da haben sich ja bestimmt schon sehr viele sehr schlaue Leute Gedanken drüber gemacht, also geh ich mal davon aus dass es dafür eine (mehrere?) Standardlösungen gibt?

volkard

happystudent schrieb:

Ist dass die Standard Vorgehensweise für so ein Problem?

Ich fürchte, das Standardvorgehen für so ein Problem ist es, erstmal diverse Bücher über Algorithmen und Datenstrukturen zu lesen und wenn man die Aufgabe angeht, gar kein so Problem zu haben.

Würde da denken an spaghetti stack und trie.