Array如何在Ruby中排序如此之快？

C＃有BitArray，C有位字段..我在Ruby內核中找不到等價物。 Google向我展示了Peter Cooper爲此寫的一個BitField課程。Array如何在Ruby中排序如此之快？

我一直在閱讀Jon Bentley的Programming Pearls，並嘗試使用BitMap排序的第一個示例 - 我需要一個類型爲位數組的類型。我用彼得的類

class BitMapSort 
    def self.sort(list, value_range_max) 
    bitmap = BitField.new(value_range_max) 

    list.each{|x| bitmap[x] = 1 } 

    sorted_list = [] 
    0.upto(value_range_max-1){ |number| 
     sorted_list << number if (bitmap[number] == 1) 
    } 
    sorted_list 
    end 
end

的範圍在[0，10,000,000）一套1M唯一編號的運行此，產生了一些有趣的結果，

      user  system  total  real 
bitmap    11.078000 0.015000 11.093000 (11.156250) 
ruby-system-sort  0.531000 0.000000 0.531000 ( 0.531250) 
quick-sort   21.562000 0.000000 21.562000 (21.625000) 

Benchmark.bm(20){|x| 
    x.report("bitmap"){ ret = BitMapSort.sort(series, 10_000_000);} 
    x.report("ruby-system-sort"){ ret = series.sort; } 
    x.report("quick-sort"){ ret = QuickSort.sort(series, 0, series.length-1); } 
    }

如何是Ruby的默認排序22X超過1M快BitField.set + 1在10M位向量上循環？ Ruby中有更高效的位域/數組嗎？ Ruby的默認排序如何達到這個級別的性能。它是否跳入C來完成這個任務？

來源

2009-08-27 Gishu

Array#sort是用C語言實現，見rb_ary_sort在array.c

它也有一些檢查，以比較Fixnums如此排序的整數數組甚至不需要方法查找。

來源

2009-08-27 18:35:54 levinalex

問題：如果我想編寫BitMapSort（因爲它對於輸入列表更合適 - 這是來自受限範圍的唯一編號），它比Array＃排序更好，這是我唯一的選擇，它用C編寫代碼？我在純C＃中重複了這個練習，BitMapSort在那裏勝過了Array.Sort。如果我從[0,2M）範圍內選擇1M個數而不是[0,10M），則它將時間縮短一半。有趣的.. – Gishu 2009-08-28 07:03:30

最主要的是方法調用開銷。在ruby 1.8中進行方法調用非常緩慢並且根本沒有被緩存。 – levinalex 2009-08-28 10:46:59