Array#sort在Ruby语言中是怎么这么快的？

Question

C#有BitArray，C有bit字段。我在Ruby内核中找不到对应的东西。谷歌向我展示了Peter Cooper为同样的目的编写的一个BitField类。

我一直在阅读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的默认排序比10M位向量上的1M BitField.set +1循环快22倍？在Ruby中有没有更有效的位域/数组？Ruby的默认排序是如何实现这种级别的性能的。它是不是跳到C来完成这件事？

Answer 1

Array#sort是用C实现的，请参见array.c中的rb_ary_sort

它还具有一些比较Fixnums的检查，因此对整数数组进行排序甚至不需要方法查找。

Answer 2

的默认排序是如何实现这种性能水平的..它是不是跳到C来完成这件事？

ruby默认实现中的所有核心类和方法都是用C实现的。

Answer 3

其速度如此之快的原因可能是因为它是在ruby实现中用C实现的。