2010-03-13 37 views
12

Un colega necesitaba ordenar una matriz de objetos ActiveRecord en una aplicación de Rails. Intentó el obvio Array.sort! pero parecía sorprendentemente lento, tomando 32s para una matriz de 3700 objetos. Así que solo en caso de que estos objetos grandes y gordos redujeran la velocidad de las cosas, reimplementó el género ordenando una serie de pequeños objetos, y luego reorganizando la matriz original de objetos ActiveRecord para que coincida, como se muestra en el siguiente código. Tada! El género ahora lleva 700ms.Ruby: ¿Por qué Array.sort es lento para objetos grandes?

Eso realmente me sorprendió. ¿El método de clasificación de Ruby termina copiando objetos sobre el lugar en lugar de solo referencias? Él está 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 
+1

Su '' <=> método también se puede escribir como: '.nonzero (@time <=> b.time)? o @sqn <=> b.sqn' –

+2

¿El registro de registro activo muestra algo interesante que sucede durante el proceso? Asegúrese de que esté configurado para registrar las consultas de la base de datos. –

+0

Glenn - Gracias por el consejo en <=>. Wayne - Creo que es posible que tenga la respuesta. Después de no obtener ninguna respuesta definitiva aquí en SO me burlé de un pequeño script de prueba para ordenar algunos objetos grandes de ActiveRecord (rellenos con algunas cadenas aleatorias) y luego repite el orden usando la técnica anterior. Ninguna mejora en absoluto. Así que el lunes le sugeriré a mi colega que tiene que buscar efectos secundarios durante el proceso. –

Respuesta

6

sort definitivamente no copia los objetos. Una diferencia que puedo imaginar entre el código que utiliza EventSorter y el código sin él (que no me proporcionó, por lo que tengo que adivinar) es que EventSorter llama al event.sqn y event.time exactamente una vez y almacena el resultado en variables. Durante la clasificación, solo se debe acceder a las variables. La versión original presumiblemente llamaba a sqn y time cada vez que se invocaba el bloque de clasificación.

Si este es el caso, se puede solucionar utilizando sort_by en lugar de ordenar. sort_by solo llama al bloque una vez por objeto y luego utiliza los resultados almacenados en caché del bloque para realizar más comparaciones.

+0

Has acertado - El evento tiene un método casi idéntico <=> para EventSorter, pero en el caso de Event, sqn y time son los nombres de las columnas en la base de datos. Eso significa que Rails/ActiveRecord proporciona métodos de sqn y de tiempo, que parece analizar los valores en los atributos de ActiveRecord hash cada vez que son llamados. Así que cada vez Evento. <=> se llamaba ActiveRecord estaba analizando una cadena de tiempo en un objeto Ruby Time, de ahí el rendimiento horrible. ¡Misterio resuelto! Gracias. –

0

Nada responde a preguntas como esta mejor que el código fuente del idioma real. Array # sort! utiliza sort_internal() que se define en array.c:

sort_internal()

(Sí, ya sé que es las fuentes de 1.8.4, pero no puedo encontrar las correctas 1.8.6 en línea y estoy bastante seguro de que este no ha cambiado.)

+1

Vamos - ¡dame una pista! No soy lo suficientemente fluido en C para hacer mucho de esto. –

+0

¡Oh, lo siento por eso! Básicamente utiliza una ordenación rápida, que está entre O (N^2) (el peor de los casos) y O (N log N) (el mejor de los casos). –

+3

Pero eso no parece explicar por qué es más lento ordenar una matriz de objetos grandes en lugar de una serie de objetos pequeños.¿La implementación requiere copiar los objetos alrededor del montón en lugar de simplemente reorganizar punteros? –

2

Así como una explicación de lo que es probable que ocurra y cómo tratar con él ...

Clasificación tiende a mirar a un elemento varias veces para una búsqueda costosa en el objeto o estructura llegará a ser muy costosa muy rápidamente .

Una Transformada Schwartzian se usa comúnmente al ordenar matrices de objetos o estructuras complejas. La idea básica es precomputar un valor simple que refleje con precisión la gran estructura u objeto, luego ordenar los valores, luego usar la matriz ordenada resultante para referirse a la fuente de la que provienen.

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

Cuestiones relacionadas