Übungen zu Datentypen

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