python中的時間分析

Question

import math 
import time 
import random 


def sequential_search(key,sorted_list): 
    for element in sorted_list: 
     if element==key: 
      return True 
     else : 
      return False 


def binary_search(key,sorted_list): 
    l=0 
    r=len(sorted_list)-1 
    while l<=r: 
     m=int(math.floor((l+r)/2)) 
     if key==sorted_list[m]: 
      return m 
     elif key<sorted_list[m]: 
      r=m-1 
     else: 
      l=m+1 


def ternary_search(key,sorted_list): 
    length = len(sorted_list) 
    left = 0 
    right = length 
    index = 0 
    x = True 
    while x and left <= right: 
    #focal = (high + low) //3 
     if left == right: 
       #check similarity between values and key 
       return left 

     elif right - left > 0: 
       index1 = ((right+2*(left))//3) 
       index2 = ((2*(right)+left)//3) 
       if sorted_list[index1] == key: 
         return index1 
       elif sorted_list[index2] == key: 
         return index2 
       else: 
         if key<sorted_list[index1]: 
             right = index1 - 1 
         elif key > sorted_list[index1] and key <sorted_list[index2]: 
             right = index2 - 1 
             left = index1 - 1 
         elif key > sorted_list[index2]: 
             left = index2+1 
    return index 
def interpolation_search(key, sorted_list): 
    low = 0 
    high = len(sorted_list) - 1 

    while sorted_list[low] <= key and sorted_list[high] >= key: 
     mid = low + ((key - sorted_list[low]) * (high - low)) \ 
      /(sorted_list[high] - sorted_list[low]) 
       # out of range is possible 

     if sorted_list[mid] < key: 
      low = mid + 1 
     elif sorted_list[mid] < key: 
      high = mid - 1 
     else: 
      return mid 

    if sorted_list[low] == key: 
     return low 
    return None 

def run_experiment(): 
    sorted_list=random.sample(range(1000000), 1000) 
    sorted_list.sort() 
    key=random.randint(0,1000001) 
    key=1000001 
    time_ss=time.time() 
    sequential_search(key,sorted_list) 
    time_ss_end=time.time() 
    print time_ss_end-time_ss 
    time_bs=time.time() 
    binary_search(key,sorted_list) 
    print time.time()-time_bs 
    time_ts=time.time() 
    ternary_search(key,sorted_list) 
    print time.time()-time_ts 
    time_is=time.time() 
    interpolation_search(key,sorted_list) 
    print time.time()-time_is 



if __name__ == '__main__': 
    run_experiment() 
    raw_input("Stop") 

我是Python新手。我想測量這些算法的時間，所以我使用「時間」方法。但輸出如下：

>>> 
0.0 
0.0 
0.0 
0.0 
>>> 

有時第一次測量會發生變化。我怎樣才能改變這些輸出？我應該更改我的代碼以進行時間分析嗎？

Answer 1

你的代碼是太快配置文件的方式（沒準它的速度是罰款）

，如果你真的想速度曲線，它嘗試這種

def run_experiment(): 
    print timeit.timeit("sequential_search(key,sorted_list)", 
         "import random;from main import sequential_search; 
         key=10000001;sorted_list=sorted(random.sample(range(100000),1000))") 

或讓你對測試列表更大......

Answer 2

從我測試的結果來看，腳本運行速度非常快，在同一毫秒內。

您可以關注this answer並將您的時間轉換爲毫秒以獲得更準確的時間。

Answer 3

原因在於從計算機的角度出發的操作非常少，以便找到密鑰並且動作幾乎立即完成（因此零或接近零時間）。

如果你想查詢的不同方法的相對效率，調用各功能很多次的循環，像這樣：

loops = 2000 

    for i in range(loops): 
     sequential_search(key,sorted_list) 

這樣做對各類型的搜索。如果你仍然得到接近於零的結果，只是使循環更大的數字