Methoden Vergleichen von zwei Listen in der Geschwindigkeit von O(n+m)

[SnrufjStill]

Hallo, bin die ganze Zeit am Rumdenken komme aber auf nichts Vernünftiges.

Aufgabe:
Zwei Listen Folgen den Regeln der Mengenlehre (es dürfen keine doppelten Elemente in einer Liste sein) ich soll nun die Methode Vereinigung (

) schreien, die steht auch und funktioniert. Jetzt soll sie optimiert werden und in O(m+n) durchlaufen, dabei steht n für die Hauptliste und m für die neue Liste, die dazukommt.

Also durchläuft die Methode einmal Liste 1 und einmal Liste 2 (?)

Momentane Situation:
Ich durchlaufe in der Methode die zweite Liste mit einem Iterator und Vergleiche jedes Element mit der in der ersten Liste mithilfe der Methodecontains, die auch nur eine Art Iterator ist. Also bin ich bei... m + n^n (n hoch n) ?

Egal wie ich es drehe und wende ich komme nicht darauf, wie ich es optimieren kann. Es wird ja am ende immer ein Vergleich benötigt, wenn ein neues Element dazu kommt(da es keine doppelten werte haben darf [ich teste es gerade mit Integer]).

 

[InfectedBytes]

Für sowas bieten sich Sets an, diese sind so aufgebaut, dass sie keine doppelten Einträge aufnehmen können. https://docs.oracle.com/javase/7/docs/api/java/util/Set.html
Eine implementierung wäre z.B. das HashSet
Da kannst du also einfach über Liste A und B drüber laufen und jedes Element dem neuen Set hinzufügen.

 

[Kababär]

Sind die Listen sortiert?
Dann könntest du ggf einen einfachen Algorithmus schreiben für einen iterator, sodass du bei O(n+m) landest.

Falls die Liste nicht sortiert ist, sortiere sie. Dann musst du nicht immer von vorne anfangen.

Mit einem virtuellen Zeiger A und B hälst du jeweils eine Referenz auf die Listen X und Y. Fange bei dem kleineren wert an und gehe solange durch, bis der ursprünglich kleinere wert nicht mehr kleiner ist. Nehme den anderen Zeiger und tue das selbe. Etc

Wo genau liegt das Problem?
Oder verstehe ich dich falsch?

 

[JCODA]

@Kababär : Sortieren ist bestenfalls n*log(n), wenn man vergleichsbasiert sortiert. So kann man nicht auf O(m+n) kommen.

 

[JStein52]

diese sind so aufgebaut, dass sie keine doppelten Einträge aufnehmen können

Das hilft ihm aber nichts, denn um das zu gewährleisten müssen Set's ja auch was tun und das muss natürlich in die Komplexitätsbetrachtung einbezogen werden.

 

[Flown]

Also einfügen kann nur mit O(n) für n Elemente passieren, wenn der Lookup O(1) - wie bei Sets - hat.

 

[JStein52]

Lookup O(1) - wie bei Sets

Wieso ist das so ?

 

[Flown]

Anders gesagt, wenn du erst überprüfen müsstest ob ein Wert in der Liste gespeichert ist(Lookup) hat das eine Komplexität von O(n). Klar oder? Du musst durch die ganze Liste iterieren und im worst-case ist das eben das letzte Element. Wenn du dann n Elemente einfügen möchtest musst du eben n * n Überprüfungen starten => O(n²).
Darum brauchst du wie ich oben schon erwähnt habe einen Lookup O(1) und der wird mit HashCode normalerweise erreicht.

 

[JStein52]

Darum brauchst du wie ich oben schon erwähnt habe einen Lookup O(1) und der wird mit HashCode normalerweise erreicht.

Alles soweit klar. Aber muss ich dann nicht n Hashcodes vergleichen ?

 

[Flown]

Darum ist auch die Einfügekomplexität für n Elemente O(n * 1) => O(n).

 

[JStein52]

Das überzeugt mich alles noch nichts und führt auch nicht zur gewünschten Lösung von O(n+m)

 

[Flown]

