Inkrementieren der Listengröße basierend auf der verstrichenen Zeit

Question

Ich erstelle ein Programm, das die Ausführungszeiten verschiedener Sortieralgorithmen (Selection, Bubble, Merge und Tree sort) misst.

Die Listengrößen für die Testfälle sollten bei 10.000 beginnen und für jeden Test um 10.000 steigen, bis die Ausführungszeit für den Test 60 Sekunden überschreitet.

Und das ist mein Problem.

Ich habe diesen wahrscheinlich sehr falschen (und hässlichen) Code, den ich erstellt habe (ich teste gerade mit dem Bubble Sort).

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   

Ich bin für die Ignoranz leid, die sehr offensichtlich ist.
Also oben war meine erste Reaktion. Dann kam ich mit dieser Schleife bis:

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) 

Ich wäre sehr dankbar, wenn mir jemand einen Stoß in die richtige Richtung geben kann und mir helfen, denken Sie an die Logik dahinter. Vielen Dank im Voraus.

Answer 1

Zuerst einige der Codes kollabieren die Lesbarkeit zu verbessern:

• Element wechselt jetzt den Python Idiom a, b = b, a
• Erstellen Sie die Liste mit einem Verständnis verwendet, keine Schleife
• parametrisieren der Liste Größe; schrittweise jedes Mal durch die Schleife.
• Haben Sie wirklich benötigen 8 Dezimalstellen für die Ausführungszeit?

Code:

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

Ausgang:

Size Time 
10000 12.05934826 
20000 47.99201040 
30000 111.39582218