Seite 2 von 2

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']
:P

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.