Der best-case für eine sortierte Liste, um ein Element zu finden ist O(log n). Das heißt sortiert einfügen hat eine Komplexität von O(n * log n). Daher braucht man Datenstrukturen, die das "besser" oder sagen wir effizienter lösen. Das ist de facto eine Hashimplementierung (HashSet).
Also ein Algorithmus der O(n + m) Komplexität besitzt sieht so aus:

/**
 * Merges two <code>Lists</code> which behave like <code>Sets</code> and forms
 * the union. The result is given in the first provided <code>List</code>.<br>
 * <i>Note</i>: This implementation has a time complexity of
 * <code>O(n + m)</code>.
 * 
 * @param <T>
 *          type of the <code>List</code> elements
 * @param n
 *          the first set of elements and the result container.
 * @param m
 *          the second set of elements.
 */
public static <T> void union(List<T> n, List<T> m) {
  Set<T> seen = new HashSet<>(n);
  for (T t : m) {
    if (seen.add(t)) {
      n.add(t);
    }
  }
}

 

[JStein52]

Sorry wenn ich da drauf rumreite, aber hier sehe ich erst mal nur dass das im Kommentar steht. Und im Code dazu erkenne ich erst mal O(m) ... aber was tut seen.add(t)) ? Mir fehlt die schlüssige Erklärung des Algorithmus mit dem sich O(n+m) begründen lässt.

 

[Flown]

Das Set wird initialisiert mit den Werten von Liste n, dass funktioniert mit einer Komplexität von O(n). Dann wird über die Liste m iteriert.
Hier passiert folgendes: seen.add(t). Genauer: Ist das Element in dem Set enthalten? Wenn ja dann gibt die Methode false zurück. Wenn nein, dann fügt es das Element dem Set hinzu und gibt true zurück. Was genau passiert bei dem add? Also in der JavaDoku selbst ist beschrieben:

This class offers constant time performance for the basic operations (add, remove, contains and size), assuming the hash function disperses the elements properly among the buckets....

Vom Element wird der hashCode berechnet und auf die Länge des Backing-Array getrimmt. Dann wird geprüft ob in diesem "Bucket" ein Element exisitiert oder nicht. Passiert alles in konstanter Zeit.
Hinzufügen eines Elements in eine Liste (meist) konstant und das jetzt für m Elemente also: O(m).
Beides gemeinsam ist dann: O(n + 1 * m) <=> O(n + m)

 

[JStein52]

Mhmmm, also ich kann mir nicht vorstellen dass diese Erklärung in einer Klausur zu dem Thema durchgehen würde: "das ist so weil im Kommentar zu HashSet steht es ist O(1) ... "

Es muss doch einen Algorithmus geben mit dem man dies erklären kann, unabhängig von Java und irgendwelchen dortigen Kommentaren ?

Genauer: Ist das Element in dem Set enthalten?

Dieser lapifare Satz ist doch der unklare Punkt ! Wie geht das mit O(1)

 

[JStein52]

Es würde gehen wenn man direkt mit dem Hashcode eines Elementes das Element selber addressieren kann und deshalb nur einen einzigen Zugriff braucht. Aber wie ?

 

[mrBrown]

Es würde gehen wenn man direkt mit dem Hashcode eines Elementes das Element selber addressieren kann und deshalb nur einen einzigen Zugriff braucht. Aber wie ?

Passiert doch bei HashSet/HashMap?
Der HashCode wird berechnet, auf die Länge des dahinterliegenden Arrays getrimmt. Passiert in O(1). das dahinterliegende Bucket muss noch durchgegangen werden, ist aber vernachlässigbar (und im Idealfall bei guter Hashfunktion und großen Tabellen auch O(1)).

 

[InfectedBytes]

Das ist eben eine der grundlegenden Eigenschaften von Hashtabellen. Wobei eben dazu gesagt werden muss, dass es sich bei dem O(1) nur um den average case handelt. Der worst case ist O(n).
Mit einer perfekten Hash Funktion könnte man sogar den worst case auf O(1) bringen, was jedoch praktisch nicht so einfach möglich ist.

