Discussion :

[Oberown]

J'ai une liste de nombre non triée.
Je voudrais récuperer les n nombres plus grands triés.

Quel est la méthode la plus optimisé ?

Voici une idée
J'ai une liste qui reçoit les valeurs les plus grandes de taille n.
Je met les n premiers éléments dedans de ma liste. Je les trie (avec un quicksort par exemple).
Je parcours ma liste non trié et si je trouve un élément plus grand je la met au bon endroit dans ma liste de réponse, en éliminant dans ma liste le nombre le plus petit.

[Nemerle]

pourquoi ne pas partir d'une liste vide, et de ne pas dépasser la taille n ?

[Fortran90]

Je ne sais pas si ta solution avec ton tableau intermédiaire est une bonne idée. Au pire des cas tu peux t'amener à un cas ou tu devras faire un quicksort pour ton tableau intermédiaire puis un tri par insertion à chaque itération . Tu pourrais aussi refaire un quicksort, mais sur une liste triée c pas terrible ^^

Le plus simple et plus économique quelque soit le cas: quicksort sur tout ton tableau puis récupération immédiate des derniers éléments du tableau.

Rappel, dans le pire des cas:
Quick sort en NlogN
Tri par insertion N²

[PRomu@ld]

Rappel, dans le pire des cas:
Quick sort en NlogN
Tri par insertion N²

Pardon ?

depuis quand un quick sort a une complexité dans le pire des cas en O(n log n) ? Il s'agit de la meilleure complexité et de la complexité en moyenne. Pour avoir du 0(n log n) constant (meilleure, moyenne, pire), il faut utiliser un autre algo (tri par tas par exemple).

Tu peux obtenir un truc en n log n sans avoir à trier ton tableau. Le tout est de construire un tas (binomial par exemple) à partir de tes nombres.

Si tu pars d'une liste à M nombre, la complexité globale de l'algo est :

O( M log M ) + O(n log M)

O( M log M) pour la construction du tas.
O( n log M) pour la récupération des n plus grand nombres.

C'est peut-être extrème comme méthode (mais néanmoins un bon exercice d'algorithmique ).

La solution de base de trier ton tableau puis d'extraire les n plus grands éléments devrait suffire.

Si tu dois faire ça à partir d'un flot de donnée, le tout est de maintenir à jour le tableau des n plus grand éléments. En gros la méthode est simple : tu compare l'élément courant avec le plus petit élément de ton tableau, s'il est plus petit alors tu passes à l'élément du flot suivant, sinon, tu l'insère dans ton tableau (insertion dans un tableau trié en log(n) ). L'algo devrait être en O( M log(n) ) dans le pire des cas, ce qui est sensiblement meilleur que les autres solutions.

[pseudocode]

Pardon ?

depuis quand un quick sort a une complexité dans le pire des cas en O(n log n) ? Il s'agit de la meilleure complexité et de la complexité en moyenne. Pour avoir du 0(n log n) constant (meilleure, moyenne, pire), il faut utiliser un autre algo (tri par tas par exemple).

1. verifier que le tableau n'est pas (partiellement) trié -> o(n)
2. melanger (partiellement) le tableau -> o(n)
3. faire un quicksort -> o(n log n)

total o(2n+ n log n)

[Nemerle]

que de gens prolixes!!!

au fait, que veut dire o(...)?

[PRomu@ld]

Pour un matheux comme toi, je pensais que tu la connaissais

http://www.developpez.net/forums/sho...57&postcount=5

[PRomu@ld]

1. verifier que le tableau n'est pas (partiellement) trié -> o(n)
2. melanger (partiellement) le tableau -> o(n)
3. faire un quicksort -> o(n log n)

total o(2n+ n log n)

En moyenne, oui, mais ça repose sur un mélange randomisé du tableau ce qui ne te garanti pas que le tableau ne sera pas trié (Murphy quand tu nous tiens ). Dans le pire des cas, on est toujours en O( n^2 ) il me semble.

[pseudocode]

En moyenne, oui, mais ça repose sur un mélange randomisé du tableau ce qui ne te garanti pas que le tableau ne sera pas trié (Murphy quand tu nous tiens ). Dans le pire des cas, on est toujours en O( n^2 ) il me semble.

heu non... le "melange partiel" n'est pas totalement aleatoire. Par exemple, si "i" est pair tu swap T[i] et T[i+1] si T[i]>T[i+1], et l'inverse is "i" est impair.

Et puisque Nemerle est la, il va nous dire quelle est la proba qu'un melange aleatoire nous donne un tableau trié.

[Jedai]

Quel est la méthode la plus optimisé ?

