unordered_set sortieren?



  • happystudent schrieb:

    Ich will erst ganz am Ende sortieren, wenn schon alle Elemente eingefügt sind.

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

    Edit: Und wenn nötig, nach dem Sortieren halt noch std::unique().



  • Mechanics schrieb:

    Sortieren: O(n * log(n))
    Einfügen in unordered_set: O(1)

    Also ist es insgesamt besser, gleich ein set zu nehmen, als in ein unordered_set einzufügen und nachträglich zu sortieren.

    Das kann man nicht so allgemein sagen. Angenommen, es werden n verschiedene Elemente je m mal eingefügt.

    Dann ist unordered_set+sortieren insgesamt O(n*m+n log n) und set O(n*m*log n) Wenn m asymptotisch grösser ist als log n (z.B. m=n), kann unordered_set+sortieren besser sein.



  • Caligulaminus schrieb:

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

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

    5rthsdfaser schrieb:

    Das kann man nicht so allgemein sagen. Angenommen, es werden n verschiedene Elemente je m mal eingefügt.

    Dann ist unordered_set+sortieren insgesamt O(n*m+n log n) und set O(n*m*log n) Wenn m asymptotisch grösser ist als log n (z.B. m=n), kann unordered_set+sortieren besser sein.

    Jo. 👍



  • 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.



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



  • 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.



  • 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());
    


  • 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 konstanter1 Zeit finden und sie über den vector<foo*> sortiert betrachten. Oder halt umgekehrt, je nachdem, was besser passt.

    1D.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.



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



  • 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.



  • 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.



  • 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.



  • 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
    

  • Mod

    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) );
    


  • 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.


Anmelden zum Antworten