Java - Buscando algo más rápido que PriorityQueue

Question

Estoy usando Java en una gran cantidad de datos.

[i tratar de simplificar el problema tanto como sea posible]

realidad tengo una clase pequeña (Element) que contiene una clave int y un peso doble (con getters & setters).

He leído muchos de estos objetos de un archivo y tengo que obtener los mejores objetos M (más pesados).

Actualmente estoy usando un PriorityQueue con un comparador escrito para comparar dos elementos, y funciona, pero es demasiado lento.

¿Sabe (lo conozco) alguna forma más rápida de hacerlo?

Gracias

Answer 1

Una cola de prioridad basada en el montón es una buena estructura de datos para este problema. Al igual que un control de cordura, verifique que esté utilizando la cola correctamente.

Si desea que los elementos de peso más altas, use un min -Queue — en la parte superior de la pila es el elemento más pequeño. Agregar cada elemento a una cola máxima y examinar los elementos superiores de M una vez hecho no es eficiente.

Para cada elemento, si hay menos de M elementos en la cola, agregue el elemento actual. De lo contrario, echa un vistazo a la parte superior del montón. Si es menor que el elemento actual, deséchelo y agregue el elemento actual en su lugar. De lo contrario, descarta el elemento actual. Cuando se hayan procesado todos los artículos, la cola contendrá los artículos de mayor peso M.

Algunos montones tienen API de acceso directo para reemplazar el tope del montón, pero el Queue de Java no lo hace. Aun así, la complejidad de la gran O es la misma.

Answer 2

Si M es adecuadamente pequeño, a continuación, clasificando todos los elementos pueden perder mucho tiempo de cálculo. Solo puedes poner los primeros objetos M en cola de prioridad (por ejemplo, un montón, elemento mínimo en la parte superior) y luego iterar sobre el resto de los elementos: cada vez que un elemento es más grande que la parte superior del montón, elimina la parte superior y empuja la nueva elemento en el montón.

De forma alternativa, podría iterar en toda la matriz una vez para encontrar un valor de umbral estadístico para el cual puede estar seguro de que hay más de M objetos con un valor mayor (requerirá algunas suposiciones con respecto a los valores, por ejemplo, si Normalmente distribuido). A continuación, puede limitar la clasificación a todos los elementos con un valor mayor.

Answer 3

@Tnay: Tiene sentido no hacer una comparación. Desafortunadamente, su código de ejemplo todavía realiza uno. Esto resuelve el problema:

public int compare(ListElement i, ListElement j) { 
    return i.getValue() - j.getValue(); 
} 

Además, ni el suyo, ni Biggs comparar método es estrictamente correcto, ya que nunca vuelvan 0. Esto puede ser un problema con algunos algoritmos de ordenación, que es un error muy complicado, ya solo aparecerá si cambia a otra implementación.

De the Java docs:

El implementador debe asegurar que sgn (compárese con (x, y)) == -sgn (comparar (y, x)) para todo x e y.

Esto puede o no tener una aceleración de factor constante significativa. Si combina esto con la solución de Erickson, probablemente será difícil hacerlo más rápido (dependiendo del tamaño de M). Si M es muy grande, la solución más eficiente probablemente sea ordenar todos los elementos usando el qsort incorporado de Java en una matriz y cortar un extremo de la matriz al final.

Answer 4

Además del algoritmo sugerido de "echar un vistazo en la parte superior del montón", que le da complejidad O (n log m) para obtener el top-m de n elementos, aquí hay dos soluciones más.

Solución 1: Use un montón de Fibonacci.

La implementación de PriorityQueue del JDK es un montón binario equilibrado. Debería poder exprimir más rendimiento de una implementación de Fibonacci heap. Se habrá amortizado el inserto de tiempo constante, mientras que la inserción en un montón binario tiene una complejidad Ω (log n) en el tamaño del montón. Si estás haciendo eso para cada elemento, entonces estás en Ω (n log n). Encontrar el top-m de n elementos usando un montón de Fib tiene complejidad O (n + m log n). Combine esto con la sugerencia de que solo inserte m elementos en el montón, y tiene O (n + m log m), que es lo más cercano al tiempo lineal que va a obtener.

Solución 2: recorra la lista M veces.

Debería poder obtener el elemento k-mayor en un conjunto en el tiempo O (n). Simplemente lea todo en una lista y haga lo siguiente:

kthLargest(k, xs) 
    Pick a random pivot element p from the list 
    (the first one will do if your list is already random). 
    Go over the set once and group it into two lists. 
    Left: smaller than p. 
    Right: Larger or equal to p. 
    If the Right list is shorter than k, return kthLargest(k - right.size, Left) 
    If the Right list is longer than k, return kthLargest(k, right) 
    Otherwise, return p. 

Eso le da O (n) tiempo. Ejecutando ese m veces, debería ser capaz de obtener los objetos top-m en su conjunto en el tiempo O (nm), que será estrictamente menor que n log n para n suficientemente grande y lo suficientemente pequeño m. Por ejemplo, obtener el top-10 de más de un millón de elementos tomará la mitad de tiempo que usar una cola de prioridad de montón binaria, en igualdad de condiciones.