Un nombre donné extraire des valeurs les plus élevées dans une liste

Question

Je cherche à afficher un nombre fixe d'éléments sur une page Web en fonction de leur poids respectif (représenté par un Integer). La liste où ces objets sont trouvés peuvent être de toutes tailles.

La première solution qui vient à l'esprit est de faire un Collections.sort() et d'obtenir les éléments un par un en passant par le List. Y at-il une solution plus élégante mais qui pourrait être utilisé pour préparer, par exemple, les huit articles?

Answer 1

Il suffit d'aller pour Collections.sort(..). Il est assez efficace.

  

Cette performance offre algorithme garanti n log (n).

peut essayer de mettre en œuvre quelque chose de plus efficace pour votre cas concret si vous connaissez des propriétés distinctives de votre liste, mais ce ne serait pas justifiée. De plus, si votre liste provient d'une base de données, par exemple, vous pouvez LIMIT et il commande là au lieu de code.

Answer 2

Vos options:

1. Faites une linéaire recherche, en maintenant les principaux poids de N trouvé le long du chemin. Cela devrait être plus rapide que le tri d'une liste lengthly si, pour une raison quelconque, vous ne pouvez pas réutiliser les résultats de tri entre affichage de la page (par exemple, la liste change rapidement).

   Mise à jour: Je me suis trompé sur la recherche linéaire étant nécessairement meilleur que le tri. Voir article de Wikipédia « Selection_algorithm - Sélection k ou plus petits éléments » pour de meilleurs algorithmes de sélection.

2. manuellement maintenir un List (l'un ou l'une parallèle originale) triée par ordre de poids. Vous pouvez utiliser des méthodes comme Collections.binarySearch () afin de déterminer où insérer chaque nouvel élément.

3. Maintenir un List (l'un ou l'une parallèle originale) classés dans l'ordre de poids en appelant Collections.sort () après chaque modification, les modifications de commandes, ou juste avant l'affichage ( maintenant peut-être un indicateur de modification pour éviter le tri d'une liste déjà triée).

4. Utilisez une structure de données qui maintient le poids ordre de tri pour vous: file d'attente prioritaire ,

   Vous pouvez utiliser un max tas.

   Si vos données proviennent d'une base de données, mettre un index sur cette colonne et utiliser ORDER BY et TOP ou LIMIT chercher uniquement les enregistrements dont vous avez besoin à l'affichage.

Ou une file d'attente prioritaire .

dollar :

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

sans utiliser dollar, vous devriez sort() à l'aide Collections.sort(), puis obtenir les premiers éléments de n en utilisant list.sublist(0, n).

Puisque vous dites que la liste des éléments à partir desquels extraire ces top N peut être de toute taille, et ainsi peut être grande, je suppose, j'augment les réponses sort() de simples ci-dessus (qui sont tout à fait approprié pour l'entrée de taille raisonnable ) en suggérant la majeure partie du travail ici est de trouver le top N - puis le tri ceux N est trivial. C'est:

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

Le tas ici (a min tas) est délimitée au moins en taille. Il n'y a pas de réel besoin de faire un tas de tous vos articles.

Non, pas vraiment. Au moins ne pas utiliser les méthodes intégrées de Java.

Il existe des moyens intelligents pour obtenir le plus haut (ou plus bas) N nombre d'éléments d'une liste plus rapide qu'une opération de O(n*log(n)), mais cela vous obligera à coder cette solution à la main. Si le nombre de séjours d'articles relativement faible (pas plus de quelques centaines), le tri à l'aide Collections.sort() puis saisir les numéros de N supérieur est le chemin à parcourir l'OMI.

