Felder auf Gleichheit überprüfen



  • @SeppJ sagte in Felder auf Gleichheit überprüfen:

    Faustregel: Sortieren stets vermeiden, außer es geht explizit darum, hinterher eine sortierte Menge zu haben. Sortieren als Zwischenschritt ist nur seltenst nötig, dafür aber sehr kostspielig. Siehe beispielsweise wobs Beitrag für eine viel bessere Umsetzung der gleichen Grundidee.

    In eine Map eintragen ist aber auch ein implizites Sortieren. Ist Performance relevant? Wenn wobs Interpretation der Aufgabe gilt, rulft man einfach das hier auf: https://en.cppreference.com/w/cpp/algorithm/is_permutation



  • @SeppJ sagte in Felder auf Gleichheit überprüfen:

    Faustregel: Sortieren stets vermeiden, außer es geht explizit darum, hinterher eine sortierte Menge zu haben. Sortieren als Zwischenschritt ist nur seltenst nötig, dafür aber sehr kostspielig. Siehe beispielsweise wobs Beitrag für eine viel bessere Umsetzung der gleichen Grundidee.

    Man sollte vielleicht noch erwähnen, dass das nur der Fall ist, wenn es sich bei der map, die wob erwähnt, um eine mit O(1)O(1)-Zugriffen handelt.

    Ansonsten sind beide Lösungen gleich "kostspielig" und die Sortier-Variante mit so etwas simplem wie return a.size() == b.size() && equal(sort(a), sort(b)) sogar noch kürzer und eleganter.

    Das mit der Faustregel sehen ich auch nicht so ehern, für geometrische Algorithmen z.B. braucht man das durchaus häufiger. Allerdings finde ich es auch nicht gut, unterschiedslos zu sortieren und diese praktische Eigenschaft nach dem Funktionsaufruf einfach wegzuwerfen. Mir gefiele es besser, wenn "ist sortiert" eine Vorbedingung für die Funktion wäre, so dass bereits sortierte Eingabedaten nicht erneut sortiert werden müssen (was die Funktion dann allerdings zu einem banalen equal-Wrapper macht, vielleicht noch mit ner is_sorted-Assertion).

    Nachtrag:

    @TGGC sagte in Felder auf Gleichheit überprüfen:

    Wenn wobs Interpretation der Aufgabe gilt, rulft man einfach das hier auf: https://en.cppreference.com/w/cpp/algorithm/is_permutation

    Heh, coole Idee - aber die angegebene Laufzeit! Uiui 😉
    Ich frage mich gerade warum O(n2)O(n^2) und ob is_permutation nicht auch mit dem doppelten Sortieren geht. Eventuell problematisch wegen den anderen Iterator-Anforderungen... muss da nochmal drüber nachdenken.


  • Mod

    @TGGC sagte in Felder auf Gleichheit überprüfen:

    @SeppJ sagte in Felder auf Gleichheit überprüfen:

    Faustregel: Sortieren stets vermeiden, außer es geht explizit darum, hinterher eine sortierte Menge zu haben. Sortieren als Zwischenschritt ist nur seltenst nötig, dafür aber sehr kostspielig. Siehe beispielsweise wobs Beitrag für eine viel bessere Umsetzung der gleichen Grundidee.

    In eine Map eintragen ist aber auch ein implizites Sortieren. Ist Performance relevant? Wenn wobs Interpretation der Aufgabe gilt, rulft man einfach das hier auf: https://en.cppreference.com/w/cpp/algorithm/is_permutation

    Ja, da habe ich im Kopf map mit unordered_map gleichgesetzt 🙂
    Wie es schon buchstäblich im Namen vorkommt, ist die unordered_map hier die bessere Wahl, da man die Sortiereigenschaft gar nicht braucht und daher auch nicht teuer bezahlen möchte.



  • Ich hab's BTW gestern ausprobiert: mit unordered_map ist die Sache auf meinem PC ab bestimmten N tatsächlich schneller als mit Sortieren.

    EDIT: Ne, sort ist überall schneller, siehe spätere Beiträge.


  • Mod

    @hustbaer sagte in Felder auf Gleichheit überprüfen:

    Ich hab's BTW gestern ausprobiert: mit unordered_map ist die Sache auf meinem PC ab bestimmten N tatsächlich schneller als mit Sortieren.

    Muss es ja. Ich bin eher überrascht, dass es N gibt, bei denen es nicht so ist. Was ist den ungefähr die Größenordnung des N beim Übergang?



  • @hustbaer
    Kommt sicher auch auf den genauen Input an, z.B. wenns keine sinnvolle Hashfunktion gibt oder einen eingeschränkten Wertebereich. is permutation braucht weder Hash noch Vergleichsoperator, kann daher diese Aufgabe auf einem abstrakterem Level lösen, gibt aber z.B. nicht aus, welcher int genau fehlt. Daher fällt eine sinnvolle Antwort schwer ohne die Rahmenbedingungen zu kennen. Mein persönlicher Ansatz wäre die std Algorithmen zu nutzen bis es ein Problem damit gibt (z.b. gemessener Bottleneck, weil die Vectoren ständig größer N sind). Dann kann man nochmal nachdenken.



  • @SeppJ
    Break-even für unordered_map<int, int> vs. 2x sort(vector<int>) ist irgendwo zwischen 1k und 10k, vermutlich im Bereich 2k~5k. (BTW: map<int, int> ist bis 10M die langsamste Variante, und > 10M hab' ich nicht getestet.)

    Das alleine wundert mich nicht, wundert mich eher noch dass der break-even so früh kommt. So ne unordered_map hat halt doch Overhead: braucht mehr Speicher, muss dauernd Hashwerte berechnen etc. Und ich bin nicht sicher ob der Speicher für die erste "Value" eines Buckets im Table der unordered_map eingebaut ist. Wenn nicht käme noch eine Allocation pro Value dazu, trotz reserve.

    Was aber strange ist: alle drei von mir getesteten Varianten skalieren ab ~10K ziemlich genau linear. Dabei sollten die doch N log N skalieren.

    EDIT: Ne, sort ist überall schneller, siehe spätere Beiträge.

    Code hab' ich leider nicht zur Hand, bin in der Arbeit, und Code liegt zu Hause. Kann ich heute Abend posten. Ist aber auch in ein paar Minuten selbst geschrieben.



  • @Finnegan sagte in Felder auf Gleichheit überprüfen:

    Heh, coole Idee - aber die angegebene Laufzeit! Uiui 😉
    Ich frage mich gerade warum O(n2)O(n^2) und ob is_permutation nicht auch mit dem doppelten Sortieren geht. Eventuell problematisch wegen den anderen Iterator-Anforderungen... muss da nochmal drüber nachdenken.

    Jede Lösung hat im Grenzfall diese Laufzeit, z.B. wenn alle Werte den gleichen Hash liefern wird die unordererd map alles in einen Bucket einsortieren und dann auch einen Vergleich auf alle Paare aufrufen. Nur wenn man alles mit allem vergleicht kann man am Ende ja sehen, ob auch alles übereingestimmt hat, wenn man nicht durch "Glück" (geschicktes Sortieren, geschicktes Anordnen nach Hash etc.) zufällig direkt die richtigen Sachen vergleicht.



  • @TGGC Ja, es kommt immer auf die genauen Umstände an. Wenn der Fall häufig ist dass die meisten Zahlen in a überhaupt nicht in b vorkommen, dann wird std::is_permutation vermutlich alles andere abhängen. Oder auch wenn die Sequenzen oft identisch sind (also auch identisch sortiert).

    Ansonsten muss man halt wissen wie wichtig die Performance bei grösseren Inputs ist. Wenn man Grund zur Annahme hat dass O(N^2) gut genug sein könnte, spricht sicher nichts dagegen erstmal std::is_permutation zu verwenden.



  • @TGGC sagte in Felder auf Gleichheit überprüfen:

    @Finnegan sagte in Felder auf Gleichheit überprüfen:

    Heh, coole Idee - aber die angegebene Laufzeit! Uiui 😉
    Ich frage mich gerade warum O(n2)O(n^2) und ob is_permutation nicht auch mit dem doppelten Sortieren geht. Eventuell problematisch wegen den anderen Iterator-Anforderungen... muss da nochmal drüber nachdenken.

    Naja std::is_permutation kann IMO nichtmal im Durchschnitt besser als N^2 sein, weil sie vom Value-Type nichts fordert ausser dass man auf Gleichheit testen kann. Ich glaube nicht dass das genug für irgendwelche schlauen Algorithmen ist. Natürlich könnte eine Library-Implementierung std::is_permutation für Dinge wie Integers speziell implementieren, aber das ist dann wieder ein anderes Thema. Für generische T muss N^2 mMn. der Normalfall sein und nicht der Grenzfall.

    Jede Lösung hat im Grenzfall diese Laufzeit

    Jede linear schnelle Lösung. Mit Sortieren (z.B. Merge-Sort) oder Bäumchen schafft man problemlos N log N.



  • Ich glaube das ist nicht garantiert, weil das Kriterium der Sortierung ein Anderes als das für Identität sein könnte oder das Ergebnis von > und < komplett unbestimmt.



  • Oh, da hat meine 08/15 Antwort ja noch für Gesprächsstoff gesorgt 😅. Interessant was so über die verschiedenen Möglichkeiten geschrieben wurde. Danke, hab wieder einiges gelernt 😁



  • @TGGC sagte in Felder auf Gleichheit überprüfen:

    Ich glaube das ist nicht garantiert, weil das Kriterium der Sortierung ein Anderes als das für Identität sein könnte oder das Ergebnis von > und < komplett unbestimmt.

    Und ich glaube dass du damit vollkommen richtig liegst 🙂 Ich wollte auch gar nicht die Design-Entscheidung kritisieren das so zu machen. Ich wollte nur erklären warum N^2 hier "normal" ist und nicht bloss worst-case.



  • Ich meine mich daran zu erinnern, dass man für Integer in einem begrenzten Wertebereich auch schnellere Sortierverfahren hat (radix sort?). Wie würde es sich damit verhalten?



  • @PeterPanzer31 sagte in Felder auf Gleichheit überprüfen:

      if (v1[0] = v2[i] )
    

    ganz böse fehlerquelle btw.



  • @HarteWare Radix-Sort ist dann aber fast schon das selbe wie die hier vorgeschlagene Map-Variante. Nur mit einer weniger effizienten Map-Implementierung, nämlich einem Radix-Tree. Dann lieber gleich (Hash)Map.



  • War neugierig und hab mir auch mal die alte Programmierer-Weisheit zu Herzen genommen (Messen!!!einself!). Gut möglich, dass ich was verbockt habe, aber ich konnte die Überlegenheit der unordered_map zumindest bis N=226N=2^{26} nicht bestätigen:

    Vektoren bis N=210N=2^{10}
    Vektoren bis N=216N=2^{16}
    Vektoren bis N=226N=2^{26}

    Gemessen wurde mit Vektoren, die mit int-Werten von 0 bis N-1 gefüllt und dann mittels std::shuffle zufällig permutiert wurden.

    Quellcode (benötigt Google Benchmark):

    benchmark-vecequal.cpp
    benchmark-vecequal-64k.cpp (mostly Copy&Paste)
    benchmark-vecequal-1k.cpp (mostly Copy&Paste)

    Vielleicht hat ja jemand von Euch eine Idee, wieso ich auf solche Messwerte komme. Ich tippe darauf, dass ich irgendwo einen Fehler gemacht oder etwas ineffizientes geschrieben habe (rehash/reserve?). Wenn sich die unordered_map nichtmal bei N=228N=2^{28} lohnt, dann fände ich das schon bemerkenswert, obwohl die schon eine stadtbekannte Cache-Sau ist 😉

    @hustbaer Wie war das noch mit deinem Code, jetzt am Abend? Den würd ich gern mal vergleichen die Tage.

    Nachtrag: Vektoren von 0-1024, weil ich eh noch alles offen hatte. Seltsam schnurgerade das alles und ohne irgendwelche Cache-Hüpfer. Bestärkt mich eher darin, dass etwas nicht stimmt, obwohl es hübsch aussieht. Frage mich auch ob die CPU Time im Gegensatz zur Real Time (Wall Time) der bessere Wert ist. Intuitiv denke ich ja, weil dort weniger OS/Hardware-Aussetzer drin sein sollten.



  • @Finnegan Habs nur mal überflogen. Aber

    std::unordered_map<int, int> c;
    std::for_each(std::begin(a), std::end(a), [&](int v) { ++c[v]; });
    

    scheint mir potentiell schonmal merkwürdig. Sicher dass hier mit 0 initialisiert wird?



  • @DNKpp sagte in Felder auf Gleichheit überprüfen:

    scheint mir potentiell schonmal merkwürdig. Sicher dass hier mit 0 initialisiert wird?

    Yep: unordered_map::operator[]:

    When the default allocator is used, this results in the key being copy constructed from key and the mapped value being value-initialized.
    ...
    value initialization
    ...
    4) otherwise, the object is zero-initialized.



  • @Finnegan
    Oops!
    Gut dass du das geschrieben hast. Ich hab Mist gebaut...

    std::vector<MyType> rand_vec(size_t size) {
    	std::default_random_engine engine;
    	engine.seed(123);
    	std::uniform_int_distribution<MyType> distribution(1, 1000); // Oops
    
    	std::vector<MyType> v;
    	v.reserve(size);
    	for (size_t i = 0; i < size; i++)
    		v.push_back(distribution(engine));
    
    	engine.seed(std::random_device{}());
    	std::shuffle(v.begin(), v.end(), engine);
    	return v;
    }
    

    🤦🏻♂ 🤦🏻♂
    Ist dann auch sehr verwunderlich dass der Break-Even bei knapp über 1000 war 🤪
    Keine Ahnung warum ich da 1000 reingeschrieben hab. Vermutlich weil ich beim Schreiben bloss an die sort Variante gedacht hab, und für die is das ziemlich wörscht. (Naja, genaugenommen auch da nicht, und der Grund warum nicht erklärt dann auch genau warum ich lineare Skalierung gesehen hab statt N log N -- was jetzt auch nicht mehr der Fall ist... hachjeh.)

    Wenn man das mit etwas sinnvollerem wie 10 * size ersetzt sehen die Ergebnisse auf einmal ganz anders aus.

    Vollständig:

    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <map>
    #include <unordered_map>
    #include <random>
    #include <chrono>
    #include <stddef.h>
    
    typedef int MyType;
    
    std::vector<MyType> rand_vec(size_t size) {
        std::default_random_engine engine;
        engine.seed(123);
        std::uniform_int_distribution<MyType> distribution(1, static_cast<MyType>(10 * size));
    
        std::vector<MyType> v;
        v.reserve(size);
        for (size_t i = 0; i < size; i++)
            v.push_back(distribution(engine));
    
        engine.seed(std::random_device{}());
        std::shuffle(v.begin(), v.end(), engine);
        return v;
    }
    
    bool compare_via_sort(std::vector<MyType> a, std::vector<MyType> b) {
        std::sort(a.begin(), a.end());
        std::sort(b.begin(), b.end());
        return a == b;
    }
    
    bool compare_via_tmap(std::vector<MyType> const& a, std::vector<MyType> const& b) {
        std::map<MyType, ptrdiff_t> tmap;
        for (auto v : a)
            tmap[v]++;
        for (auto v : b)
            tmap[v]--;
    
        for (auto e : tmap)
            if (e.second != 0)
                return false;
    
        return true;
    }
    
    bool compare_via_umap(std::vector<MyType> const& a, std::vector<MyType> const& b) {
        std::unordered_map<MyType, ptrdiff_t> umap;
        umap.reserve(a.size() * 2);
        for (auto v : a)
            umap[v]++;
        for (auto v : b)
            umap[v]--;
    
        for (auto e : umap)
            if (e.second != 0)
                return false;
    
        return true;
    }
    
    volatile bool result_dummy = false;
    volatile void const* ptr_dummy = nullptr;
    volatile long long t_dummy = 0;
    
    template <class F>
    long long bench(F f, size_t n) {
        auto const a = rand_vec(n);
        ptr_dummy = a.data();
        auto const b = rand_vec(n);
        ptr_dummy = b.data();
    
        using clock = std::chrono::high_resolution_clock;
        auto const t0 = clock::now();
        result_dummy = f(a, b);
        auto const t1 = clock::now();
        auto const dur = t1 - t0;
        auto const dur_ns = std::chrono::duration_cast<std::chrono::nanoseconds>(dur).count();
        t_dummy = dur_ns;
        return dur_ns;
    }
    
    template <class F>
    void bench2(F f, size_t n, char const* name) {
        auto best = std::numeric_limits<long long>::max();
        for (size_t i = 0; i < 10; i++) {
            auto const d = bench(f, n);
            if (d < best)
                best = d;
        }
    
        std::cout << name << "[" << n << "]: " << best << " ns\n";
    }
    
    int main() {
        for (size_t n = 10; n <= 1'000'000; n *= 10) {
            bench2([](auto a, auto b) { return compare_via_sort(a, b); }, n, "sort");
            bench2([](auto a, auto b) { return compare_via_tmap(a, b); }, n, "tmap");
            bench2([](auto a, auto b) { return compare_via_umap(a, b); }, n, "umap");
        }
    }
    

    Output:

    sort[10]: 700 ns
    tmap[10]: 2000 ns
    umap[10]: 1800 ns
    sort[100]: 6200 ns
    tmap[100]: 20800 ns
    umap[100]: 19400 ns
    sort[1000]: 82500 ns
    tmap[1000]: 244600 ns
    umap[1000]: 143200 ns
    sort[10000]: 1008500 ns
    tmap[10000]: 3306700 ns
    umap[10000]: 1435800 ns
    sort[100000]: 13107800 ns
    tmap[100000]: 62987400 ns
    umap[100000]: 22860400 ns
    sort[1000000]: 159867600 ns
    tmap[1000000]: 1874229500 ns
    umap[1000000]: 497277000 ns
    

    Fazit: umap hasn't got a prayer.

    Was dann auch mehr meiner ursprünglichen Vermutung entspricht. Wenigstens das.


Anmelden zum Antworten