Schnellste Methode für Liste ohne Duplikate

[DKKA]

Hallo zusammen,

Ich habe eine Frage, was ist die schnellste Methode um eine Liste ohne Duplikate zu erstellen? Angenommen ich will eine Liste mit 100 verschiedenen Wörtern haben, ist es dann besser zuerst möglichst viele Wörter zu generieren und dann die Liste Filtern oder soll ich bei jedem generierten Wort nachschauen, ob das Wort schon in der Liste steht? Und bei der letzteren Variante,wie kann man das möglichst effizient lösen? Gibt es da einen schnelleren Weg als bei jedem neuen String zuerst alle in der Liste vorhandenen Strings zu überprüfen, ob der selbe String schon vorhanden ist oder nicht?

Vom Aufwand wäre das O(n!) oder nicht? Gibt es da eine schnellere Möglichkeit als String zu vergleichen?

[snafu]

Nutze ``set(deine_woerter)``. Dies erzeugt ein Set-Objekt (auf deutsch: Menge), welches definitionsgemäß keine mehrfach vorkommenden Elemente enthält. ``woerter`` kann hier z.B. eine Liste sein oder mittels Generator erzeugt werden. Letzteres ist sowohl effizienter als auch speicherfreundlicher im Gegensatz zu dem Zwischenschritt über eine Liste.

[/me]

Ich habe eine Frage, was ist die schnellste Methode um eine Liste ohne Duplikate zu erstellen?

Ein Set ist eine recht praktische Datenstruktur.

Code: Alles auswählen

>>> data = ['Monty', 'Eric', 'John', 'Monty']
>>> print(set(data))
{'John', 'Eric', 'Monty'}
>>> print(list(set(data)))
['John', 'Eric', 'Monty']

[snafu]

Vom Aufwand wäre das O(n!) oder nicht? Gibt es da eine schnellere Möglichkeit als String zu vergleichen?

Die von dir beschriebene Vorgehensweise schon. Bei einem Set weden hingegen Hashwerte erzeugt und da ist das Hinzufügen eines Elements O(1). Für n Elemente also O(n).

[BlackJack]

@DKKA: Jedes Wort in einer Liste von Worten zu prüfen wäre O(n²) Laufzeit. Verwende statt einer Liste ein `set`. Falls es auf die Reihenfolge ankommt, dann muss man beides verwenden, eine Liste für das Ergebnis und ein `set` um sich zu merken was man schon gesehen hat.

[Hyperion]

Vom Aufwand wäre das O(n!) oder nicht? Gibt es da eine schnellere Möglichkeit als String zu vergleichen?

Nur der Vollständigkeit halber: Nein! Die Komplexität ist dabei ja direkt abhängig von der Erzeugungsfunktion; und je nach Güte der "Duplikatfreiheit" kann diese durchaus auch unendlich sein...

Auch wenn Deine Zielstruktur (m) begrenzt ist (bei Dir ja maximal 100 Wörter) und Du die Anzahl an Durchläufen (n) nicht kennst, so kannst Du imho nur O(n * m) als Komplexität annehmen. Für jedes neue Wort aus "n" musst Du ja schlimmstenfalls "m" Mal die Zielliste abgleichen.

[DKKA]

Vom Aufwand wäre das O(n!) oder nicht? Gibt es da eine schnellere Möglichkeit als String zu vergleichen?

Die von dir beschriebene Vorgehensweise schon. Bei einem Set weden hingegen Hashwerte erzeugt und da ist das Hinzufügen eines Elements O(1). Für n Elemente also O(n).

Vielen Dank für alle Antworten. Wie funktioniert den intern das mit dem Set? Wenn ich ein Element einem Set hinzufüge, ist da dann ein Heap oder AVL-Tree etc. drunter der das ganze überprüft, weil jeden existierenden Hashwert zu überprüfen wäre doch gleich schnell wie das String vergleichen...?

EDIT: Da hab ich die Antwort von Hyperion noch nicht gesehen.

[BlackJack]

@DKKA: Ein `set` verwendet intern eine Hash-Tabelle.

[snafu]

Erklärung zur Funktionsweise einer Hash-Tabelle: http://de.wikipedia.org/wiki/Hashtabell ... lgorithmus