Extrahieren einer gegebenen Anzahl der höchsten Werte in einer Liste

Question

Ich suche eine feste Anzahl von Elementen auf einer Webseite entsprechend ihrem jeweiligen Gewicht (dargestellt durch eine Integer) angezeigt werden soll. Die Liste, wo diese Elemente gefunden werden, kann jede Größe von praktisch sein.

Die erste Lösung, die den Sinn kommt, ist eine Collections.sort() zu tun, und die Elemente nacheinander, indem Sie durch die List zu bekommen. Gibt es eine elegantere Lösung obwohl das verwendet werden könnte, um vorzubereiten, zu sagen, die besten acht Einzelteile?

Answer 1

Just for Collections.sort(..) gehen. Es ist effizient genug.

  

Dieser Algorithmus bietet garantiert n log (n) Leistung.

Sie können versuchen, etwas effizienter zu implementieren für Ihren konkreten Fall , wenn Sie einige besondere Eigenschaften Ihrer Liste wissen, aber das ist nicht gerechtfertigt wäre. Außerdem, wenn Sie Ihre Liste aus einer Datenbank kommt, zum Beispiel, können Sie LIMIT it & um sie dort statt im Code.

Answer 2

Ihre Optionen:

1. Führen Sie eine linear suchen, die Aufrechterhaltung der Top-N Gewichte auf dem Weg gefunden. Dies sollte schneller sein als eine lengthly Liste Sortierung, wenn aus irgendeinem Grund, können Sie nicht die Sortierergebnisse wiederzuverwenden zwischen die Seite angezeigt wird (zum Beispiel die Liste ändert sich schnell).

   UPDATE: Ich korrigiert stehen auf der linearen Suche notwendigerweise besser zu sein als zu sortieren. Siehe Wikipedia-Artikel „ Selection_algorithm - Auswählen von k kleinsten oder größten Elemente “ für eine bessere Auswahl-Algorithmen.

2. manuell pflegt einen List (das Original oder einen parallelen one) sortierte in Gewicht Reihenfolge. Sie können Methoden wie Collections.binarySearch () zu bestimmen, wo jedes neue Element eingefügt werden.

3. Pflegen eine List (das Original oder ein paralleles eins) in Gewichts Reihenfolge sortierte durch Aufruf Collections.sort () nach jeder Änderung, batch Modifikationen oder kurz vor dem Display ( möglicherweise eine Modifikation Flagge Aufrechterhaltung einer bereits sortierten Liste zu vermeiden Sortierung).

4. Verwenden Sie eine Datenstruktur, die für Sie sortieren Gewicht Ordnung hält: Prioritätswarteschlange ,

   könnten Sie verwenden einen max-heap .

   Wenn Sie Ihre Daten stammen aus einer Datenbank, einen Index auf dieser Spalte setzen und ORDER BY und TOP oder LIMIT zu holen verwendet nur die Datensätze, die Sie anzeigen müssen.

Oder eine Prioritätswarteschlange .

Dollar :

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

ohne Dollar verwenden Sie es mit sort() Collections.sort() sollten, erhalten dann die ersten n Elemente mit list.sublist(0, n).

Da Sie die Liste der Elemente sagen, aus dem diese oben zu extrahieren N jeder Größe sein kann und so sein kann, große Ich gehe davon aus, würde ich die einfachen sort() Antworten oben (vergrößern, die für angemessen großen Eingangs ganz angemessen sind ), indem Sie hier die meiste Arbeit darauf hindeutet, ist die Top-N zu finden - dann diejenigen N ist trivial zu sortieren. Das heißt:

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

Der Haufen hier (a min-heap) zumindest in der Größe begrenzt. Es gibt keinen wirklichen Bedarf einen Haufen aus allen Ihren Einzelteilen zu machen.

Nein, nicht wirklich. Zumindest nicht mit Java integrierten Methoden.

Es gibt clevere Möglichkeiten, um die höchste (oder niedrigsten) N Anzahl von Elementen aus einer Liste schneller als ein O(n*log(n)) Betrieb zu bekommen, aber das erfordert, dass Sie diese Lösung mit der Hand zu kodieren. Wenn die Anzahl der Elemente bleibt relativ niedrig (nicht mehr als ein paar hundert), sortieren sie Collections.sort() verwenden und dann die Top-N-Nummern greifen ist der Weg, IMO zu gehen.

