Felder auf Gleichheit überprüfen



  • Hallo zusammen,
    mein Anliegen lautet wie folgt :
    Ich möchte zwei Felder mit beliebig vielen Elementen vom Typ vector<int> in einer Funktion auf Gleichheit überprüfen,dabei spielt die Position der Elemente keine Rolle.

    Mein Ansatz wäre eine For-Schleife die den ersten Vektor durchgeht und falls ein Gleiches Element gefunden wird, einen Wahrheitswert true (ansonsten false) ausgibt. Doch wie soll ich diese For-Schleife mit den Abfragen für die weiteren Elemente verbinden ?

    Bisher habe ich :

    bool VecEqual(vector <int> v1, vector <int> v2)
    {
    bool Gleichheit;
    for (int i = 0; i < v1.size(); i++)
    	{
    
    		if (v1[0] = v2[i] )
    		{
    			Gleichheit == true
                     }
    if (Gleichheit==true)
    return true;
    else 
    return false;
    }


  • Kann man nur eine Schleife in einem Programm machen?



  • Abgesehen davon, dass der Rest noch keinen Sinn macht, kann man das

    if (Gleichheit==true)
    return true;
    else 
    return false;
    

    nicht kürzer schreiben?



  • @PeterPanzer31
    Die Vectoren sind gleich lang und alle Elemente müssen ein Gegenstück haben?



  • @PeterPanzer31 wenn die Position der Elemente keine Rolle spielt, könntest du eine map machen, in der zu zählst, wie oft welches Element im ersten vector vorkommt. Dann gehst du durch den zweiten vector du subtrahierst jeweils 1 von der Anzahl. Wenn am Ende alle map-Values 0 sind, sind die vectoren gleich. Du kannst sogar vorher abbrechen, wenn beim Subtrahieren -1 rauskommt.



  • In der std gibts dafür passende Algorithmen. Da ich deine Definition von gleich nicht ganz verstand, kann ich dir den korrekten nicht nennen. Also schau am besten mal selbst rein.



  • Ich würde wahrscheinlich erst beide sortieren und dann mit std::equal vergleichen. Aber das ist sicher keine gute Lösung, wegen dem Sortieraufwand.


  • Mod

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

    Ich würde wahrscheinlich erst beide sortieren und dann mit std::equal vergleichen. Aber das ist sicher keine gute Lösung, wegen dem Sortieraufwand.

    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.



  • @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 😁


Log in to reply