<=>如何针对不同的排序策略工作？

Question

我正在浏览CodeAcademy上的一些教程，并遇到了这个场景：

books = ["Charlie and the Chocolate Factory", "War and Peace", "Utopia", "A Brief History of Time", "A Wrinkle in Time"]

# To sort our books in ascending order, in-place
books.sort! { |firstBook, secondBook| firstBook <=> secondBook }


# Sort your books in descending order, in-place below
# this lin initially left blank
books.sort! {|firstBook, secondBook| secondBook <=> firstBook}

我没有使用if/else块，而是尝试了一下，它成功了，但我不知道为什么。我假设您在支票中放置项目的顺序并不重要(例如，a <=> b与b <=> a)。有人能解释一下这里发生了什么吗？

Answer 1

如果反转<=>中的元素，则会反转其值。如果两个元素相等，则此操作符返回0，但如果第一个元素较小，则返回负值；如果第一个元素较大，则返回正值。因此，如果为temp = a <=> b，则b <=> a为-temp。因此，如果您以相反的顺序编写参数，则会颠倒排序的顺序。

Answer 2

下面是一些简单的可视方式来了解<=>做了什么，以及颠倒比较变量的顺序如何影响输出的顺序。

从基本数组开始：

foo = %w[a z b x]

我们可以进行升序排序：

foo.sort { |i, j| i <=> j } # => ["a", "b", "x", "z"]

或者通过颠倒被比较的两个变量来进行降序排序：

foo.sort { |i, j| j <=> i } # => ["z", "x", "b", "a"]

根据比较结果是<、==还是>，<=>运算符分别返回-1、0或1。

我们可以通过否定比较的结果来测试这一点，如果理论成立，这将颠倒顺序。

foo.sort { |i, j| -(i <=> j) } # => ["z", "x", "b", "a"]
foo.sort { |i, j| -(j <=> i) } # => ["a", "b", "x", "z"]

通过否定比较的结果，顺序确实颠倒了。但是，为了清晰起见，只需颠倒变量的顺序即可。

话虽如此，使用sort或其破坏性兄弟sort!并不总是对复杂对象进行排序的最快方法。简单对象，如字符串、字符和数字，排序速度非常快，因为它们的类实现了快速执行<=>测试所需的方法。

一些答案和评论提到了sort_by，所以我们就去那里吧。

复杂对象通常不会正确排序，因此我们最终使用getters/accessors来检索我们想要比较的值，并且该操作会占用CPU时间。sort会反复比较这些值，这样检索就会重复发生，当排序没有发生时，这些值加起来就是浪费的时间。

为了解决这个问题，一位名叫Randall Schwartz的聪明人开始使用一种算法，该算法只预先计算一次用于排序的值；因此，该算法通常被称为Schwartzian Transform。该值和实际对象被捆绑在一个小的子数组中，然后进行排序。因为排序是针对预先计算的值进行的，所以它及其关联的对象将按顺序移动，直到排序完成。此时，将检索实际对象并将其作为方法的结果返回。Ruby使用sort_by实现了这种类型的排序。

sort_by不在外部使用<=>，因此您可以通过简单地告诉它如何获取要比较的值来进行排序：

class Foo
  attr_reader :i, :c
  def initialize(i, c)
    @i = i
    @c = c
  end
end

这是对象的数组。请注意，它们是按创建顺序排列的，但没有排序：

foo = [[1,  'z'], [26, 'a'], [2,  'x'], [25, 'b'] ].map { |i, c| Foo.new(i, c) }
# => [#<Foo:0x007f97d1061d80 @c="z", @i=1>,
#     #<Foo:0x007f97d1061d58 @c="a", @i=26>,
#     #<Foo:0x007f97d1061d30 @c="x", @i=2>,
#     #<Foo:0x007f97d1061ce0 @c="b", @i=25>]

按整数值排序：

foo.sort_by{ |f| f.i } 
# => [#<Foo:0x007f97d1061d80 @c="z", @i=1>,
#     #<Foo:0x007f97d1061d30 @c="x", @i=2>,
#     #<Foo:0x007f97d1061ce0 @c="b", @i=25>,
#     #<Foo:0x007f97d1061d58 @c="a", @i=26>]

按字符值排序：

foo.sort_by{ |f| f.c } 
# => [#<Foo:0x007f97d1061d58 @c="a", @i=26>,
#     #<Foo:0x007f97d1061ce0 @c="b", @i=25>,
#     #<Foo:0x007f97d1061d30 @c="x", @i=2>,
#     #<Foo:0x007f97d1061d80 @c="z", @i=1>]

sort_by对使用取反的值的响应不如sort和<=>，因此，基于some benchmarks在堆栈溢出上所做的一段时间，我们知道对结果值使用reverse是将顺序从升序切换到降序的最快方法：

foo.sort_by{ |f| f.i }.reverse
# => [#<Foo:0x007f97d1061d58 @c="a", @i=26>,
#     #<Foo:0x007f97d1061ce0 @c="b", @i=25>,
#     #<Foo:0x007f97d1061d30 @c="x", @i=2>,
#     #<Foo:0x007f97d1061d80 @c="z", @i=1>]

foo.sort_by{ |f| f.c }.reverse 
# => [#<Foo:0x007f97d1061d80 @c="z", @i=1>,
#     #<Foo:0x007f97d1061d30 @c="x", @i=2>,
#     #<Foo:0x007f97d1061ce0 @c="b", @i=25>,
#     #<Foo:0x007f97d1061d58 @c="a", @i=26>]

它们在某种程度上是可以互换的，但您必须记住，sort_by确实有开销，当您在针对简单对象运行时将其时间与sort时间进行比较时，这一点是显而易见的。在正确的时间使用正确的方法，您可以看到戏剧性的速度提升。

Answer 3

如果你有这样的东西

my_array = ["b","c","a"]

my_array.sort!会比较数组的元素，因为它知道英文字母表中的字母具有自然的顺序，同样，如果您有整数数组，也是如此

my_array2 = [3,1,2]

my_array2.sort!将比较这些元素并给出结果1,2,3

但是，如果您想要更改在字符串数组或复杂对象中进行比较的方式，则可以使用<=>运算符进行指定。

my_array3 = ["hello", "world how are" , "you"]

my_array3.sort! { |first_element, second_element| first_element <=> second_element }

因此，它将告诉排序方法进行如下比较：

Is first_element < second_element

Is first_element = second_element

Is first_element > second_element

但是如果你把这个stmt，

my_array3.sort! { |first_element, second_element| first_element <=> second_element }

比较结果如下：

是second_element < first_element吗？

Is second_element = first_element？

是second_element > first_element吗？

因此，如果您更改要考虑的元素，则会有所不同。