Übungen zu Datentypen

[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.

[mutetella]

Bei 100 Elementen sind das knapp 5000 Aktionen, ...

Warum? Was beweist sum() in diesem Zusammenhang. Geht es hier nicht vielmehr um len()?

[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.

[EyDu]

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

[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...

[BlackJack]

@mutetella: Bei ``+`` wird eine neue Liste erzeugt und die Elemente von beiden Listen werden dort hinein kopiert.

[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:]

[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.

[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.

[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']

[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.

[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']

[Dauerbaustelle]

Genius! :-D derdon, was haben die so für Laufzeiten?

[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.

[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/

[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']

[Dauerbaustelle]

Nene ich meinte schon die Komplexität.