Garder les N meilleurs
Olivier Miakinen
J'ai un petit algorithme ￜ ￜcrire, et je ne sais pas comment le faire
pour qu'il soit efficace.
Voilￜ. J'ai une liste ordonnￜe d'objets possￜdant plusieurs attributs
(ou propriï¿œtï¿œs, ou variables, je ne sais pas quel est le terme le plus
appropriￜ), dont un nombre qui s'appelle ￜ score ￜ. Les objets ne sont
pas triï¿œs par score, et plusieurs objets peuvent avoir le mï¿œme score.
Je voudrais extraire de la liste N objets ayant les meilleurs scores.
En d'autres termes, je voudrais qu'il existe un score S tel que les N
objets choisis aient tous un score >= S, et que tous les objets non
choisis aient un score <= S. Parmi les objets de score ￜgal ￜ S s'il y
en a plusieurs, peu importe lesquels sont choisis et lesquels sont ï¿œliminï¿œs.
Pour fixer les idï¿œes, je devrais avoir quelques milliers d'objets au
total avant extraction de N d'entre eux, avec N aux alentours de 100.
Variante, dans le cas favorable oￜ les objets ne sont pas donnￜs ￜ
l'avance : je construis les objets un ￜ un et les place dans une liste.
Aprï¿œs avoir construit les N premiers objets, pour chaque nouvel objet
je peux calculer le score avant d'avoir tout construit. Je peux donc
dￜcider d'arrￜter de le construire si son score est infￜrieur ou ￜgal ￜ
ceux des N dￜjￜ dans la liste, ou au contraire le terminer, l'ajouter ￜ
la liste, et supprimer l'un de ceux qui ont le plus petit score.
Auriez-vous des idï¿œes pour traiter ces deux cas, ou simplement des
critï¿œres de recherche pour trouver les algos correspondants sur la
toile via un moteur de recherche ?
Cordialement,
--
Olivier Miakinen
Mehdi Tibouchi
>
> Je voudrais extraire de la liste N objets ayant les meilleurs scores.
> En d'autres termes, je voudrais qu'il existe un score S tel que les N
> objets choisis aient tous un score >= S, et que tous les objets non
> en a plusieurs, peu importe lesquels sont choisis et lesquels sont �limin�s.
>
> Pour fixer les id�es, je devrais avoir quelques milliers d'objets au
> total avant extraction de N d'entre eux, avec N aux alentours de 100.
Pour ces ordres de grandeur, � moins que la m�moire soit extr�mement
contrainte, il me semble que l'algorithme consistant � trier puis prendre
les N premiers est largement assez efficace, non�? (Pas besoin de faire
de copie bien s�r�--�il est possible par exemple de trier une liste de
couples (score, r�f�rence sur l'objet correspondant)).
> Variante, dans le cas favorable o� les objets ne sont pas donn�s �
> l'avance : je construis les objets un � un et les place dans une liste.
> Apr�s avoir construit les N premiers objets, pour chaque nouvel objet
> je peux calculer le score avant d'avoir tout construit. Je peux donc
> d�cider d'arr�ter de le construire si son score est inf�rieur ou �gal �
> ceux des N d�j� dans la liste, ou au contraire le terminer, l'ajouter �
> la liste, et supprimer l'un de ceux qui ont le plus petit score.
Faire exactement �a, mais en rangeant les objets construits dans un arbre
binaire de recherche plut�t qu'une liste�?
Jean-Marc Bourguet
Un tas (celui du heap sort) tri� de sorte que sa t�te soit le plus petit
�l�ment dans lequel tu ne laisses que N �l�ments. Tu enl�ves la t�te et tu
ajoutes le nouvel �l�ment si il est plus grand que la t�te.
A+
--
Jean-Marc
Site de usenet-fr: http://www.usenet-fr.news.eu.org
zwim
Mehdi Tibouchi a �crit
>>
>> Je voudrais extraire de la liste N objets ayant les meilleurs scores.
>> En d'autres termes, je voudrais qu'il existe un score S tel que les N
>> objets choisis aient tous un score >= S, et que tous les objets non
>> choisis aient un score <= S. Parmi les objets de score �gal � S s'il y
>> en a plusieurs, peu importe lesquels sont choisis et lesquels sont �limin�s.
>>
>> Pour fixer les id�es, je devrais avoir quelques milliers d'objets au
>> total avant extraction de N d'entre eux, avec N aux alentours de 100.
>
>Pour ces ordres de grandeur, � moins que la m�moire soit extr�mement
>contrainte, il me semble que l'algorithme consistant � trier puis prendre
>les N premiers est largement assez efficace, non�? (Pas besoin de faire
>de copie bien s�r�--�il est possible par exemple de trier une liste de
>couples (score, r�f�rence sur l'objet correspondant)).
A priori pas besoin de trier enti�rement, par exemple quicksort est un
algo � pivot qui range les �l�ments plus grands que le pivot dans une
premi�re partie de tableau et le reste dans la seconde moiti�.
Donc en appliquant un quicksort partiel, on devrait se retrouver assez
vite avec N �l�ments en d�but de tableau plus grands que le reste.
>> Variante, dans le cas favorable o� les objets ne sont pas donn�s �
>> l'avance : je construis les objets un � un et les place dans une liste.
>> Apr�s avoir construit les N premiers objets, pour chaque nouvel objet
>> je peux calculer le score avant d'avoir tout construit. Je peux donc
>> d�cider d'arr�ter de le construire si son score est inf�rieur ou �gal �
>> ceux des N d�j� dans la liste, ou au contraire le terminer, l'ajouter �
>> la liste, et supprimer l'un de ceux qui ont le plus petit score.
>
>Faire exactement �a, mais en rangeant les objets construits dans un arbre
>binaire de recherche plut�t qu'une liste�?
--
zwim.
Rien n'est impossible que la mesure de la volont� humaine...
Olivier Miakinen
Le 11/10/2009 15:56, Mehdi Tibouchi a ï¿œcrit :
>>
>> Pour fixer les idï¿œes, je devrais avoir quelques milliers d'objets au
>> total avant extraction de N d'entre eux, avec N aux alentours de 100.
>
> Pour ces ordres de grandeur, ￜ moins que la mￜmoire soit extrￜmement
> contrainte, il me semble que l'algorithme consistant ￜ trier puis prendre
> les N premiers est largement assez efficace, non ? (Pas besoin de faire
> de copie bien sï¿œr -- il est possible par exemple de trier une liste de
> couples (score, rï¿œfï¿œrence sur l'objet correspondant)).
La mￜmoire n'est pas trￜs contrainte, non. Je n'avais pas pensￜ ￜ la
possibilitￜ de trier des rￜfￜrences au lieu des objets eux-mￜmes : il
faut dire que je n'ai jamais eu ce genre de besoin. En tout cas, ï¿œa me
semble une trï¿œs bonne idï¿œe.
>> Variante, dans le cas favorable oￜ les objets ne sont pas donnￜs ￜ
>> l'avance : [...]
>
> Faire exactement ï¿œa, mais en rangeant les objets construits dans un arbre
> binaire de recherche plutï¿œt qu'une liste ?
Je pourrais faire ï¿œa dans un second temps, si je le code en C ou en C++.
Mais dans un premier temps je le fais en PHP, et j'aime autant utiliser
les fonctions dￜjￜ codￜes en C, pour des raisons de performances. Or je
ne vois pas de gestion d'arbre binaire dans les fonctions de base.
Merci en tout cas pour les idï¿œes !
--
Olivier Miakinen
Olivier Miakinen
> Un tas (celui du heap sort) triￜ de sorte que sa tￜte soit le plus petit
> ï¿œlï¿œment dans lequel tu ne laisses que N ï¿œlï¿œments. Tu enlï¿œves la tï¿œte et tu
> ajoutes le nouvel ï¿œlï¿œment si il est plus grand que la tï¿œte.
Je ne connais pas ce tri (d'ailleurs je n'en connais aucun ￜ vrai dire)
mais j'ai commencￜ ￜ lire <http://fr.wikipedia.org/wiki/Tri_par_tas>
pour essayer de comprendre.
Merci !
--
Olivier Miakinen
Olivier Miakinen
>
> A priori pas besoin de trier entiï¿œrement, par exemple quicksort est un
> algo ￜ pivot qui range les ￜlￜments plus grands que le pivot dans une
> premiￜre partie de tableau et le reste dans la seconde moitiￜ.
>
> Donc en appliquant un quicksort partiel, on devrait se retrouver assez
Oui, ï¿œa semble assez prometteur, et je vais lire aussi la page sur le
tri rapide <http://fr.wikipedia.org/wiki/Tri_rapide>.
Merci ￜ toi !
--
Olivier Miakinen
zwim
Olivier Miakinen a �crit
>Bonjour,
>
>J'ai un petit algorithme � �crire, et je ne sais pas comment le faire
>pour qu'il soit efficace.
>
>
>(ou propri�t�s, ou variables, je ne sais pas quel est le terme le plus
>appropri�), dont un nombre qui s'appelle � score �. Les objets ne sont
>pas tri�s par score, et plusieurs objets peuvent avoir le m�me score.
>
>Je voudrais extraire de la liste N objets ayant les meilleurs scores.
>En d'autres termes, je voudrais qu'il existe un score S tel que les N
>objets choisis aient tous un score >= S, et que tous les objets non
>en a plusieurs, peu importe lesquels sont choisis et lesquels sont �limin�s.
>
>total avant extraction de N d'entre eux, avec N aux alentours de 100.
>
>
>l'avance : je construis les objets un � un et les place dans une liste.
>Apr�s avoir construit les N premiers objets, pour chaque nouvel objet
>je peux calculer le score avant d'avoir tout construit. Je peux donc
>la liste, et supprimer l'un de ceux qui ont le plus petit score.
>
>
>crit�res de recherche pour trouver les algos correspondants sur la
>toile via un moteur de recherche ?
>
>Cordialement,
Voil� qui confirme ce qu'on a dit tous les 3 ;-)
Michel Olagnon
> Le Sun, 11 Oct 2009 15:56:30 +0200
> Mehdi Tibouchi a �crit
>
>>Olivier Miakinen wrote in message <4ad1...@meta.neottia.net>:
>>
>>>Je voudrais extraire de la liste N objets ayant les meilleurs scores.
>>>En d'autres termes, je voudrais qu'il existe un score S tel que les N
>>>objets choisis aient tous un score >= S, et que tous les objets non
>>>choisis aient un score <= S. Parmi les objets de score �gal � S s'il y
>>>en a plusieurs, peu importe lesquels sont choisis et lesquels sont �limin�s.
>>>
>>>Pour fixer les id�es, je devrais avoir quelques milliers d'objets au
>>>total avant extraction de N d'entre eux, avec N aux alentours de 100.
>>
>>Pour ces ordres de grandeur, � moins que la m�moire soit extr�mement
>>contrainte, il me semble que l'algorithme consistant � trier puis prendre
>>les N premiers est largement assez efficace, non ? (Pas besoin de faire
>>de copie bien s�r -- il est possible par exemple de trier une liste de
>>couples (score, r�f�rence sur l'objet correspondant)).
>
>
> A priori pas besoin de trier enti�rement, par exemple quicksort est un
> algo � pivot qui range les �l�ments plus grands que le pivot dans une
> premi�re partie de tableau et le reste dans la seconde moiti�.
>
> Donc en appliquant un quicksort partiel, on devrait se retrouver assez
> vite avec N �l�ments en d�but de tableau plus grands que le reste.
>
C'est en effet ce que je fais.
http://www.fortran-2000.com/rank/index.html
>
>>>Variante, dans le cas favorable o� les objets ne sont pas donn�s �
>>>l'avance : je construis les objets un � un et les place dans une liste.
>>>Apr�s avoir construit les N premiers objets, pour chaque nouvel objet
>>>je peux calculer le score avant d'avoir tout construit. Je peux donc
>>>d�cider d'arr�ter de le construire si son score est inf�rieur ou �gal �
>>>ceux des N d�j� dans la liste, ou au contraire le terminer, l'ajouter �
>>>la liste, et supprimer l'un de ceux qui ont le plus petit score.
>>
>>Faire exactement �a, mais en rangeant les objets construits dans un arbre
>>binaire de recherche plut�t qu'une liste ?
>
>
N aux alentours de 100 me parait un peu eleve pour appliquer ce genre
de methode, qui ressemble a un tri insertion incomplet, que j'aurais plutot
vu meilleur seulement pour N inferieur a 20 ou moins encore.
Olivier Miakinen
>
> Voilￜ qui confirme ce qu'on a dit tous les 3 ;-)
>
> http://stackoverflow.com/questions/814186/c-efficient-algorithm-to-find-greatest-m-elements-in-an-n-x-n-matrix
En effet. Encore merci ￜ tous les trois, ainsi qu'ￜ Michel Olagnon.
JLH974
Juste un point qui peut sembler secondaire mais j'adore couper les cheveux
en 2^10 ;-)
Sï¿œlectionner les N meilleurs peut dï¿œboucher sur un problï¿œme insoluble
surtout si on prï¿œcise que plusieurs "candidats" peuvent avoir le mï¿œme score.
Le tri par ordre classe les "candidats" par ordre dï¿œcroissant et le
programme doit sï¿œlectionner tous les candidats ayant le mï¿œme rang.
Pour prendre un exemple plus parlant : Soit ￜ sￜlectionner les 4 meilleurs
scores parmi un ensemble composￜ de :
1 candidat ayant le score 100 (par exemple)
2 candidats ayant le score 80
3 candidats ayant le score 70
Et lￜ... catastrophe...
En conclusion : si on veut sï¿œlectionner N meilleurs scores dans un ensemble
oￜ plusieurs candidats peuvent avoir le mￜme score, il faut obligatoirement
un autre critï¿œre pour dï¿œpartager les ex-aequo
JLH
"Olivier Miakinen" <om+...@miakinen.net> a ï¿œcrit dans le message de
news:4ad2...@meta.neottia.net...
Olivier Miakinen
Le 19/10/2009 18:12, JLH974 a ï¿œcrit :
>
> Juste un point qui peut sembler secondaire
> [...]
Tu m'as dￜjￜ fait cette remarque par courriel privￜ, et je t'ai
dￜjￜ signalￜ que j'y avais rￜpondu par anticipation dans l'article
d'origine... ;-)
Cordialement,
--
Olivier Miakinen