経過時間に基づいてリストサイズを増やす

Question

さまざまなソートアルゴリズム（選択、バブル、マージ、ツリーソート）の実行時間を測定するプログラムを作成しています。

テストケースに使用されるリストサイズは10,000から始まり、テストの実行時間が60秒を超えるまでテストごとに10,000ずつ増加する必要があります。

これが私の問題です。

私はこれがおそらく非常に間違った（そして醜い）コードを作りました（私は現在バブルソートだけでテストしています）。

import random 
import time 

def bubbleSort(a_list): 
    for passnum in range(len(a_list)-1,0,-1): 
     for i in range(passnum): 
      if a_list[i]>a_list[i+1]: 
       temp = a_list[i] 
       a_list[i] = a_list[i+1] 
       a_list[i+1] = temp 

a_list = [] 
for i in range(10000): 
    a_list.append(random.randrange(0,10000)) 

start = time.perf_counter()  
bubbleSort(a_list) 
end = time.perf_counter() 

elapsed = end - start 
print("{0:.8f}".format(elapsed, "\n"))  
print(a_list) 

if elapsed <= 60: 
    for i in range(len(a_list), len(a_list)+10000): 
     a_list.append(random.randrange(len(a_list)+10000)) 

     start = time.perf_counter()  
     bubbleSort(a_list) 
     end = time.perf_counter() 

     elapsed = end - start 
     print("{0:.8f}".format(elapsed, "\n"))  
     print(a_list) 
else: 
    #it'll quit   

非常に明白な無知には申し訳ありません。
これは私の最初の反応でした。それから私はこのループを思い付いた：

start = time.perf_counter() 
while start <= 60: 
    for i in range(len(a_list)+10000): 
     a_list.append(random.randrange(len(a_list)+10000))  
     bubbleSort(a_list) 

end = time.perf_counter() 

elapsed = end - start 
print("{0:.8f}".format(elapsed, "\n"))  
print(a_list) 

誰かが私に正しい方向にプッシュを与え、私はその背後にあるロジックを考えるのを助けることができる場合、私は非常に感謝されます。あらかじめありがとうございます。

Answer 1

まず、読みやすさを改善するために、コードの一部を折りたたむ：

• 要素は現在、Pythonのイディオムa, b = b, a
• は、リストのサイズをパラメータループ
• 、理解してリストをいないビルドの使用に切り替えます。ループのたびに増加します。
• 実際にはに実行時間は小数点8桁が必要ですか？

コード：

import random 
import time 

def bubbleSort(a_list): 
    for passnum in range(len(a_list)-1,0,-1): 
     for i in range(passnum): 
      if a_list[i] > a_list[i+1]: 
       a_list[i], a_list[i+1] = a_list[i+1], a_list[i] 

elapsed = 0 
size = 0 
size_inc = 10000 

print("Size\tTime") 
while elapsed < 60: 
    # Add 10,000 numbers to the list 
    size += size_inc 
    a_list = [random.randrange(0,size) for i in range(size)] 

    start = time.perf_counter()  
    bubbleSort(a_list) 
    end = time.perf_counter() 
    elapsed = end - start 

    print(size, "\t{0:.8f}".format(elapsed, "sec.\n")) 

出力：

Size Time 
10000 12.05934826 
20000 47.99201040 
30000 111.39582218