導致這兩種插入排序實現之間性能差異的原因是什麼？

我有兩個插入排序的實現。首先是幾乎在我的Java教科書的例子的轉錄（儘管有while循環，而不是Java的for環）導致這兩種插入排序實現之間性能差異的原因是什麼？

def insertion_sort(array): 
    for i in range(1,len(array)): 
     j = i 
     while j > 0 and array[j] < array[j-1]: 
      array[j],array[j-1] = array[j-1], array[j] 
      j=j-1 
    return array

第二似乎是一個更Python實現。

def insertion_sort2(array): 
    for i in range(1,len(array)): 
     for j in range(i-1,-1,-1): 
      if array[j+1] < array[j]: 
       array[j+1],array[j] = array[j],array[j+1] 
      else: 
       break 
    return array

計時後，似乎第二個慢得多（3到4倍慢），當列表已經排序或非常接近排序。然而，隨着倒數的增加，第二次執行似乎佔上風（更快10-15％）。我只是想知道是否有人能夠解釋這種差異的原因可能是什麼。謝謝！

編輯：這是我用來創建一個隨機列表的函數。

def rand_list(length): 
    return [random.randint(0,9*length) for _ in range(length)]

當我想要一個部分排序的列表時，我只需撥打list(range(length1)) + rand_list(length2)。

至於他們需要多長時間運行我已經使用%timeit工具和兩個datetime.now()調用之間的差異。他們都給出了非常一致的結果。此外，我只想強調，我每次都創建一個新列表，而不是對已排序的列表進行排序。

來源

2016-11-20 CopOnTheRun

它是Python 2還是3？如果Python 2嘗試xrange，範圍將預先分配Python2中的列表，而在Python3中，它會返回一個迭代器。 – totoro

Python 3，特別是3.5.2。我更新了標籤以反映這一點！ – CopOnTheRun

@totoro問題不在於如何讓這個更快，它是*解釋差異* –

我能夠重現您的時間。對於隨機數據或反向排序數據，insert_sort2比Python3.6上的插入點數快一點。但是，如您所述，對於已排序的數據，insert_sort2的速度要慢三倍。

其原因第一種情況（稍快於隨機或排序數據）是range_iterator對象產生降低整數更快（內部使用C-代碼）比手動編寫j=j-1和j > 0這兩者都是純Python步驟。因此，一旦for循環被加熱，它的運行速度要比while循環等效。

第二種情況（排序數據慢得多）的原因是while循環比零循環時等價的for循環便宜。這是因爲while循環沒有安裝成本。等價的for-loop仍然必須先創建一個範圍對象和一個range_iterator對象，然後才能找出沒有迭代的對象。因此，while循環在空或接近空時擊敗for-loop，因爲它們避免了建立成本。

來源

2017-03-25 01:46:06

導致這兩種插入排序實現之間性能差異的原因是什麼？

回答

相關問題