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

Коллеге необходимо было отсортировать массив объектов ActiveRecord в приложении Rails. Он пробовал очевидный Array.sort!, но он казался неожиданно медленным, взяв 32s для массива из 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

Ответы

Ответ 1

sort определенно не копирует объекты. Одно отличие, которое я могу представить между кодом, использующим EventSorter, и кодом без него (который вы не поставляли, поэтому я должен угадать), заключается в том, что EventSorter вызывает event.sqn и event.time ровно один раз и сохраняет результат в переменных. При сортировке необходимо получить доступ только к переменным. Первоначальная версия предположительно называлась sqn и time каждый раз при вызове sort-block.

Если это так, его можно устранить, используя sort_by вместо сортировки. sort_by только вызывает блок один раз на объект и затем использует кешированные результаты блока для дальнейших сравнений.

Ответ 2

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

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

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

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

Ответ 3

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

sort_internal()

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