爲什麼我的插入排序比mergesort更快？

Question

# sort.rb 
class Array 
    def insertion 
    (1..self.count).each do |i| 
     (i..0).each do |j| 
     first = j - 1 
     second = j 
     if self[second] > self[first] 
      swap(second, first) 
     end 
     end 
    end 
    self 
    end 

    def mergesort 
    return self if self.size <= 1 
    mid = self.size/2 
    left = self[0, mid] 
    right = self[mid, self.size-mid] 
    merge_array(left.mergesort, right.mergesort) 
    end 

    # helpers 

    def merge_array(left, right) 
    sorted = [] 
    until left.empty? or right.empty? 
     if left.first <= right.first 
     sorted << left.shift 
     else 
     sorted << right.shift 
     end 
    end 
    sorted.concat(left).concat(right) 
    end 

    def swap(previous, current) 
    copy = self[previous] 
    self[previous] = self[current] 
    self[current] = copy 
    end 
end 

我的RSpec的文件：

require './sort' 

unsorted = 5000.downto(1).to_a.shuffle 

describe Array, "#insertion" do 
    it "sorts using insertion sort" do 
    time = Time.now 
    unsorted.insertion.should eq(unsorted.sort) 
    puts "insertion" 
    puts Time.now - time 
    end 
end 

describe Array, "#merge" do 
    it "sorts using merge sort" do 
    time = Time.now 
    unsorted.mergesort.should eq(unsorted.sort) 
    puts "merge" 
    puts Time.now - time 
    end 
end 

我們知道，插入排序應該比歸併排序慢，因爲插入排序的運行時間平均爲O（n^2），而合併排序是O（n * log（n））。但是，當我運行上面的測試代碼時，合併比插入慢10倍以上。

 
insertion 
0.001294 seconds 

.merge 
0.017322 seconds 

我的猜測是，我使用一些昂貴的計算方法，如shift和concat，但具有相差10倍是太過分了。

如何改進合併排序？

Answer 1

很多事情在這裏：

1. 這不是一個插入排序，這是一個冒泡排序。
2. (i..0).each什麼都不做，因爲範圍不能以相反的順序進行（您的規範無法通過）。改爲使用downto。
3. 邏輯本身是錯誤的，如果你的最後一個索引位於字符串的開頭，那麼當第二個元素小於第一個時，你想交換。
4. 您的規格使用相同的數組，但插入方法會改變數組，所以在進入合併排序時它已經被排序。
5. 把這些放在Array上沒有很好的理由（除了它的新穎之處），一般來說，猴子修補是一種不好的做法（我會解釋爲什麼，但它超出了這個響應的範圍） 。
6. 交換方法可以簡化爲多個分配self[a], self[b] = self[b], self[a]。
7. 名稱first,second,previous,next，都是令人困惑的。他們的名字暗示他們是元素，但他們真的是索引，我會重新命名爲index1（也許first_index，但可能會變得冗長）。
8. 爲什麼要在count和size之間切換？這是令人困惑的，並使它看起來像你複製和粘貼其他人的代碼（以及其中一個函數改變數組而另一個函數不改變的事實，通常，合併排序看起來像是由知道某人的人編寫的他們在做什麼，以及「插入」排序不）。
9. 合併排序可能會比較慢，因爲它會在不需要的地方創建大量的數組（它沒有副作用，但從性能的角度來看，最好是dup數組，然後將其排序）基於開始和結束索引。
10. 測試不是很有用，因爲它們只對一個數組進行排序。假設這個數組已經大部分被排序了，那麼這個冒泡排序必須執行的交換很少，所以它只是遍歷數組並且完成了。
11. 這些調用之間可能會發生環境差異（優化，垃圾收集狀態），最好使用Benchmark庫。它有bmbm它試圖最小化這些差異。
12. 因爲您正在計時器unsorted.insertion.should eq(unsorted.sort)內部運行測試，所以您不僅僅是對排序進行計時，還會計算Ruby的unsorted.sort以及RSpec斷言。將時間代碼中的排序包裹起來然後輸出結果會更好。

Answer 2

思路：因爲插入排序

• 嘗試正在增加你的測試規模在幾十萬和平均的東西在幾個不同的陣列會比你的合併排序
非常快，最好的情況下
• 預分配在合併數組，而不是動態生成的陣列，因爲你應該知道的大小
• 採取的正確性（...應該）召喚出的匹配時間