Java Zwei verschiedene String-Arrays: Prüfen, ob beide Arrays die gleichen Inhalte haben

[KROKvsKROK]

Hallo,

Nehmen wir an ich habe in meinem Programm viele verschiedene Arrays von der Länge 5. Jedes Array enthält also 5 Strings.
Ich möchte jetzt prüfen, ob zwei Arrays die selben Strings beinhalten (Die Reihenfolge dieser Strings in einem Array spielt keine Rolle, es kommt nur auf die Elemente an sich an).

Beispiel:

String[] a = {"Hallo", "wie", "gehts"};
String[] b = {"wie", "gehts", "Hallo"};

Die beiden Arrays a und b haben also (in meinem Kontext hier) den selben Inhalt.

Gibt es dafür bereits irgendetwas fertiges aus der API? Ich konnte bisher nichts finden.

 

[Rossie]

http://docs.oracle.com/javase/7/doc...quals(java.lang.Object[], java.lang.Object[])
http://docs.oracle.com/javase/7/doc...quals(java.lang.Object[], java.lang.Object[])

 

[SymA]

Gibt es dafür bereits irgendetwas fertiges aus der API? Ich konnte bisher nichts finden.

Such mal weiter...

 

[xbrtll]

@soares: In beiden Fällen ist aber die Reihenfolge der Elemente relevant.

Wenn es auf den zusätzlichen Speicherverbrauch nicht ankommt, könnte man kopieren, sortieren und dann vergleichen (deepEquals).

 

[DefconDev]

Du könntest auch die einzelnen Strings vorher abspeichern und deren Bezeichner im array ablegen. Dann in einer methode die einzelnen Strings innerhalb des Arrays vergleichen lassen.

Das wäre die primitivste Art und Weise ohne jetzt zu googlen^^

 

[kuddlmuddl]

Wenns dir um Performance geht würde ich den Quelltext von diesem Algorithmus nach Java portieren:
http://www.cplusplus.com/reference/algorithm/is_permutation/
denn ich gehe mal stark davon aus dass es schneller geht als die naheliegenden vorgeschlagenden Lösungen.

http://stackoverflow.com/questions/5959517/where-to-download-c-stlsource-code-both-h-and-cpp-files

 

[Rossie]

@soares: In beiden Fällen ist aber die Reihenfolge der Elemente relevant.

Wenn es auf den zusätzlichen Speicherverbrauch nicht ankommt, könnte man kopieren, sortieren und dann vergleichen (deepEquals).

Dass er damit die Arrays vor dem Vergleich sortieren muss, halte ich als vertretbar. Von einer optimalen Lösung war nicht die Rede. Ein wenig Eigenleistung schadet auch nicht

 

[xbrtll]

Dann schreibe eben noch einen Satz dazu, dass das nicht als direkte Antwort auf die Frage gedacht war.

Wenns dir um Performance geht würde ich den Quelltext von diesem Algorithmus nach Java portieren:

Der hat eine quadratische Laufzeit, mein Ansatz nur n log n.

 

[Freezedevil]

Dass er damit die Arrays vor dem Vergleich sortieren muss, halte ich als vertretbar. Von einer optimalen Lösung war nicht die Rede. Ein wenig Eigenleistung schadet auch nicht

Du könntest auch einfach zugeben, dass du die Frage nicht richtig gelesen hast, aber sowas macht man ja nicht...
Der TE erweckt nicht den Eindruck, dass er nicht in der Lage wäre selbst eine Lösung zu finden. Die Frage war und ist ob es eine Standardfunktion gibt. Scheinbar gibt es keine. Außer SymA, der schlauer als der Rest von uns ist, hat jedenfalls inklusive mir keiner eine parat.

Ergänzung (24. Mai 2014)

Der hat eine quadratische Laufzeit, mein Ansatz nur n log n.

Bekommt man auch in O(n) hin wenn man nicht so auf den Speicher gucken muss und ich grad keinen Denkfehler hab.

 

[xbrtll]

O(n) vielleicht mit Hashing, aber selbst da bin ich mir gerade nicht ganz sicher (also im Bezug auf garantiertes O(n), im Erwartungswert sollte das schon passen).

Ansonsten ist n log n auch untere Schranke, etwa weil das hier mit k = n/2 ein Teilproblem ist.

 

[kuddlmuddl]

Der hat eine quadratische Laufzeit, mein Ansatz nur n log n.

