L'estrazione di un certo numero di valori più alti in un elenco

Question

Sto cercando di visualizzare un numero fisso di elementi su una pagina web in base al loro rispettivo peso (rappresentata da un Integer). La lista in cui si trovano questi elementi può essere di qualsiasi dimensione.

La prima soluzione che viene in mente è quello di fare un Collections.sort() e per ottenere gli articoli uno per uno per passare attraverso il List. C'è una soluzione più elegante, tuttavia, che potrebbero essere utilizzati per preparare, ad esempio, i primi otto articoli?

Answer 1

Basta andare per Collections.sort(..). E 'abbastanza efficiente.

  

Questa offerta algoritmo garantito n log (n) le prestazioni.

possono cercare di implementare qualcosa di più efficiente per il vostro caso concreto se si conoscono alcune proprietà distintive della tua lista, ma che sarebbe non essere giustificato. Inoltre, se la vostra lista proviene da un database, per esempio, è possibile LIMIT it & ordine lì invece che in codice.

Answer 2

Le opzioni disponibili:

1. Fare un linear cercare, mantenendo le prime N pesi trovano lungo la strada. Questo dovrebbe essere più veloce di ordinamento di un elenco lengthly se, per qualche motivo, non è possibile riutilizzare i risultati di ordinamento tra la visualizzazione della pagina (ad esempio, la lista sta cambiando rapidamente).

   UPDATE: Io correggo sulla ricerca lineare necessariamente meglio di ordinamento. Vedere articolo Wikipedia " Selection_algorithm - Selezione k più piccoli o più grandi elementi " per una migliore algoritmi di selezione.

2. mantenere manualmente un List (quella originale o uno parallelo) disposto in ordine di peso. È possibile utilizzare metodi come Collections.binarySearch () per determinare dove inserire ogni nuovo elemento.

3. Mantenere una List (quella originale o uno parallelo) ordinati in ordine di peso chiamando Collections.sort () dopo ogni modifica, modifiche batch o appena prima visualizzazione ( possibilmente mantenendo un flag di modifica per evitare classificare un elenco già ordinato).

4. Utilizza una struttura di dati che mantiene ordinato il peso-ordine per voi: priorità della coda , albero set , ecc Si potrebbe anche creare la propria struttura dei dati.

5. mantenere manualmente un secondo (possibilmente peso-ordinato) struttura dati degli elementi superiore N. Questa struttura di dati viene aggiornata in qualsiasi momento la struttura di dati originale viene modificato. È possibile creare la propria struttura dei dati per avvolgere l'elenco originale e questo "cache top N" insieme.

Answer 3

Si potrebbe usare un max-heap .

Se i tuoi origine dati da un database, messo un indice su quella colonna e utilizzare ORDER BY e TOP o limitare per recuperare solo i record è necessario visualizzare.

Answer 4

priorità della coda .

Answer 5

dollaro :

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

senza utilizzare dollaro si dovrebbe sort() utilizzando Collections.sort(), quindi ottenere i primi n elementi utilizzando list.sublist(0, n).

Answer 6

Dal momento che dici l'elenco degli elementi da cui estrarre questi top N può essere di qualsiasi dimensione, e così può essere grande suppongo, mi piacerebbe aumentare le risposte semplici sort() di cui sopra (che sono del tutto appropriato per l'ingresso di dimensioni ragionevoli ) suggerendo la maggior parte del lavoro qui è trovare la parte superiore N - allora l'ordinamento coloro N è banale. Cioè:

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());

Il mucchio qui (un min-heap) è delimitata almeno in termini di dimensioni. Non c'è alcuna reale necessità di fare un mucchio di tutti i tuoi oggetti.

Answer 7

No, non proprio. Almeno non utilizzando metodi incorporato del Java.

Ci sono modi intelligenti per ottenere il più alto (o più basso) numero N di elementi da un elenco più veloce di un'operazione O(n*log(n)), ma che richiedono di codificare questa soluzione a mano. Se il numero di articoli soggiorni relativamente basso (non più di un paio di centinaia), l'ordinamento utilizzando Collections.sort() e poi afferrando i numeri superiore N è la strada da percorrere IMO.

Answer 8

Dipende da quanti. Consente di definire n come il numero totale di chiavi, e m come il numero che si desidera visualizzare.
Ordinamento l'intera cosa: O(nlogn)
Scansione l'array ogni volta per il prossimo numero più alto: O(n*m)
Quindi la domanda è - Qual è il rapporto tra n per m
? Se m < log n, la scansione sarà più efficiente.
Altrimenti, m >= log n, che significa smistamento sarà migliore. (Dal momento che per il caso limite di m = log n in realtà non importa, ma l'ordinamento vi darà anche il vantaggio di, beh, l'ordinamento della matrice, che è sempre bello.

Answer 9

Se la dimensione della lista è N, e il numero di elementi da recuperare è K, è necessario chiamare heapify sulla lista, che converte l'elenco (che deve essere indicizzabile, ad esempio una matrice) in una priorità coda. (Vedi funzione heapify in http://en.wikipedia.org/wiki/Heapsort )

Recupero di un oggetto sulla parte superiore del mucchio (la voce max) batte O (lg n). Così il vostro tempo complessivo potrebbe essere:

O (N + k lg N)

che è meglio di O (N lg N) supponendo k è molto più piccolo di N.

Answer 10

Se mantenere un array ordinato o utilizzando una struttura dati diversa non è un'opzione, si potrebbe provare qualcosa di simile alla seguente. Il tempo O è simile classificare il grande array ma in pratica questo dovrebbe essere più efficiente.

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 potrebbe essere un oggetto [] e il ciclo interno potrebbe essere fatto con scambio realtà invece di estrazione e inserimento in una matrice.