私のLinkedListでは、head_pop（）とappend（）の時間が同じですか？

Question

LinkListの終わりに要素を追加するよりも速くLinkListのhead要素を削除するかどうかをテストします。

これは私のLINKLISTのメインのコードです：

その後、

class LNode: 
    def __init__(self,elem,next_=None): 
     self.elem=elem 
     self.next=next_ 

class LinkList: 
    def __init__(self): 
     self.__head=None 

    #delete head element 
    def head_pop(self): 
     if self.__head is None: 
      raise LinkedListUnderflow("in pop") 
     e=self.__head.elem 
     self.__head=self.__head.next 
     return e 

    #add an element at end 
    def append(self,elem): 
     if self.__head is None: 
      self.__head=LNode(elem) 
      return 
     p=self.__head 
     while p.next is not None: 
      p=p.next 
     p.next=LNode(elem) 

import time 

#test time 
def timetest(f): 
    start=time.clock() 
    for a in range(0,1000000): 
     f 
    end=time.clock() 
    print("times:"+str(end-start)) 

、私はこれを試してみてください。

llist=LinkList() 

def append(): 
    llist.append(666) 

def head_pop(): 
    llist.head_pop() 

timetest(append()) 
timetest(head_pop()) 

出力：

times:0.029582597002445254 
times:0.03032071299821837 

あなたが見ることができるように、彼らは同じ時間を要しました。

しかし、私はそれがO（n）：O（1）であるべきだと思います。

Answer 1

append()の結果を時間テスト関数に渡していますが、関数自体を渡す必要があります。テストにこれを使用すると

def timetest(f): 
    start=time.clock() 
    for a in range(0,1000000): 
     f() # <- note the() here 
    end=time.clock() 
    print("times:"+str(end-start)) 

：

は f関数を呼び出すためにあなたの時間のテストを変更

timetest(append) 
timetest(head_pop) 

あなたが見ることができるように、我々はテストのための機能を渡しています関数の結果（一度呼び出されています！）の代わりに呼び出すことができます。