La extracción de un número determinado 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 a 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 viene a la mente es hacer un Collections.sort() y para conseguir los artículos uno por uno por ir a través de la List. ¿Hay una solución más elegante a pesar de que podrían ser utilizados para preparar, por ejemplo, los ocho mejores equipos?

Answer 1

Simplemente de Collections.sort(..). Es lo suficientemente eficiente.

  

Esta actuación ofertas algoritmo garantizada n log (n).

pueden 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. Por otra parte, si su lista proviene de una base de datos, por ejemplo, puede que LIMIT y orden que allí en vez de en el código.

Answer 2

Sus opciones:

1. Hacer un linear buscar, el mantenimiento de los N primeros pesos encuentran a lo largo del camino. Esto debería ser más rápido que ordenar una lista lengthly si, por alguna razón, no se puede volver a utilizar los resultados de la clasificación entre la visualización de la página (por ejemplo, la lista está cambiando rápidamente).

   ACTUALIZACIÓN: mi error en la búsqueda lineal necesariamente ser mejor que la clasificación. Véase el artículo de Wikipedia " Selection_algorithm - Selección de k más pequeños o más grandes elementos " para obtener mejores algoritmos de selección.

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

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

4. Usar una estructura de datos que mantiene ordenada peso orden para usted: prioridad de la cola , conjunto de árbol , etc. también podría crear su propia estructura de datos.

5. mantener manualmente un segundo (posiblemente peso ordenada) estructura de datos de los elementos de la parte superior N. Esta estructura de datos se actualiza cada vez que la estructura de datos original se modificó. Usted puede crear su propia estructura de datos para envolver la lista original y este "N caché superior" juntos.

Answer 3

Se puede usar un max-heap.

Si se origina su datos desde una base de datos, ponen un índice en esa columna y utilizar ORDER BY y TOP o limitar a buscar sólo los registros que necesita para mostrar.

Answer 4

prioridad cola.

Answer 5

dólar :

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

Desde que dice la lista de elementos a partir del cual extraer estos subir N puede ser de cualquier tamaño, y por lo tanto puede ser grande asumo, me aumentan las respuestas simples sort() anteriores (que son totalmente apropiado para la entrada de tamaño razonable ) sugiriendo la mayor parte del trabajo aquí es encontrar la parte superior N - a continuación, clasificando los 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í (a min-montón) está delimitada al menos en tamaño. No hay necesidad real de hacer un montón de todos sus artículos.

Answer 7

No, no realmente. Al menos no mediante los métodos incorporados en Java.

Hay maneras inteligentes para obtener la N número más alto (o más bajo) de los elementos de una lista más rápido que una operación O(n*log(n)), pero que requieren que codificar esta solución a mano. Si el número de artículos se mantiene relativamente baja (no más de un par de cientos), su clasificación utilizando Collections.sort() y luego agarrar los números de la parte superior N es el camino a seguir de la OMI.

Answer 8

Depende de cuántas. Permite definir n como el número total de claves, y m como el número que desea que se vea.
Clasificar 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 a m
? Si m < log n, la exploración será más eficiente.
De lo contrario, m >= log n, que medios de clasificación será mejor. (Dado que para el caso borde de m = log n En realidad, no importa, pero la clasificación también le dará el beneficio de, bueno, la clasificación de la matriz, que siempre es agradable.

Answer 9

Si el tamaño de la lista es N, y el número de artículos a ser recuperada es K, necesita llamar Heapify en la lista, que convierte la lista (la que tiene que ser indexable, por ejemplo, una matriz) en una prioridad cola. (Véase la 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) realiza O (lg N) tiempo. Por lo que su tiempo total sería:

O (N + k lg N)

que es mejor que O (N lg N) k suponiendo es mucho menor que N.

Answer 10

Si mantener una matriz ordenada o el uso de una estructura de datos diferente no es una opción, usted podría intentar algo como lo siguiente. El tiempo de O es similar a la clasificación de la gran matriz, pero en la práctica esto debe 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.