Interessant, steht ja sogar dort auf der cplusplus Seite - hatte ich garnicht erwartet. Wäre interessant zu wissen ob die evtl. trotzdem ein besseres Verfahren gefunden haben was die Kopiererei spart und trotzdem nicht stumpf jeden Eintrag im ersten Array einfach im zweiten sucht.
Ich will jetzt keine Erbsenzählerdiskussion starten aber aus reinem Interesse: Beim WikiArtikel zu Quicksort steht, dass er (auch) eine worst-case O(n^2) Laufzeit hat und trotzdem idR verwendet wird. Bedeutet das nicht, dass die Java-Api-Variante mittels sortieren und vergleichen auch eine worst-case, also O(n^2) komplexität hat? Das hier http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html liest sich zumindest so. Aber man könnte natürlich einen Sort-Algo nehmen der worst nur nlog(n) hat und dann is man zumindest theoretisch optimal.
Ich vermute mal die kopiererei kostet aber in der Realität trotz niedriger Komplxität sehr viel Zeit.

 

[xbrtll]

QuickSort hat tatsächlich eine quadratischen Worst Case, dieser ist in der randomisierten Variante aber sehr unwahrscheinlich (einfach gesagt müssen "oft" ungünstige Pivotelemente gewählt werden, wodurch die Wahrscheinlichkeit dafür exponentiell abnimmt).

Die API bietet aber auch MergeSort mit garantiertem n log n.

 

[DaVian]

Man kann auch einfach ein bei gegebenem Array A und B:
A.containsAll(B) & B.containsAll(A)

 

[xbrtll]

a) In Java bietet ein Array selbst keine solche Methode.
b) Die Laufzeit ist vermutlich schlechter.
c) Es wären dann {"a","b"} und {"a","b","a"} gleich. Ich habe die Beschreibung des TO so interpretiert, dass dieses Verhalten nicht erwünscht ist, denn es ist nur vom Ignorieren der Reihenfolge, nicht der Häufigkeiten die Rede.

 

[Grantig]

Ich würde sagen Hashing ist am schnellsten:

public static <E> boolean isPermutation(E[] arr1, E[] arr2)
{
    if (arr1.length != arr2.length)
    {
        return false;
    }

    HashMap<E, Integer> map = new HashMap<E, Integer>();

    for (int i = 0; i < arr1.length; i++)
    {
        if (map.containsKey(arr1[i]))
        {
            map.put(arr1[i], map.get(arr1[i]) + 1);
        }
        else
        {
            map.put(arr1[i], 0);
        }
    }

    for (int i = 0; i < arr2.length; i++)
    {
        if (map.containsKey(arr2[i]))
        {
            int val = map.get(arr2[i]);

            if (val < 0)
            {
                return false;
            }
            else
            {
                map.put(arr2[i], val - 1);
            }
        }
        else
        {
            return false;
        }
    }

    return true;
}

Ist Omega(n) wenn mich nicht alles täuscht. Mit ner Hashtable statt der HashMap wärs sogar O(n), allerdings ist dann 'null' im Array nicht erlaubt.

 

[Jack159]

Mir kommt es in diesem Fall nicht auf die Schnelligkeit an. Ganz im Gegenteil, je kürzer die Lösung ist, desto besser (Laufzeit ist egal).

 

[DaVian]

für containsAll müsste mans halt in eine collection geben.
Aber wenn er wie du schon erwähnt hast duplikate nicht haben will ist natürlich falsch

 

[Rossie]

Du könntest auch einfach zugeben, dass du die Frage nicht richtig gelesen hast, aber sowas macht man ja nicht...
Der TE erweckt nicht den Eindruck, dass er nicht in der Lage wäre selbst eine Lösung zu finden. Die Frage war und ist ob es eine Standardfunktion gibt. Scheinbar gibt es keine. Außer SymA, der schlauer als der Rest von uns ist, hat jedenfalls inklusive mir keiner eine parat.

Ich poste in den meisten Fällen keine kompletten Lösungen, sondern gebe nur Hinweise, gerne auch mal nur einen Link. Je nachdem wie der TE sich an der Diskussion beteiligt oder nicht, poste ich dann weiter oder eben nicht. Ist auch hier wieder interessant zu sehen, dass viele Lösungen angeboten werden, ohne dass der TE schlüssig dargelegt hätte, welche Kriterien letztendlich wichtig sind.

 

[Donnidonis]

Ich würde einfach beide Arrays sortieren, und dann ein equals/deepequals machen, da dir die Laufzeit ja egal ist.

 

[DasBoeseLebt]

Könnte man nicht auch, weil beide Arrays ja nur Strings enthalten, .. Array a zu einem ganzen String zusammenbasteln(Wörter mit Leerzeichen getrennt; Wenn Wörter aber Leerzeichen enthalten können, nen anderes Trennungszeichen nehmen) und mit dem Elementen aus Array b prüfen, ob Element aus b in dem String aus a enthalten ist?

Man müsste dann halt nicht erst groß rumkopieren/sortieren, sondern könnte mit ganz normalen StringOperationen arbeiten und auch auf doppelte Elemente prüfen. (indexOf usw).

?!