Es würde gehen wenn man direkt mit dem Hashcode eines Elementes das Element selber addressieren kann und deshalb nur einen einzigen Zugriff braucht. Aber wie ?

Das machen Hashsets ja (mehr oder weniger). Der Grundgedanke ist, das die Hashfunktion aus einem gegeben Objekt den hash berechnet und dieser dann direkt als Index betrachtet werden kann. Im Detail ist das natürlich etwas aufwendiger, da man ja nicht unendlich viel speicher reservieren kann und es je nach Hashfunktion kollisionen geben kann etc.

edit: zu langsam^^

 

[JStein52]

Das machen Hashsets ja (mehr oder weniger). Der Grundgedanke ist, das die Hashfunktion aus einem gegeben Objekt den hash berechnet und dieser dann direkt als Index betrachtet werden kann.

Das ist mir ja alles klar. Meine Frage war ja auch nur wie ? Und wie du ja selbst sagst:

Der worst case ist O(n).

Ich habe ja nur so ein bisschen das Gefühl dass wir hier keinen Algorithmus diskutieren wie der TO das mit O(n+m) schaffen kann sondern dass wir die Komplexität auf HashSet outsourcen und sagen das wird schon so sein. Ich habe mir natürlich auch die JavaDoc zu HashSet angeschaut aber da wird ja auch genau mit den Begriffen hantiert die ihr oben benutzt habt. Für mich wäre das als Antwort in einer Klausur nicht ausreichend aber vielleicht ist der TO ja schon lange zufrieden

 

[InfectedBytes]

kommt eben genauer auf die Frage bzw. den Korrektor an. Man müsste halt wissen ob nach dem worst case oder dem average case gefragt wird

 

[JStein52]

Ja genau. kommt halt auf den ganzen Kontext der Aufgabe an. Der TO hat ja jetzt seine Vereinigungsmethode in Java geschrieben, aber vielleicht geht es ja ganz allgemein um rein akademische Fragen unabhängig von einer Programmiersprache und Java wird nur zur Demonstration des gewählten Algorithmus benutzt ?
@SnrufjStill : vielleicht kannst du uns mehr dazu sagen. Und mich würde hier auch die "gewünschte" Lösung interessieren falls du die mal kriegst.

 

[Flown]

@JStein52 Was verstehst du an dem Hashing/Caching Algorithmus nicht?
Habs doch noch extra hinzugeschrieben:

Vom Element wird der hashCode berechnet und auf die Länge des Backing-Array getrimmt. Dann wird geprüft ob in diesem "Bucket" ein Element exisitiert oder nicht. Passiert alles in konstanter Zeit.

Um das für int Zahlen zu konkretisieren setze doch für hashCode = Eigenwert und für Bucket ein int[] array ein.

 

[JStein52]

Was verstehst du an dem Hashing/Caching Algorithmus nicht

Dann poste doch mal schnell deine Version von der Methode "vereinigung()" für int-Listen ! Aber bitte nicht einfach ein HashSet anlegen. Diese Version habe ich verstanden

 

[Flown]

So war mal auf Mittag... Hier ist eine Implementierung für byte[] mit perfekter Hashfunktion:

public static byte[] union(byte[] n, byte[] m) {
  int newLength = n.length;
  byte[] result = Arrays.copyOf(n, n.length + m.length);

  boolean[] seen = new boolean[1 << Byte.SIZE];

  for (byte b : n) {
    add(seen, b);
  } // <=> new HashSet<>(n);

  for (byte b : m) {
    if (add(seen, b)) { // <=> seen.add(t);
      result[newLength++] = b;
    }
  }
  return Arrays.copyOf(result, newLength);
}

public static boolean add(boolean[] set, byte element) {
  int idx = hash(element);
  if (!set[idx]) {
    return set[idx] = true;
  }
  return false;
}

private static int hash(byte b) {
  return Byte.toUnsignedInt(b);
}

So funktioniert auch ein HashSet und das ist jetzt wirklich heruntergebrochen auf das Minimum. Alles andere wäre jetzt für mich zu viel Aufwand gewesen.

 

[JStein52]

