programmierung.in python

[mutetella]

@guy12
Ich gehe davon aus, dass `splitline` die Liste ist, deren Duplikate Du entfernen möchtest. Wenn dem so ist, dann übergibst Du `splitline` an eine der Funktionen, über die wir in diesem Thread (wenngleich auch etwas offtopic) bisher geschrieben haben. Die schnellste wäre da wohl BlackJacks Lösung.

mutetella

[snafu]

Ok, ich glaub' ich hab's geschnallt: Das Problem war nicht, dass jeder Test dieselbe Liste abarbeitete, sondern dass durch die einfache Multiplikation der Eingangsliste letztlich die Ergebnisliste doch dieselbe blieb und dadurch die Listenlösung niemals in den Bereich vordrang, ab dem sie ihren Vorteil gegenüber der Setlösung verlor. Kann man das so sagen?

Es ist so: Wenn du eine Liste von fünf Elementen einfach hundertmal duplizierst und dann ein ``elem in mylist`` anwendest, dann dauert die lineare Suche nach dem gewünschten Element ja maximal solange, wie für das Durchlaufen der Liste bis zum fünften Element benötigt wird. Das liegt daran, dass das Suchverhalten in Listen so programmiert wurde, dass nach Auffinden des ersten Treffers sinnigerweise nicht mehr weitergesucht wird, sondern direkt das Ergebnis ausgespuckt wird. Das heißt: Die restlichen 95, 950, 9500, wieviel-auch-immer Elemente werden niemals angefasst, wenn du deine Testfälle stumpf mittels Duplikation erzeugst. Viel interessanter ist es doch, wenn das gewünschte Element an einer völlig zufälligen Position innerhalb der Liste auftaucht - im Worst Case erst an der allerletzten Position in der Liste oder wenn es dort überhaupt nicht vorhanden ist (also noch nicht gesehen wurde). Und dann kann man das vergleichen mit der Suchdauer einem Set. Dort gibt es nämlich per Definition keine Positionen (Vgl. Mengenlehre) und alle Elemente werden (in der Theorie) gleich schnell rausgesucht. Ein Set mit 100 Elementen braucht zum Finden eines Treffers genau so lange wie ein Set mit 1 Mio Elementen braucht. Genau das ist die Idee hinter einem Set und diese Idee sollte auch auf deine Testfälle abgebildet werden.

[jerch]

Ok, ich glaub' ich hab's geschnallt: Das Problem war nicht, dass jeder Test dieselbe Liste abarbeitete, sondern dass durch die einfache Multiplikation der Eingangsliste letztlich die Ergebnisliste doch dieselbe blieb und dadurch die Listenlösung niemals in den Bereich vordrang, ab dem sie ihren Vorteil gegenüber der Setlösung verlor. Kann man das so sagen?

Im Prinzip ja. Kritische Operation ist das Suchen in der Ergebnisdatenstruktur, um Dubletten zu vermeiden. Die Einfügeoperation ist auch wichtig, da sie aber "gefiltert" abläuft, ist deren Einfluß abhängig von den Dubletten in den Ausgangswerten.

Zu den Laufzeiten der Basisoperationen der Pythondatenstrukturen gibt es hier eine Auflistung: https://wiki.python.org/moin/TimeComplexity

[Hyperion]

Man sollte dazu natürlich bei allen verschiedenen Varianten *dieselbe* Testdatenstruktur verwenden
(Klar geht es auch mit unterschiedlichen Ausgangssituationen und hinreichend großer Anzahl an Durchläufen - einfacher ist jedoch ersteres)

Zu den Laufzeiten der Basisoperationen der Pythondatenstrukturen gibt es hier eine Auflistung: https://wiki.python.org/moin/TimeComplexity

Schade eigentlich, dass das nicht *direkt* in der Doku zu den Datentypen steht! Oder habe ich das bisher übersehen?

[snafu]

@mutetella: Man kann Zeitmessungen auch relativ elegant in der IPython-Shell durchführen:

Code: Alles auswählen

In [1]: import random

In [2]: DATA = ['D{:02}'.format(random.randrange(100)) for _ in xrange(10000)]

In [3]: def unique_with_list(elems):
   ...:     result = []
   ...:     for elem in elems:
   ...:         if not elem in result:
   ...:             result.append(elem)
   ...:     return result
   ...: 

In [4]: timeit unique_with_list(DATA)
10 loops, best of 3: 20.9 ms per loop

In [5]: def unique_with_set(elems):
   ...:     result = []
   ...:     seen = set()
   ...:     for elem in elems:
   ...:         if not elem in seen:
   ...:             seen.add(elem)
   ...:             result.append(elem)
   ...:     return result
   ...: 

In [6]: timeit unique_with_set(DATA)
1000 loops, best of 3: 1.27 ms per loop

In [7]: from itertools import ifilterfalse

In [8]: def unique_with_ifilterfalse(elems):
   ...:     result = []
   ...:     seen = set()
   ...:     have_seen = seen.__contains__
   ...:     for elem in ifilterfalse(have_seen, elems):
   ...:         seen.add(elem)
   ...:         result.append(elem)
   ...:     return result
   ...: 

In [9]: timeit unique_with_ifilterfalse(DATA)
1000 loops, best of 3: 1.42 ms per loop

Ich habe jetzt mal Testdaten genommen, wo die Wahrscheinlichkeit für Duplikate schön hoch ist. Letztlich haben wir aber sowieso keine Ahnung, wie die tatsächlichen Daten beschaffen sind und wieviele es sind. An sich spielt das aber auch keine wesentliche Rolle, da es hier in der Diskussion ja mehr um das Prinzip von Sets ging und weniger um die konkreten Auswirkungen auf die vorliegenden Daten. Die Essenz sollte halt lediglich sein, dass ein Set ein potenziell besserer Kandidat für das Sammeln von Duplikaten ist als eine Liste. Aber das ist dir ja inzwischen wohl schon klar geworden.

Übrigens, die ``ifilterfalse``-Variante gewinnt nichtmal bei extrem vielen Duplikaten:

Code: Alles auswählen

In [13]: DATA = ['D{:02}'.format(random.randrange(3)) for _ in xrange(10000)]

In [14]: timeit unique_with_set(DATA)
1000 loops, best of 3: 1.21 ms per loop

In [15]: timeit unique_with_ifilterfalse(DATA)
1000 loops, best of 3: 1.37 ms per loop

Das Ziel dieser Idee wurde also völlig verfehlt. Aber so weiß man es wenigstens, bevor man sich auf solch kryptischen Code einlässt im Glauben, damit etwas optimieren zu können.

[mutetella]

Aber das ist dir ja inzwischen wohl schon klar geworden.

Ja, in diesem Thread ist mir tatsächlich so einiges klar geworden... Danke dafür und danke für den IPython-Tipp!!

mutetella