Ruby：为什么对大型对象进行排序时Array.sort速度缓慢？

Question

我的同事需要对Rails应用程序中的一个ActiveRecord对象数组进行排序。 他尝试了显而易见的Array.sort！，但似乎速度非常慢，对于3700个对象的数组，需要32秒的时间。 因此，以防这些大型对象拖慢速度，他重新实现了排序，通过对小对象数组进行排序，然后重新排列原始的ActiveRecord对象数组以匹配 - 如下所示。 Tada！ 现在排序只需要700毫秒。

这真的让我很惊讶。Ruby的sort方法最终会复制对象到各个地方，而不仅仅是引用吗？他正在使用Ruby 1.8.6 / 7。

def self.sort_events(events)
  event_sorters = Array.new(events.length) {|i| EventSorter.new(i, events[i])}
  event_sorters.sort!
  event_sorters.collect {|es| events[es.index]} 
end

private

# Class used by sort_events
class EventSorter
  attr_reader :sqn
  attr_reader :time
  attr_reader :index

  def initialize(index, event)
    @index = index  
    @sqn   = event.sqn
    @time  = event.time  
  end

  def <=>(b)
    @time != b.time ? @time <=> b.time : @sqn <=> b.sqn
  end
end

- David Waller

---

你的 <=> 方法也可以写成：(@time <=> b.time).nonzero? or @sqn <=> b.sqn。 - glenn jackman

活动记录日志是否显示在排序期间发生了什么有趣的事情？请确保配置记录数据库查询。 - Wayne Conrad

Glenn - 感谢你关于<=>的提示。Wayne - 我认为你可能有答案。在SO这里没有得到任何明确的答案后，我编写了一个小测试脚本来对一些大型ActiveRecord对象进行排序（使用一些随机字符串填充），然后使用上述技术重复排序。完全没有改进。因此，周一我会建议我的同事在排序过程中寻找副作用。 - David Waller

Answer 1

sort 没有复制对象。我可以想象使用 EventSorter 代码与不使用它的代码之间的一个区别（你没有提供，所以我必须猜测）是 EventSorter 调用 event.sqn 和 event.time 只一次，并将结果存储在变量中。在排序期间，只需要访问变量即可。原始版本可能每次调用排序块时都会调用 sqn 和 time。

如果是这种情况，可以通过使用 sort_by 而不是 sort 来解决问题。sort_by 每个对象仅调用一次块，然后使用块的缓存结果进行进一步比较。

- sepp2k

---

你猜对了 - Event类有一个几乎与EventSorter相同的<=>方法，但在Event类中，sqn和time是数据库中列的名称。这意味着Rails / ActiveRecord提供了sqn和time方法，它们似乎会解析ActiveRecord属性哈希中的值每次调用它们时。因此，每次调用Event.<=>时，ActiveRecord都会将时间字符串解析为Ruby Time对象，因此性能非常差。谜团解决了！谢谢。 - David Waller

Answer 2

作为解释可能正在发生的事情以及如何处理它的说明...

排序通常会多次查看元素，因此对对象或结构进行昂贵的查找将很快变得非常昂贵。

当对复杂对象或结构的数组进行排序时，Schwartzian Transform通常被使用。基本思想是预先计算一个简单的值，准确反映大结构或对象，然后对这些值进行排序，然后使用结果排序的数组来引用它们所来自的东西。

http://en.wikipedia.org/wiki/Schwartzian_transform

- the Tin Man

Answer 3

要回答此类问题，最好的方式莫过于查看实际语言源代码。Array#sort!使用在array.c文件中定义的sort_internal()：

sort_internal()

（是的，我知道这是1.8.4版本的源代码，但我找不到1.8.6版本的在线源代码，并且相信这没有改变。）

- Michael Kohl

---

继续——给我一个提示吧！ 我的C语言水平不够好，很难理解这个。 - David Waller

哦，对不起！它基本上使用快速排序，其时间复杂度介于O（N ^ 2）（最坏情况）和O（N log N）（最佳情况）之间。 - Michael Kohl

似乎这并不能解释为什么排序一个大对象数组比排序一个小对象数组慢。是不是实现需要在堆中复制对象而不仅仅是重新排列指针？ - David Waller