c - Ruby的排序是如何实现的？

Question

我很想知道 sort_by 和 sort_by! 是如何实现的。我查看了一些实现代码，但无法解析大量的宏(这反过来又产生了更多的宏)来弄清楚实际发生了什么。

以下是我的基准测试结果:

sort_by -a[:bar]       8.830000   0.010000   8.840000 (  8.847953)
sort_by a[:bar]*-1     8.620000   0.010000   8.630000 (  8.628056)
sort_by(&:bar).reverse!  8.550000   0.000000   8.550000 (  8.558410)

对比:

sort_by! -a[:bar]      2.800000   0.000000   2.800000 (  2.800778)
sort_by! a[:bar]*-1    2.690000   0.000000   2.690000 (  2.692756)
sort_by!(&:bar).reverse!  2.470000   0.010000   2.480000 (  2.480710)

我很想知道为什么会有如此显着的差异。我的一个假设是关于 sort_by 必须执行的内存分配。但这是我的基准测试代码，您可以看到它是我正在排序的数组(即分配可以发生一次，数组大小已知)。

#!/usr/bin/ruby

require 'benchmark'

foo = []
for i in 0..10000
  foo << {:bar => rand(10000)} 
end

Benchmark.bm(20) do |b|
  b.report("sort_by! -a[:bar]") { 1000.times { foo.sort_by!{ |a| -a[:bar] } } }
  b.report("sort_by! a[:bar]*-1") { 1000.times { foo.sort_by!{ |a| a[:bar]*-1 } } }
  b.report("sort_by!(&:bar).reverse!") { 1000.times { foo.sort_by!{ |a| a[:bar] }.reverse! } }
end

Answer 1

您的基准没有反射(reflect)输出，而且它们需要简化。测试时保持简单，只测试您想了解的内容:

require 'benchmark'

BAR = (1..10_000).to_a.shuffle

n = 1000
Benchmark.bmbm(8) do |b|
  b.report("sort_by")  { n.times { foo = BAR.dup; foo = foo.sort_by{ |a| a }; foo } }
  b.report("sort_by!") { n.times { foo = BAR.dup; foo.sort_by!{ |a| a };      foo } }
end

导致:

Rehearsal --------------------------------------------
sort_by    6.350000   0.010000   6.360000 (  6.364429)
sort_by!   6.620000   0.000000   6.620000 (  6.615428)
---------------------------------- total: 12.980000sec

               user     system      total        real
sort_by    6.350000   0.000000   6.350000 (  6.353188)
sort_by!   6.840000   0.010000   6.850000 (  6.842521)

环境可能在您的测试中没有稳定下来，再加上您进行的更改会混淆测试。

重要的是复制所有内容，只有一个不同，以测试您想要了解的内容。 sort_by! 改变数组。 sort_by 返回一个新数组，因此，要获得相同的结果，您还应该将结果分配给数组。

---

这个测试值得重复:

require 'benchmark'

BAR = (1..10_000).to_a.shuffle

n = 1000

Benchmark.bmbm(12) do |b|
  b.report("sort (no block)")  { n.times { foo = BAR.dup; foo = foo.sort;                   foo } }
  b.report("sort! (no block)") { n.times { foo = BAR.dup; foo.sort!;                        foo } }
  b.report("sort (block)")     { n.times { foo = BAR.dup; foo = foo.sort{ |a, b| a <=> b }; foo } }
  b.report("sort! (block)")    { n.times { foo = BAR.dup; foo.sort!{ |a, b| a <=> b };      foo } }
  b.report("sort_by")          { n.times { foo = BAR.dup; foo = foo.sort_by{ |a| a };       foo } }
  b.report("sort_by!")         { n.times { foo = BAR.dup; foo.sort_by!{ |a| a };            foo } }
end

导致:

Rehearsal ----------------------------------------------------
sort (no block)    1.250000   0.010000   1.260000 (  1.253412)
sort! (no block)   1.240000   0.010000   1.250000 (  1.254230)
sort (block)      12.380000   0.010000  12.390000 ( 12.378503)
sort! (block)     12.390000   0.000000  12.390000 ( 12.399870)
sort_by            6.410000   0.010000   6.420000 (  6.408380)
sort_by!           6.720000   0.000000   6.720000 (  6.727324)
------------------------------------------ total: 40.430000sec

                       user     system      total        real
sort (no block)    1.240000   0.010000   1.250000 (  1.249624)
sort! (no block)   1.230000   0.020000   1.250000 (  1.241353)
sort (block)      12.320000   0.010000  12.330000 ( 12.341552)
sort! (block)     12.390000   0.010000  12.400000 ( 12.397626)
sort_by            6.410000   0.010000   6.420000 (  6.411413)
sort_by!           6.940000   0.000000   6.940000 (  6.943647)

这里有两个“要点”:

• sort 在没有 block 的情况下比较基本对象时优于 sort_by，因此如果可以，请使用没有 block 的 sort 系列。
• 如果您正在排序并使用 block 进入对象以查找您正在排序的内容，或者如果您正在进行计算以确定排序值，则使用 sort_by 系列.