Ruby:为什么Array.sort对于大型对象来说速度慢？

Question

一位同事需要在Rails应用程序中对一组ActiveRecord对象进行排序.他尝试了显而易见的Array.sort!但看起来非常缓慢,需要32秒才能获得3700个物体.所以以防万一它是速度变慢这些大发物,他通过排序小对象的数组,然后重新排序ActiveRecord对象的原始数组匹配重新实现排序-如下面的代码.田田!排序现在需要700毫秒.

这真让我感到惊讶.Ruby的排序方法最终会复制关于该位置的对象而不仅仅是引用吗？他正在使用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

Answer 1

sort绝对不会复制对象.一个不同之处,我可以使用EventSorter没有它的代码之间的代码想象(你没有提供,所以我猜)是EventSorter调用event.sqn和event.time恰好一次并将结果保存在变量.在排序期间,只需要访问变量.可能会调用原始版本,sqn并且time每次调用sort-block时.

如果是这种情况,可以使用sort_by而不是sort来修复它.sort_by仅对每个对象调用一次块,然后使用块的缓存结果进行进一步比较.