파이썬의 시간 분석

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

키를 찾기 위해 (컴퓨터 관점에서) 거의 작동하지 않기 때문에 작업이 거의 즉시 완료됩니다 (따라서 0 또는 0에 가까움).

당신이 다른 방법의 상대적 효율성을 확인과 같이 루프에서 각 기능에 여러 번 호출 할 경우

loops = 2000 

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

검색의 각 유형에 대해이 작업을 수행합니다. 여전히 0에 가까운 결과를 얻는다면 루프를 더 큰 숫자로 만드십시오.