Ruby: Почему Array.sort работает медленно для больших объектов?

Question

Коллега должен был отсортировать массив объектов ActiveRecord в приложении Rails. Он попробовал очевидное 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_by вместо sort. sort_by вызывает блок только один раз для каждого объекта, а затем использует кэшированные результаты блока для дальнейшего сравнения.

Answer 2

Так же, как объяснение того, что, вероятно, происходит и как с этим бороться ...

Сортировка имеет тенденцию рассматривать элемент несколько раз, поэтому дорогой поиск объекта или структуры очень быстро становится очень дорогостоящим.

Преобразование Шварца обычно используется при сортировке массивов сложных объектов или структур. Основная идея заключается в том, чтобы предварительно вычислить простое значение, которое точно отражает большую структуру или объект, затем отсортировать значения, а затем использовать результирующий отсортированный массив, чтобы вернуться к тому, из чего они получены.

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

Answer 3

Ничто не отвечает на такие вопросы лучше, чем реальный исходный код языка. Массив # сортировать! использует sort_internal (), которая определена в array.c:

sort_internal ()

(Да, я знаю, что это источники для 1.8.4, но я не могу найти 1.8.6 в сети правильно и уверен, что это не изменилось.)