Abhängig von, wie viele. Lets n als die Gesamtzahl der Schlüssel definieren, und m als Zahl, die Sie anzeigen möchten.
Sortieren der ganzen Sache: O(nlogn)
Abtasten der Anordnung jedes Mal für die nächsthöhere Nummer: O(n*m)
Die Frage ist also - Was ist die Beziehung zwischen n zu m
? Wenn m < log n, wird der Scanvorgang effizienter.
Andernfalls m >= log n, die besser werden Mittel zu sortieren. (Da für den Randfall m = log n tut es eigentlich nicht Materie, sondern Sortierung werden Sie auch den Vorteil, na ja, das Array sortiert wird, das ist immer schön.

Wenn die Größe der Liste ist N, und die Anzahl der Elemente abgerufen werden soll, K, müssen Sie Heapify auf der Liste nennen, die die Liste umwandelt (die Wende sein muss, zum Beispiel eines Array) in eine Priorität Warteschlange. (Siehe heapify Funktion in http://en.wikipedia.org/wiki/Heapsort )

ein Element Suchen auf der Spitze des Haufens (der max Artikel) nimmt O (lg N) Zeit. So Ihre Gesamtzeit wäre:

O (N + k lg N)

, die besser ist, als O (N lg N) unter der Annahme, k viel kleiner als N ist.

Wenn ein sortiertes Array zu halten oder eine andere Datenstruktur ist keine Option, könnten Sie so etwas wie die folgenden versuchen. Die O-Zeit ist ähnlich dem großen Array Sortierung aber in der Praxis sollte dies effizienter sein.

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 könnte ein Objekt sein [] und die innere Schleife mit Swapping anstatt wirklich geschehen könnte Entfernen und Einsetzen in eine Anordnung.

Answer 3

Answer 4

Answer 5

Answer 6

Answer 7

könnten Sie verwenden einen

Answer 8

Oder eine Prioritätswarteschlange .

Answer 9

Dollar :

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

ohne Dollar verwenden Sie es mit sort() Collections.sort() sollten, erhalten dann die ersten n Elemente mit list.sublist(0, n).

Answer 10

Da Sie die Liste der Elemente sagen, aus dem diese oben zu extrahieren N jeder Größe sein kann und so sein kann, große Ich gehe davon aus, würde ich die einfachen sort() Antworten oben (vergrößern, die für angemessen großen Eingangs ganz angemessen sind ), indem Sie hier die meiste Arbeit darauf hindeutet, ist die Top-N zu finden - dann diejenigen N ist trivial zu sortieren. Das heißt:

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

Der Haufen hier (a min-heap) zumindest in der Größe begrenzt. Es gibt keinen wirklichen Bedarf einen Haufen aus allen Ihren Einzelteilen zu machen.

Answer 11

Nein, nicht wirklich. Zumindest nicht mit Java integrierten Methoden.

Es gibt clevere Möglichkeiten, um die höchste (oder niedrigsten) N Anzahl von Elementen aus einer Liste schneller als ein O(n*log(n)) Betrieb zu bekommen, aber das erfordert, dass Sie diese Lösung mit der Hand zu kodieren. Wenn die Anzahl der Elemente bleibt relativ niedrig (nicht mehr als ein paar hundert), sortieren sie Collections.sort() verwenden und dann die Top-N-Nummern greifen ist der Weg, IMO zu gehen.

Answer 12

Abhängig von, wie viele. Lets n als die Gesamtzahl der Schlüssel definieren, und m als Zahl, die Sie anzeigen möchten.
Sortieren der ganzen Sache: O(nlogn)
Abtasten der Anordnung jedes Mal für die nächsthöhere Nummer: O(n*m)
Die Frage ist also - Was ist die Beziehung zwischen n zu m
? Wenn m < log n, wird der Scanvorgang effizienter.
Andernfalls m >= log n, die besser werden Mittel zu sortieren. (Da für den Randfall m = log n tut es eigentlich nicht Materie, sondern Sortierung werden Sie auch den Vorteil, na ja, das Array sortiert wird, das ist immer schön.

Answer 13

Wenn die Größe der Liste ist N, und die Anzahl der Elemente abgerufen werden soll, K, müssen Sie Heapify auf der Liste nennen, die die Liste umwandelt (die Wende sein muss, zum Beispiel eines Array) in eine Priorität Warteschlange. (Siehe heapify Funktion in http://en.wikipedia.org/wiki/Heapsort )

ein Element Suchen auf der Spitze des Haufens (der max Artikel) nimmt O (lg N) Zeit. So Ihre Gesamtzeit wäre:

O (N + k lg N)

, die besser ist, als O (N lg N) unter der Annahme, k viel kleiner als N ist.

Answer 14

Wenn ein sortiertes Array zu halten oder eine andere Datenstruktur ist keine Option, könnten Sie so etwas wie die folgenden versuchen. Die O-Zeit ist ähnlich dem großen Array Sortierung aber in der Praxis sollte dies effizienter sein.

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 könnte ein Objekt sein [] und die innere Schleife mit Swapping anstatt wirklich geschehen könnte Entfernen und Einsetzen in eine Anordnung.