Einer der exercises (nämlich # 6) fordert uns auf, die Leistung der Warteschlangenimplementierungen zu vergleichen (mit Kopf in der Anfang/am Ende einer Liste). Das klingt, als könnte es einen Unterschied geben, also habe ich versucht es herauszufinden. Hier ist mein CodeUnterschied zwischen Warteschlangenimplementierungen in Python
import timeit
class QueueStart(object):
'''Queue implementation with head in the beginning of a list'''
def __init__(self):
self.items = []
def enqueue(self, i):
self.items.append(i)
def dequeue(self):
return self.items.pop(0)
def isEmpty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
class QueueEnd(object):
'''Queue implementation with head at the end of a list'''
def __init__(self):
self.items = []
def enqueue(self, item):
self.items.insert(0, item)
def dequeue(self):
return self.items.pop()
def isEmpty(self):
return len(self.items) == 0
def size(self):
return len(self.items)
# store results for further plotting
start_add_list = [] # QueueStart.enqueue(item) runtimes for inputs of different sizes
start_pop_list = [] # the same for QueueStart.dequeue(item)
end_add_list = [] # the same for QueueEnd.enqueue(item)
end_pop_list = [] # the same for QueueEnd.dequeue(item)
for i in range(100000, 500000, 10000):
qs = QueueStart()
qs.items = list(range(i))
qe = QueueEnd()
qe.items = list(range(i))
start_add = timeit.Timer('qs.enqueue(1)', 'from __main__ import qs')
start_pop = timeit.Timer('qs.dequeue()', 'from __main__ import qs')
end_add = timeit.Timer('qe.enqueue(1)', 'from __main__ import qe')
end_pop = timeit.Timer('qe.dequeue()', 'from __main__ import qe')
start_add_list.append(start_add.timeit(number=1000))
start_pop_list.append(start_pop.timeit(number=1000))
end_add_list.append(end_add.timeit(number=1000))
end_pop_list.append(end_pop.timeit(number=1000))
Und hier Plots sind die Ergebnisse meiner Experiment reflektieren 
Es ist bekannt, dass insert und pop(index) sind O (n). Das Interessante ist jedoch, dass wir aus den Graphen sehen, dass insert(0, item) doppelt so lang ist wie pop(0). Diese Beobachtung ließ mich fragen, warum das so ist. An der Oberfläche sehen zwei Methoden sehr ähnlich aus, aber anscheinend ist unter der Haube etwas Interessantes im Gange. Die Frage ist also: Könnten Sie mir helfen, es herauszufinden?
Dies hängt wahrscheinlich von der Implementierung ab, je nachdem, wie die Vorgänge beim Hinzufügen und Löschen des zugrunde liegenden Arrays Speicher verwalten. Zum Beispiel, 'insert (0, ...)' würde ständig alles um einen Slot hochschieben müssen, während 'pop (0)' einfach das Array-Element '[0]' auf Kosten von unbenutztem Speicher ändern könnte an der Vorderseite des Arrays. – chepner
@chepner: Das Buch, aus dem die Übung kommt, sagt: "Wenn Pop am Ende der Liste aufgerufen wird, braucht es O (1), aber wenn Pop für das erste Element in der Liste oder irgendwo in der Mitte aufgerufen wird, ist es O (n) Der Grund dafür liegt darin, wie sich Python für die Implementierung von Listen entscheidet. ** Wenn ein Element von der Vorderseite der Liste übernommen wird, werden in der Python-Implementierung alle anderen Elemente in der Liste um eine Position näher an den Anfang verschoben **. " Wie ich es verstehe, können sowohl "insert (0, ...)" als auch "pop (0)" im ungünstigsten Fall Tonnen von Verschiebungen machen, aber es ist nicht klar, woher der Unterschied durch den konstanten Faktor kommt. –