Warum hat Python keine native Implementierung einer verknüpften Liste?

Question

Ich habe versucht, ein paar schnelle Experimente zu vergleichen, die die Leistung von nativen Python-Listen mit Implementierungen von verketteten Listen wie this vergleichen.

Die nativen Python-Listen sind immer schneller als die nicht native verknüpfte Liste in den Fällen, in denen sie nicht sein sollten (nach der Theorie).

from linkedlist import * 
import time 
a = LinkedList() 
b = [] 
for i in range(1000000): 
    b.append(i) 
    a.add_first(i) 
t0 = time.clock() 
a.remove(10) 
t1 = time.clock() 
b.remove(10) 
t2 = time.clock() 
print t1-t0 
print t2-t1 

Die Ergebnisse, die ich auf dem Test oben haben, sind:

• nativen verknüpften Liste = 2.00000000001e-05

• python list = 0,005576

• nicht nativer verkettete Liste = 3.90000000001d-05

Also habe ich mich gefragt, warum Python keine native Linked List Datenstruktur hat. Im Fall von Python sieht es für mich aus, dass es algorithmisch sinnvoll sein könnte, anstelle der Standardlisten die Verknüpfungsliste zu verwenden, um einige Aspekte der Standardbibliothek zu beschleunigen.

Mein Verständnis ist, dass die List-Datenstruktur ein Schlüsselbaustein der Sprache ist und dass sie den Code wartbarer und leicht zu optimieren macht, um sich auf genau diese Datenstruktur zu konzentrieren.

Gibt es noch einen anderen Grund?

Answer 1

Python hat collections.deque, die eine native doppelt verkettete Liste ist.

Answer 2

Es ist nur weil Bau Liste dauert die meiste Zeit, anstatt Append-Methode. Wenn es sich also nicht um eine lineare Zeitoperation handelt, wie Sie gezeigt haben, ist die Methode append wichtiger als die Erstellung, die zu dem Ergebnis führt, das Sie sehen möchten.