Ruby: Why is Array.sort slow for large objects?
- by David Waller
A colleague needed to sort an array of ActiveRecord objects in a Rails app. He tried the obvious Array.sort! but it seemed surprisingly slow, taking 32s for an array of 3700 objects. So just in case it was these big fat objects slowing things down, he reimplemented the sort by sorting an array of small objects, then reordering the original array of ActiveRecord objects to match - as shown in the code below. Tada! The sort now takes 700ms.
That really surprised me. Does Ruby's sort method end up copying objects about the place rather than just references? He's using 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
