在Ruby中对字符串数组进行排序

Question

我已经学习了 Ruby 中的两种数组排序方法：

array = ["one", "two", "three"]
array.sort.reverse!

或者：

array = ["one", "two", "three"]
array.sort { |x,y| y<=>x }

我无法区分这两种方法。哪一种方法更好，它们在执行上有何不同？

- poorvank

---

这是一个有些棘手的问题。它使用了相同的方法#sort，如果需要实现细节，请查阅C源代码：http://ruby-doc.org/core-2.0/Array.html#method-i-sort。 - Boris Stitnicky

另外：如果你需要一个在Ruby中支持大多数Enumerable方法、可以排序和存储唯一数据的数据结构，你可能想看看SortedSet。 - Kashyap

Answer 1

这两行代码的作用相同（创建一个新数组，其中元素是反向排序的）。主要争论点在于可读性和性能。使用array.sort.reverse!比使用array.sort{|x,y| y<=>x}更易读 - 我们可以在这方面达成共识。

至于性能部分，我创建了一个快速基准测试脚本，在我的系统上（ruby 1.9.3p392 [x86_64-linux]）给出以下结果：

                              user     system      total        real
array.sort.reverse        1.330000   0.000000   1.330000 (  1.334667)
array.sort.reverse!       1.200000   0.000000   1.200000 (  1.198232)
array.sort!.reverse!      1.200000   0.000000   1.200000 (  1.199296)
array.sort{|x,y| y<=>x}   5.220000   0.000000   5.220000 (  5.239487)

运行时间在多次执行基准测试脚本时非常稳定。

array.sort.reverse(带或不带!)比array.sort{|x,y| y<=>x}要快得多。因此，我建议使用前者。

---

这里是参考脚本：

#!/usr/bin/env ruby
require 'benchmark'

Benchmark.bm do|b|
  master = (1..1_000_000).map(&:to_s).shuffle
  a = master.dup
  b.report("array.sort.reverse      ") do
    a.sort.reverse
  end

  a = master.dup
  b.report("array.sort.reverse!     ") do
    a.sort.reverse!
  end

  a = master.dup
  b.report("array.sort!.reverse!    ") do
    a.sort!.reverse!
  end

  a = master.dup
  b.report("array.sort{|x,y| y<=>x} ") do
    a.sort{|x,y| y<=>x}
  end
end

- tessi

---

一个小的改进是只创建一次数组：master = (1..1000000).map(&:to_s).shuffle，然后在每个基准测试报告之前设置 a = master.clone，这样它们都会精确地排序相同的东西。我还将大小提高到了 1_000_000，并添加了一个 a.sort!.reverse! 的基准测试。在我的系统上（ruby 2.0.0p195 [x86_64-darwin12.3.0]），使用原地 a.sort!.reverse! 获胜。 - pjs

这里的 reverse! 浪费了 CPU。它试图修改由 sort 交出的临时数组，这并没有帮助。 - the Tin Man

@pjs，在Stack Overflow上，我有一个大型基准测试，测试了多种进行降序排序的方法。使用 reverse 比在块中使用 sort_by 或者使用反转或否定结果的 sort 更快，这让我们感到惊讶。sort!.reverse! 更快是因为它改变了原始数组。 - the Tin Man

@theTinMan - 对我来说非常清楚。这就是为什么在我尝试时添加了特定的基准测试的原因。 - pjs

@pjs，我采纳了你的建议。有趣的是，在1.9.3中，array.sort.reverse!略微更快。 - tessi

Answer 2

这里实际上没有区别。两种方法都返回一个新的数组。

就这个例子而言，简单就是美。我建议使用array.sort.reverse，因为它比另一种方法更易读。将块传递给像sort这样的方法应该保留给更复杂的数据结构和用户定义的类的数组。

编辑：虽然destructive方法（任何以！结尾的方法）对于性能提升很好，但有人指出它们不需要返回更新后的数组，或者根本不需要返回任何东西。这一点很重要，因为array.sort.reverse!很可能会返回nil。如果您希望在新生成的数组上使用破坏性方法，则应该优先调用.reverse!在单独的一行上而不是一行代码中。

示例：

array = array.sort
array.reverse!

应优先选择

array = array.sort.reverse!

- James Brewer

---

楼主正在学习Ruby，这个阶段不应该过于关注性能问题。我仍然坚持我的建议。 - James Brewer

@JamesBrewer，然而，在先前排序创建的临时数组上调用破坏性reverse是一种不好的做法。文档中没有说明reverse！必须返回更新后的数组，它只会更新被调用的对象。非破坏性版本才有此功能。 - Torimus

Answer 3

反转！更快速

通常情况下，基准测试是无可替代的。虽然在较短的脚本中可能没有区别，但使用 #reverse! 方法相对于使用“太空船”运算符进行排序会显著地提升速度。例如，在MRI Ruby 2.0上，给定以下基准测试代码：

