Seite 1 von 2
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 14:29
von Dauerbaustelle
Versuch das mal ohne `.insert`, weil das ganz unterirdische Laufzeit hat (siehe gleich). Darii hat doch ganz gute Tipps gegeben.
Zu `insert`: Das hat eine Laufzeit von O(n) (n = Anzahl der Elemente in der Liste), heißt, dass die Dauer einer `insert`-Operation proportional zur Anzahl der Elemente ansteigt.
Hierzu eine kurze Erklärung wie `insert` funktioniert: Ist die Liste zum Beispiel [3, 5, 7] und du fügst etwas am Anfang ein, dann wird die Liste im Speicher zuerst um eines vergrößert und dann werden alle Elemente eins nach hinten verschoben. Danach wird das neue Elemente dann eingefügt. Könnte man sich etwa so vorstellen:
Code: Alles auswählen
[3, 5, 7]
Vergrößern:
[3, 5, 7, leer]
Verschieben:
[3, 5, leer, 7]
[3, leer, 5, 7]
[leer, 3, 5, 7]
Einfügen:
[11, 3, 5, 7]
Wie man sieht braucht das Verschieben so viele Schritte wie Elemente in der Liste (hier 3), "läuft" also in Zeit "n" ab. In O-Notation: O(n)
Bei kleinen Listen macht das noch nicht wirklich was aus, wenn deine Liste jetzt aber 1.000 oder 100.000 Einträge hat wird jede Insert-Operation inakzeptabel langsam.
Jetzt zu ms4py `reverse`-Implementation mit `insert` am Beispiel von`reverse([1, 2, 3, 4, 5])`:
Code: Alles auswählen
reversed = [] # mit einer leeren Ergebnisliste beginnend
jetzt geht man von hinten nach vorn die umzudrehende Liste durch:
reversed.insert(0, 5) kostet 0 Zeit
reversed.insert(0, 4) kostet 1 Zeit
reversed.insert(0, 3) kostet 2 Zeit
reversed.insert(0, 2) kostet 3 Zeit
reversed.insert(0, 1) kostet 4 Zeit
Wäre die Liste n lang, bräuchte man 0 + 1 + 2 + ... + n-1 Zeit. Für 10 Elemente bräuchte man dann 45 Zeit, für 100 schon 4950 und für 1000 499500 und das geht so weiter. (Mag mal jemand ne Regressionsfunktion erstellen? :-)
Bessere wäre eine Laufzeit von O(n), wo das umdrehen also immer nur so lange dauert wie Elemente in der Liste und die Dauer nicht wie hier exponentiell steigt.
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 16:40
von mutetella
BlackJack hat geschrieben:Bei 100 Elementen sind das knapp 5000 Aktionen, ...
Warum? Was beweist sum() in diesem Zusammenhang. Geht es hier nicht vielmehr um len()?
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 16:43
von cofi
Der Post an sich beweist nichts, sondern rechnet nur. Dauerbaustelle's 2. Code Block zeigt _was_ gerechnet wird.[1] Und das faellt eben mit `sum(range(n))` zusammen.
[1] Und zwar die kosten beim Einfügen von `n` Elementen.
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 17:14
von EyDu
Dauerbaustelle hat geschrieben:Bessere wäre eine Laufzeit von O(n), wo das umdrehen also immer nur so lange dauert wie Elemente in der Liste und die Dauer nicht wie hier exponentiell steigt.
Bei mir ist n*(n+1)/2 immer noch quadratisch
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 19:32
von mutetella
Und was geschieht bei [0] + [1, 2, 3]?
Dasselbe wie bei [1, 2, 3].insert(0, 0)?
Oder werden beim 1. Beispiel lediglich 2 Speicherbereiche miteinander verbunden, falls so etwas überhaupt geht...
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 19:52
von BlackJack
@mutetella: Bei ``+`` wird eine neue Liste erzeugt und die Elemente von beiden Listen werden dort hinein kopiert.
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 20:13
von mutetella
Ok... wenn ich das also richtig verstehe ist demnach eine Listenaddition bei weitem nicht so rechenintensiv wie das Einfügen eines Elements innerhalb einer Liste.
Warum arbeitet dann die insert()-Methode nicht von vornherein so:
Code: Alles auswählen
[2, 3, 4].insert(0, 1) <==> [1] + [2, 3, 4]
[1, 2, 4].insert(2, 3) <==> [1, 2, 4][0:2] + [3] + [1, 2, 4][2:]
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 20:39
von cofi
Weil eine _neue_ Liste erzeugt wird und damit mehr Speicher benoetigt wird. Vorallem aendert sich die Semantik: `insert` arbeitet in-place, damit hat man bei einer neuen Liste dann doch erhebliche Probleme.
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 21:20
von Dauerbaustelle
Mutella: Du musst aber auch bei der Listenaddition alle Elemente kopieren. Ich vermute mal, dass dabei mehrere Elemente auf einmal kopiert werden, weil das schneller geht als jedes Element einzeln zu behandeln. Diese Optimierung kann aber auch bei `insert` gemacht werden.
Re: Übungen zu Datentypen
Verfasst: Mittwoch 16. März 2011, 23:01
von ms4py
So
Code: Alles auswählen
from collections import deque
test = ["test1", "test2", "test3", "test4"]
temp = deque()
for item in test:
temp.appendleft(item)
print list(temp)
#> ['test4', 'test3', 'test2', 'test1']
Re: Übungen zu Datentypen
Verfasst: Donnerstag 17. März 2011, 00:13
von BlackJack
@mutetella: Das hast Du falsch verstanden. `insert()` kann sogar weniger rechenintensiv sein als Listenkonkatenation. Beim ``+`` werden grundsätzlich alle beteiligten Elemente angefasst -- bei `insert()` kommt man in der Regel mit denen nach dem Einfügepunkt aus. Und dann gibt es halt noch den Punkt mit der unterschiedlichen Semantik, der ja schon angesprochen wurde.
Re: Übungen zu Datentypen
Verfasst: Donnerstag 17. März 2011, 00:21
von derdon
Ganz offensichtlich ist ja wohl der Weg:
Code: Alles auswählen
>>> from collections import deque
>>> test = ["test1", "test2", "test3", "test4"]
>>> d = deque(test[-test.index(x)] for x in test)
>>> d.rotate(-1)
>>> list(d)
['test4', 'test3', 'test2', 'test1']
Edit: mindestens genauso sinnlos ist das hier:
Code: Alles auswählen
>>> from collections import deque
>>> test = ["test1", "test2", "test3", "test4"]
>>> d = deque(test[-test.index(x)+1] for x in test)
>>> d.rotate(2)
>>> list(d)
['test4', 'test3', 'test2', 'test1']
Edit2: ohne Worte
Code: Alles auswählen
>>> from collections import deque
>>> from itertools import tee, izip, chain
>>> test = ["test1", "test2", "test3", "test4"]
>>> def pairwise(iterable):
... a, b = tee(iterable)
... next(b, None)
... return izip(a, b)
...
>>> def reverse_pair(pair):
... a, b = pair
... return b, a
...
>>> d = deque(map(reverse_pair, pairwise(test)))
>>> d.rotate(1)
>>> l = list(d)
>>> list(chain.from_iterable(l[:len(test)/2]))
['test4', 'test3', 'test2', 'test1']
Re: Übungen zu Datentypen
Verfasst: Donnerstag 17. März 2011, 09:15
von Dauerbaustelle
Genius! :-D derdon, was haben die so für Laufzeiten?
Re: Übungen zu Datentypen
Verfasst: Donnerstag 17. März 2011, 14:42
von derdon
ka, das kann uns bestimmt BlackJack verraten
Edit: Habe dich falsch verstanden. Ich dachte, du wolltest die O-Notation haben. Laufzeit wird gleich nachgereicht.
Re: Übungen zu Datentypen
Verfasst: Donnerstag 17. März 2011, 15:42
von derdon
So, hier sind die Zeiten:
http://paste.pocoo.org/show/355071/
Das Py-Skript, das ich dafür verwendet habe:
http://paste.pocoo.org/show/355098/
Re: Übungen zu Datentypen
Verfasst: Donnerstag 17. März 2011, 16:17
von BlackJack
Vielleicht sollte man sich vor der Laufzeit, ob nun absolut oder in O-Notation, ersteinmal Gedanken um die Korrektheit machen:
Code: Alles auswählen
In [713]: test = ['t1', 't2', 't3', 't4', 't1']
In [714]: d = deque(test[-test.index(x)] for x in test)
In [715]: d.rotate(-1)
In [716]: list(d)
Out[716]: ['t1', 't4', 't3', 't1', 't1']
Der zweite auf `index()` basierende Ansatz hat das gleiche Problem.
Und auch der dritte Ansatz liefert nicht das richtige Ergebnis:
Code: Alles auswählen
In [727]: list(chain.from_iterable(l[:len(test)/2]))
Out[727]: ['t1', 't2', 't2', 't1', 't3', 't2']
In [728]: test
Out[728]: ['t1', 't2', 't3', 't4', 't2', 't1']
Re: Übungen zu Datentypen
Verfasst: Donnerstag 17. März 2011, 17:08
von Dauerbaustelle
Nene ich meinte schon die Komplexität.