Extracción de un número dado de los valores más altos en una lista

Question

Estoy tratando de mostrar un número fijo de elementos en una página web de acuerdo con su peso respectivo (representado por un Integer). La lista donde se encuentran estos elementos puede ser de prácticamente cualquier tamaño.

La primera solución que se le viene a la mente es hacer un Collections.sort() y obtener los artículos uno por uno yendo a través del List. ¿Existe una solución más elegante que pueda usarse para preparar, por ejemplo, los ocho artículos principales?

Answer 1

Solo tiene que ir por Collections.sort(..). Es lo suficientemente eficiente.

Este algoritmo ofrece un rendimiento n log (n) garantizado.

Usted puede tratar de poner en práctica algo más eficiente para su caso concreto si usted sabe algunas propiedades distintivas de su lista, pero que no estaría justificada. Además, si su lista proviene de una base de datos, por ejemplo, puede LIMIT & ordenarla allí en lugar de en el código.

Answer 2

Puede usar max-heap.

Si sus datos provienen de una base de datos, coloque un índice en esa columna y use ORDER BY y TOP o LIMIT para buscar solo los registros que necesita visualizar.

Answer 3

O a priority queue.

Answer 4

No, realmente no. Al menos no usando los métodos integrados de Java.

Hay formas inteligentes de obtener el número N más alto (o el más bajo) de una lista más rápido que una operación O(n*log(n)), pero eso requerirá que codifique esta solución a mano. Si el número de artículos permanece relativamente bajo (no más de un par de cientos), ordenarlo usando Collections.sort() y luego agarrar los N números superiores es la manera de ir a IMO.

Answer 5

usando dollar:

List<Integer> topTen = $(list).sort().slice(10).toList(); 

sin necesidad de utilizar el dólar debe sort() usando Collections.sort(), a continuación, obtener los primeros n elementos usando list.sublist(0, n).

Answer 6

Dado que dice que la lista de elementos para extraer estos N superiores puede ser de cualquier tamaño, y por lo tanto puede ser grande, supongo que aumentaría las respuestas simples sort() anteriores (que son totalmente apropiadas para un tamaño razonable entrada) sugiriendo que la mayor parte del trabajo aquí es encontrar el N superior; luego, ordenar esos N es trivial. Es decir:

Queue<Integer> topN = new PriorityQueue<Integer>(n); 
for (Integer item : input) { 
    if (topN.size() < n) { 
    topN.add(item);   
    } else if (item > topN.peek()) { 
    topN.add(item);   
    topN.poll(); 
    } 
} 

List<Integer> result = new ArrayList<Integer>(n); 
result.addAll(topN); 
Collections.sort(result, Collections.reverseOrder()); 

El montón aquí (un min-heap) es al menos limitado en tamaño. No hay una necesidad real de hacer un montón de todos sus artículos.

Answer 7

Sus opciones:

1. Haz una lineal búsqueda, el mantenimiento de los N primeros pesos que se encuentran en el camino. Esto debería ser más rápido que ordenar una lista larga si, por alguna razón, no puede reutilizar los resultados de clasificación entre mostrar la página (por ejemplo, la lista está cambiando rápidamente).

   ACTUALIZACIÓN: Me corresponde corregir en la búsqueda lineal que necesariamente es mejor que la clasificación. Consulte el artículo de Wikipedia "Selection_algorithm - Selecting k smallest or largest elements" para obtener mejores algoritmos de selección.

2. Mantenga manualmente un List (el original o uno paralelo) ordenado en orden de peso. Puede usar métodos como Collections.binarySearch() para determinar dónde insertar cada nuevo elemento.

3. Mantener un List (el original uno o un paralelo uno) ordenadas en orden de peso llamando Collections.sort() después de cada modificación, las modificaciones de proceso por lotes, o justo antes de la pantalla (posiblemente el mantenimiento de un indicador de modificación para evitar clasificar una lista ya ordenados).

4. Utilice una estructura de datos que mantenga orden de peso ordenado para usted: priority queue, tree set, etc. También podría crear su propia estructura de datos.

5. Mantenga manualmente una segunda estructura de datos (posiblemente por peso) de los N elementos principales. Esta estructura de datos se actualiza cada vez que se modifica la estructura de datos original. Podrías crear tu propia estructura de datos para envolver la lista original y esta "caché N superior" juntas.

Answer 8

Depende de cuántos. Vamos a definir n como el número total de claves, y m como el número que desea visualizar.
Ordenación de toda la cosa: O(nlogn)
El escaneo de la gama cada vez para el siguiente número más alto: O(n*m)
Así que la pregunta es - ¿Cuál es la relación entre n para m?
Si m < log n, el escaneo será más eficiente.
De lo contrario, m >= log n, lo que significa que la clasificación será mejor. (Dado que para el caso de borde de m = log n en realidad no importa, pero la clasificación también le dará la ventaja de, bueno, ordenar la matriz, que siempre es agradable.

Answer 9

Si el tamaño de la lista es N, y el número de elementos que se recuperarán es K, necesita llamar a Heapify en la lista, que convierte la lista (que debe ser indexable, por ejemplo, una matriz) en una cola de prioridad. (Ver función heapify en http://en.wikipedia.org/wiki/Heapsort)

Recuperación de un elemento en la parte superior de la pila (el elemento max) toma tiempo O (lg N) para que su tiempo total sería:.

O (N + k lg N)

que es mejor que O (N lg N) suponiendo que k es mucho más pequeño que N.

Answer 10

Si mantener una matriz ordenada o utilizar una estructura de datos diferente no es una opción, puede intentar algo como lo siguiente. El tiempo O es similar a ordenar el conjunto grande, pero en la práctica esto debería ser más eficiente.

small_array = big_array.slice(number_of_items_to_find); 
small_array.sort(); 
least_found_value = small_array.get(0).value; 

for (item in big_array) { // needs to skip first few items 
    if (item.value > least_found_value) { 
    small_array.remove(0); 
    small_array.insert_sorted(item); 
    least_found_value = small_array.get(0).value; 
    } 
} 

small_array podría ser un Object [] y el bucle interior se podría hacer con el intercambio en lugar de realmente la eliminación y la inserción en una matriz.