Warum ist Pythons Deque.Reverse () so langsam? ⇐ Python

[Anonymous]

Betrachten Sie die CPython -Implementierung eines Deque, es scheint, dass Reverse () als O (n) -Zeit sein wird. Es scheint in der Praxis genauso langsam zu sein: < /p>
from collections import deque
import time
n = 100000
l = [i for i in range(n)]
d = deque(l)

start = time.time()
for _ in range(n):
l.reverse()
print("list reversal", time.time() - start)
start = time.time()
for _ in range(n):
d.reverse()
print("deque reversal", time.time() - start)
< /code>
gibt eine Ausgabe von: < /p>
list reversal 3.3866615295410156
deque reversal 4.0808796882629395
< /code>
Meine Frage ist, warum ist es nicht o (1)? Könnten Sie eine doppelt verknüpfte Liste nicht umkehren, indem Sie einen Booleschen festlegen, um zu bestimmen, welche Seite der Kopf berücksichtigt? Gibt es einen Grund, warum es den Standort jedes Artikels im Speicher austauschen muss?