require 'benchmark'

array = ["one", "two", "three"]
loops = 1_000_000

Benchmark.bmbm do |bm|
    bm.report('reverse!')  { loops.times {array.sort.reverse!} }
    bm.report('spaceship') { loops.times {array.sort {|x,y| y<=>x} }}
end

系统报告称 #reverse! 操作几乎比使用联合比较运算符快了一倍。

                user     system      total        real
reverse!    0.340000   0.000000   0.340000 (  0.344198)
spaceship   0.590000   0.010000   0.600000 (  0.595747)

我的建议是：在特定的上下文中使用语义更有意义的内容，除非你正在运行一个紧密循环。

- Todd A. Jacobs

---

这实际上是一架X翼战斗机 :) - squiguy

Answer 4

当比较像你的例子一样简单时，没有太大的区别，但是随着比较公式变得更加复杂，最好避免在块中使用<=>，因为传递的块将针对数组的每个元素进行评估，导致冗余。考虑以下情况：

array.sort{|x, y| some_expensive_method(x) <=> some_expensive_method(y)}

在这种情况下，some_expensive_method将为array的每一个可能的元素对进行评估。

在您的特定情况下，可以使用reverse来避免使用带有<=>的块。

array.sort_by{|x| some_expensive_method(x)}.reverse

这被称为Schwartzian变换。

- sawa

---

你如何使用 sort_by 进行“反向排序”？因为这就是 OP 所做的。 - Sergio Tulentsev

谢谢你指出“Schartzian transform”这个术语 - 我不知道这个模式有一个名字 :) - tessi

Answer 5

在我的机器上运行tessi的基准测试时，我得到了一些有趣的结果。我正在运行最新版本的Ruby 2（即ruby 2.0.0p195 [x86_64-darwin12.3.0]），并使用bmbm而不是Benchmark模块中的bm。我的时间如下：

Rehearsal -------------------------------------------------------------
array.sort.reverse:         1.010000   0.000000   1.010000 (  1.020397)
array.sort.reverse!:        0.810000   0.000000   0.810000 (  0.808368)
array.sort!.reverse!:       0.800000   0.010000   0.810000 (  0.809666)
array.sort{|x,y| y<=>x}:    0.300000   0.000000   0.300000 (  0.291002)
array.sort!{|x,y| y<=>x}:   0.100000   0.000000   0.100000 (  0.105345)
---------------------------------------------------- total: 3.030000sec

                                user     system      total        real
array.sort.reverse:         0.210000   0.000000   0.210000 (  0.208378)
array.sort.reverse!:        0.030000   0.000000   0.030000 (  0.027746)
array.sort!.reverse!:       0.020000   0.000000   0.020000 (  0.020082)
array.sort{|x,y| y<=>x}:    0.110000   0.000000   0.110000 (  0.107065)
array.sort!{|x,y| y<=>x}:   0.110000   0.000000   0.110000 (  0.105359)

首先，请注意在排练阶段，使用比较块的 sort! 显然是赢家。Matz 在 Ruby 2 中肯定对其进行了大量调整！

另一件让我感到非常奇怪的事情是，在生产过程中，array.sort.reverse! 和 array.sort!.reverse! 的改进程度如此之大，以至于让我怀疑是否已经传递了这些已排序的数据，因此在执行每个基准测试之前，我添加了明确检查已排序或反向排序数据的步骤。

---

我的版本遵循tessi的脚本：

#!/usr/bin/env ruby
require 'benchmark'

class Array
  def sorted?
    (1...length).each {|i| return false if self[i] < self[i-1] }
    true
  end

  def reversed?
    (1...length).each {|i| return false if self[i] > self[i-1] }
    true
  end
end

master = (1..1_000_000).map(&:to_s).shuffle

Benchmark.bmbm(25) do|b|
  a = master.dup
  puts "uh-oh!" if a.sorted?
  puts "oh-uh!" if a.reversed?
  b.report("array.sort.reverse:") { a.sort.reverse }

  a = master.dup
  puts "uh-oh!" if a.sorted?
  puts "oh-uh!" if a.reversed?
  b.report("array.sort.reverse!:") { a.sort.reverse! }

  a = master.dup
  puts "uh-oh!" if a.sorted?
  puts "oh-uh!" if a.reversed?
  b.report("array.sort!.reverse!:") { a.sort!.reverse! }

  a = master.dup
  puts "uh-oh!" if a.sorted?
  puts "oh-uh!" if a.reversed?
  b.report("array.sort{|x,y| y<=>x}:") { a.sort{|x,y| y<=>x} }

  a = master.dup
  puts "uh-oh!" if a.sorted?
  puts "oh-uh!" if a.reversed?
  b.report("array.sort!{|x,y| y<=>x}:") { a.sort!{|x,y| y<=>x} }
end

- pjs