dépend du nombre. Permet de définir n que le nombre total de clés, et m comme le numéro que vous souhaitez afficher.
Tri de la chose entière: O(nlogn)
Numérisation du tableau à chaque fois que le plus grand nombre suivant: O(n*m)
La question est donc - Quelle est la relation entre n m à
? Si m < log n, la numérisation sera plus efficace.
Dans le cas contraire, m >= log n, ce qui signifie que le tri sera mieux. (Comme pour le cas de bord de m = log n il ne fait pas la matière, mais le tri vous donnera également l'avantage de bien, trier le tableau, ce qui est toujours agréable.

Si la taille de la liste est N, et le nombre d'éléments à récupérer est K, vous devez appeler Heapify sur la liste, qui convertit la liste (qui doit être indexable, par exemple un tableau) en une priorité queue. (Voir la fonction heapify http://en.wikipedia.org/wiki/Heapsort )

Récupération d'un objet sur le dessus du tas (le point max) tire O (lg n). Donc, votre temps global serait:

O (N + k lg N)

qui est mieux que O (N s N) en supposant que k est beaucoup plus petit que n.

Si la tenue d'un tableau trié ou en utilisant une structure de données différentes ne sont pas une option, vous pouvez essayer quelque chose comme ce qui suit. Le temps de O est similaire à trier le grand tableau, mais dans la pratique, cela devrait être plus efficace.

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 pourrait être un objet [] et la boucle intérieure peut être fait avec permutation au lieu de retirer et d'insérer effectivement dans un tableau.

Answer 3

Answer 4

Answer 5

Answer 6

Answer 7

Vous pouvez utiliser un

Answer 8

Ou une file d'attente prioritaire .

Answer 9

dollar :

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

sans utiliser dollar, vous devriez sort() à l'aide Collections.sort(), puis obtenir les premiers éléments de n en utilisant list.sublist(0, n).

Answer 10

Puisque vous dites que la liste des éléments à partir desquels extraire ces top N peut être de toute taille, et ainsi peut être grande, je suppose, j'augment les réponses sort() de simples ci-dessus (qui sont tout à fait approprié pour l'entrée de taille raisonnable ) en suggérant la majeure partie du travail ici est de trouver le top N - puis le tri ceux N est trivial. C'est:

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

Le tas ici (a min tas) est délimitée au moins en taille. Il n'y a pas de réel besoin de faire un tas de tous vos articles.

Answer 11

Non, pas vraiment. Au moins ne pas utiliser les méthodes intégrées de Java.

Il existe des moyens intelligents pour obtenir le plus haut (ou plus bas) N nombre d'éléments d'une liste plus rapide qu'une opération de O(n*log(n)), mais cela vous obligera à coder cette solution à la main. Si le nombre de séjours d'articles relativement faible (pas plus de quelques centaines), le tri à l'aide Collections.sort() puis saisir les numéros de N supérieur est le chemin à parcourir l'OMI.

Answer 12

dépend du nombre. Permet de définir n que le nombre total de clés, et m comme le numéro que vous souhaitez afficher.
Tri de la chose entière: O(nlogn)
Numérisation du tableau à chaque fois que le plus grand nombre suivant: O(n*m)
La question est donc - Quelle est la relation entre n m à
? Si m < log n, la numérisation sera plus efficace.
Dans le cas contraire, m >= log n, ce qui signifie que le tri sera mieux. (Comme pour le cas de bord de m = log n il ne fait pas la matière, mais le tri vous donnera également l'avantage de bien, trier le tableau, ce qui est toujours agréable.

Answer 13

Si la taille de la liste est N, et le nombre d'éléments à récupérer est K, vous devez appeler Heapify sur la liste, qui convertit la liste (qui doit être indexable, par exemple un tableau) en une priorité queue. (Voir la fonction heapify http://en.wikipedia.org/wiki/Heapsort )

Récupération d'un objet sur le dessus du tas (le point max) tire O (lg n). Donc, votre temps global serait:

O (N + k lg N)

qui est mieux que O (N s N) en supposant que k est beaucoup plus petit que n.

Answer 14

Si la tenue d'un tableau trié ou en utilisant une structure de données différentes ne sont pas une option, vous pouvez essayer quelque chose comme ce qui suit. Le temps de O est similaire à trier le grand tableau, mais dans la pratique, cela devrait être plus efficace.

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 pourrait être un objet [] et la boucle intérieure peut être fait avec permutation au lieu de retirer et d'insérer effectivement dans un tableau.