Pythonでのキュー実装の違い

Question

exercises（つまり＃6）の1つは、キュー実装のパフォーマンスを比較するように要求しています。それはいくつかの違いがあるように聞こえるので、私はそれを把握しようとしました。ここに私のコードは

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)) 

だとここで私の実験の結果

を反映プロットは、insertとpop(index)はO（n）があることが知られています。興味深いことに、グラフからわかるように、insert(0, item)はpop(0)の2倍の時間がかかります。その観察は私にはなぜ、これが当てはまるのか不思議に思った。表面上、2つの方法は非常によく似ていますが、明らかにボンネットの下には何か面白いことがあります。それで、問題は、あなたが私にそれを理解させる助けになるか？

Answer 1

はCPythonのlist実装で読んでいくつか：http://www.laurentluce.com/posts/python-list-implementation/

は、基本的には、リストは、彼らは任意の時点で必要があるとして、約2倍の量のメモリを持つように設計されているので、彼らは、メモリを再割り当てする必要がなく、わずかに長さを変更することができます。リストがより多くのメモリを必要とする場合、リスト全体を十分なスペースを持つメモリ内の別の場所に移動する必要があることがあります。彼らは縮小すると、リストの最後にメモリを解放するだけです。