unordered_set sortieren?



  • Hallo,

    ich hab ein Problem mit dem unordered_set Datentyp der Standard-Library. Und zwar würde ich dieses gerne mittels std::sort sortieren, was allerdings nicht hinhaut. Nach Recherche mittles Google geht das nicht und der einzige Wege wäre das unordered_set in einen anderen Container zu kopieren und dann wieder zurück zu kopieren.

    Diesen zusätzlichen Kopier-Vorgang will ich aber vermeiden. Gibt es wirklich keine andere, effizientere Möglichkeit ein unordered_set zu sortieren?

    Grüße,
    hs



  • Nein



  • Du könntest die Elemente vom unordered_set in einen vector moven.

    Aber warum kein normales set wenn du die Elemente sortiert haben möchtest?



  • unordered_set|ordered_set schrieb:

    Aber warum kein normales set wenn du die Elemente sortiert haben möchtest?

    Weil ich pro Iteration viele Elemente in die Datenstruktur einfüge. Das Sortieren kann erst ganz am Ende erledigt werden, wenn alle Elemente hinzugefügt wurden. Ein normales set sortiert ja nach jedem Einfügevorgang, was in so einem Fall ja sehr schlecht ist.

    manni66 schrieb:

    Nein

    Danke für diese konstruktive Antwort 🙂
    Welche Datenstruktur würde sich dann besser für mein Vorhaben eignen?



  • happystudent schrieb:

    Ein normales set sortiert ja nach jedem Einfügevorgang, was in so einem Fall ja sehr schlecht ist.

    Nein, da wird nichts nachträglich sortiert. Das Element wird gleich an die richtige Stelle eingefügt.

    happystudent schrieb:

    Welche Datenstruktur würde sich dann besser für mein Vorhaben eignen?

    std::set natürlich.



  • aqe schrieb:

    Nein, da wird nichts nachträglich sortiert. Das Element wird gleich an die richtige Stelle eingefügt.

    Ja, aber das "an der richtigen Stelle Einfügen" kostet doch auch?

    std::set::insert hat logarithmische Komplexität für die Einfügeoperation
    std::unordered_set::insert hat konstante Komplexität für die Einfügeoperation

    Also ist das hier auf jeden Fall ungünstiger. Ich will erst ganz am Ende sortieren, wenn schon alle Elemente eingefügt sind.



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



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


Log in to reply