La méthode de PRomu@ld n'est pas mauvaise, même si il n'utilise pas la bonne structure (l'insertion dans un tableau trié est en O(n), pas O(log(n)) même si la recherche de la place où insérer est effectivement en O(log(n)), il faut utiliser un tas).

Le mieux qu'on puisse faire est du O(M + n * log(n)), en faisant un quicksort partiel et en assumant un "bon" choix de pivot à chaque étape. Dans un langage paresseux comme Haskell, tu n'as même pas besoin de coder explicitement ce quicksearch, pourvu que ton quicksort soit suffisament paresseux, comme expliqué dans ce mail. En particulier dans ton cas (car je doute malheureusement que tu utilises Haskell), ce mail donne aussi un lien vers une excellente source sur ton problème : l'article Wikipedia sur la question.

--
Jedaï

[PRomu@ld]

La méthode de PRomu@ld n'est pas mauvaise, même si il n'utilise pas la bonne structure (l'insertion dans un tableau trié est en O(n), pas O(log(n)) même si la recherche de la place où insérer est effectivement en O(log(n)), il faut utiliser un tas).

Méa culpa. Je pensais tas et j'écris tableau. (en fait même pas un tas mais un arbre équilibré pour pouvoir extraire les plus grands éléments en O(n) et pas en O(n log n), mais bon, passons)

J'ai l'impression que nous nous sommes égarés, Oberown ne nous a pas répondu, il a surement une solution à son problème dans nos réponses. S'il veut plus, il n'aura qu'à nous dire ce qu'il cherche.

[Jedai]

en fait même pas un tas mais un arbre équilibré pour pouvoir extraire les plus grands éléments en O(n) et pas en O(n log n), mais bon, passons

Pour extraire le plus grand élément dans un arbre équilibré, c'est du O(log n) comme dans un tas, non ? Comment parviens-tu à un temps total en O(n) alors que tu dois retirer O(M) plus grand élément au pire ? Je ne suis sûr de comprendre ?

--
Jedaï

[PRomu@ld]

Je ne veux pas l'extraire, seulement lire les n plus grand

En fait, en mettant à jour (à partir de tes M valeurs) l'arbre de façon à avoir seulement n valeurs (les n plus grandes), tu te retrouves en fin de la première étape de l'algorithme avec un arbre binaire de recherche à n valeurs, pour les récupérer dans l'ordre, un simple parcours suffit (en 0(n) donc), ce qui est plus rapide qu'avec un tas (puisque tu es obligé d'extraire les n valeurs pour les avoir dans l'ordre).

[Jedai]

Je ne veux pas l'extraire, seulement lire les n plus grand

En fait, en mettant à jour (à partir de tes M valeurs) l'arbre de façon à avoir seulement n valeurs (les n plus grandes), tu te retrouves en fin de la première étape de l'algorithme avec un arbre binaire de recherche à n valeurs, pour les récupérer dans l'ordre, un simple parcours suffit (en 0(n) donc), ce qui est plus rapide qu'avec un tas (puisque tu es obligé d'extraire les n valeurs pour les avoir dans l'ordre).

Effectivement, je n'avais pas vu ça. Evidemment ça ne change pas la complexité globale de l'algorithme, mais peut-être que ça améliore un peu l'efficacité réelle.

--
Jedaï

[PRomu@ld]

Effectivement, je n'avais pas vu ça. Evidemment ça ne change pas la complexité globale de l'algorithme, mais peut-être que ça améliore un peu l'efficacité réelle.

Franchement, passer d'un n log n à n sur des valeurs faibles, c'est relativment peu important qui plus est étant donné que n << M (sinon autant faire un tri sur le tableau directement).

[alex_pi]

Si le but est de sortir les n premiers dans l'ordre, il est évident qu'il n'y a pas de solution linéaire. Si c'était le cas, en prenant n le nombre d'élément de la liste, on aurait un algo de tri en temps linéaire, ce qui est impossible dans le cas général.

Et même si ce n'est pas dans l'ordre, je ne pense pas que ce soit possible en temps linéaire. En effet, si c'était le cas, en déterminant ensuite le plus grand élément de l'ensemble (facilement faisable en temps linéaire), on obtiendrait le n ieme plus grand élément d'une liste en temps linéaire, et je pense que c'est impossible (mais là je suis moins catégorique que pour le tri)

Par contre je peux te proposer un algo probabiliste si tu veux :-)

[Nemerle]

Pour un matheux comme toi, je pensais que tu la connaissais

http://www.developpez.net/forums/sho...57&postcount=5

si je la connaissais bien sûr... maintenant, que penser de

verifier que le tableau n'est pas (partiellement) trié -> o(n)
2. melanger (partiellement) le tableau -> o(n)
3. faire un quicksort -> o(n log n)

total o(2n+ n log n)

[PRomu@ld]

Dès que ça fait appel à de l'aléatoire, je reste extrêmement prudent. Mais si vous voulez bien, on va essayer de ne pas trop se disperser, si vous voulez continuer à discuter sur ce sujet, il faudra soit que le principal intéressé en ait vraiment besoin, soit ouvrir un nouveau sujet.

Merci à vous