So ähnlich hatte ich mir das vorhin auch schon mal überlegt. Aber ich habe dann nicht mehr weiter gemacht weil ich nicht mehr so sicher war wie ich das:

boolean[] seen = new boolean[1 << Byte.SIZE];

im allgemeinen Fall dimensioniere. Für byte ist ja noch relativ einfach und einsichtig. Und klar dass das auch mit der verwendeten Hash-Funktion zusammenpassen muss. Und an der Stelle habe ich dann aufgehört.

 

[mrBrown]

im allgemeinen Fall dimensioniere. Für byte ist ja noch relativ einfach und einsichtig. Und klar dass das auch mit der verwendeten Hash-Funktion zusammenpassen muss. Und an der Stelle habe ich dann aufgehört.

Der Weg nur mit Arrays funktioniert nur, wenn die HashFunktion keine Kollisionen ergeben kann, und wenn das der Fall ist, sollte auch die Anzahl der Möglichkeiten bekannt sein. Im Zweifel sind's dann halt 1l << Integer.SIZE

 

[Tobse]

Mir gehts ein bisschen so wie @JStein52: Einen eigenständigen Algorithmuss würde ich auch gerne sehen.

Der Weg nur mit Arrays funktioniert nur, wenn die HashFunktion keine Kollisionen ergeben kann, und wenn das der Fall ist, sollte auch die Anzahl der Möglichkeiten bekannt sein. Im Zweifel sind's dann halt 1l << Integer.SIZE

In der Theorie erreicht man damit konstante Zeit. In der Praxis kann man aber nicht 2GB Arbeitsspeicher für jede HashMap reservieren - womit der Worst-Case für contains() wieder O(n) ist.
Deshalb bin ich der Meinung, dass - wie bereits gesagt wurde - die Frage gar nicht den Worst-Case meinen kann. Aber bis zu einer Aufklärung vom TE ist das eh pure Spekulation.

 

[klauskarambulut]

Bei einem Merge Sort hat man gegen Ende auch zwei sortierte Listen die zu einer sortierten Liste vereinigt werden.
Dieser Schritt hat dann O(m+n).
Wenn die Hashfunktion bijektiv ist, dann sind die Liste, das Set auch in O(1) sortierbar, womit man dann beim Mergesort ist.

 

[Tobse]

Bei einem Merge Sort hat man gegen Ende auch zwei sortierte Listen die zu einer sortierten Liste vereinigt werden.
Dieser Schritt hat dann O(m+n).

Aber nur deshalb, weil es Dubletten geben darf; ergo müssen sie nicht herausgefiltert werden. Da ist O(m+n) einfach

 

[Meniskusschaden]

Wenn die Hashfunktion bijektiv ist, dann sind die Liste, das Set auch in O(1) sortierbar, womit man dann beim Mergesort ist.

Davon habe ich noch nie etwas gehört und kann mir das gerade auch überhaupt nicht vorstellen. Hast du nähere Infos dazu, wie man das macht? Ehrlich gesagt bezweifle ich, dass es funktioniert.

Aber nur deshalb, weil es Dubletten geben darf; ergo müssen sie nicht herausgefiltert werden. Da ist O(m+n) einfach

Der Merge-Schritt funktioniert auch mit Dubletten einfach in O(m+n).

 

[Flown]

Ich weiß echt nicht was hier noch das Problem ist. Algorithmen werden meist im average case angegeben. Wie sollte man sonst einen Algorithmus schreiben können mit O(n + m) für Setoperationen. Wenn jemand diesen im worst case liefern kann dann immer her damit.

 

[Tobse]

Ich weiß echt nicht was hier noch das Problem ist. Algorithmen werden meist im average case angegeben. Wie sollte man sonst einen Algorithmus schreiben können mit O(n + m) für Setoperationen. Wenn jemand diesen im worst case liefern kann dann immer her damit.

Das wollte ich im Prinzip auch sagen.

 

[JStein52]

Wenn jemand diesen im worst case liefern kann dann immer her damit

Vielleicht kann uns der TE ja irgendwann eine Musterlösung geben