Ruby: Perché Array.sort è lento per oggetti di grandi dimensioni?

Question

Un collega aveva bisogno di ordinare una matrice di oggetti ActiveRecord in un'app Rails. Ha provato l'ovvio Array.sort! ma sembrava sorprendentemente lento, prendendo 32 secondi per un array di 3700 oggetti. Quindi, nel caso in cui questi grandi oggetti grassi rallentassero le cose, ha reimplementato l'ordinamento ordinando una serie di piccoli oggetti, quindi riordinando la matrice originale di oggetti ActiveRecord in modo che corrispondessero - come mostrato nel codice qui sotto. Tada! L'ordinamento ora richiede 700ms.

Questo mi ha davvero sorpreso. Il metodo di ordinamento di Ruby finisce per copiare oggetti sul luogo anziché solo riferimenti? Sta usando 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 sicuramente non copia gli oggetti. Una differenza che posso immaginare tra il codice che utilizza EventSorter e il codice senza (che non hai fornito, quindi devo indovinare) è che EventSorter chiama event.sqn e event.time esattamente una volta e memorizza il risultato in variabili. Durante l'ordinamento è necessario accedere solo alle variabili. La versione originale presumibilmente si chiamava sqn e time ogni volta che veniva richiamato il blocco di ordinamento.

In questo caso, può essere risolto utilizzando sort_by anziché ordinamento. sort_by chiama il blocco solo una volta per oggetto e quindi utilizza i risultati memorizzati nella cache del blocco per ulteriori confronti.

Answer 2

Nulla risponde a domande come questa meglio del codice sorgente della lingua corrente. Array # sorta! usa sort_internal() che è definito in array.c:

sort_internal()

(Sì, lo so che è le fonti per 1.8.4, ma non riesco a trovare 1.8.6 quelli on-line e sono abbastanza sicuro che questo non è cambiato)

Answer 3

Proprio come una spiegazione di ciò che è probabile che accada e come trattare con esso ...

Ordinamento tende a guardare un elemento più volte in modo una ricerca costosa in oggetto o struttura diventerà molto costoso molto rapidamente .

Una trasformazione di Schwartz è comunemente utilizzata per ordinare array di oggetti o strutture complessi. L'idea di base è precalcolare un valore semplice che rifletta accuratamente la grande struttura o l'oggetto, quindi ordinare i valori, quindi utilizzare la matrice ordinata risultante per fare riferimento alla cosa da cui provengono.

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