如何快速地将Ruby排序在Ruby中？

Question

C#有BitArray,C有位字段..我在Ruby核心中找不到等价物.谷歌向我展示了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); }
    }

在10M位向量上,ruby的默认排序比1M BitField.set + 1循环快22倍？Ruby中是否有更高效的位字段/数组？Ruby的默认排序如何达到这种性能水平..它是否会跳到C来完成这项工作？

Answer 1

阵列#排序是用C语言实现,看到rb_ary_sort在array.c

它还有一些比较Fixnums的检查,因此排序整数数组甚至不需要方法查找.

Answer 2

Ruby的默认排序如何达到这种性能水平..它是否会跳到C来完成这项工作？

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