Algorithme permettant de garder les meilleurs score

**mhtrinh** · 11/12/2007, 21h13

Bonjour,

J'ai un programme en C qui calcule des scores. Et je veux garder que un certain nombre de meilleurs scores.
Le problème c'est que j'ai environ 10^9 score a calculer et je voudrais garder les 10^6 meilleurs. Je cherche une methode qui soit relativement optimisée (sinon, mes calculs risques de prendre des heures ...).

Merci

**Pacorabanix** · 11/12/2007, 21h17

ce que je trouve le plus simple :

* conserver les scores dans une liste triée (ou alors les trier au dernier moment)

* les "meilleurs scores" sont simplement les 10^6 premieres cases du tableau

Ceci revient donc à faire un algorithme de tri.

**mhtrinh** · 11/12/2007, 21h37

Les scores calculés arrivent au fur et a mesure. Je les ai pas tous d'un coup. Et je veux pas non plus tous les stocker (10^9 double en memoire ca fait mal ... )

Pour le tableau ordoné de score : j'y ai deja pense. Mon programme pour l'instant utilse un tableau de pointeur vers des structures contenant les scores (et d'autres infos utiles).
Quand un nouveau score arrive, je regarde si il est superieur au minimum du tableau (le dernier element du tableau). Si oui, je regarde la ou il faut l'inserer (recherche par dichotomie) puis je fais un memmove pour inserer le nouveau element.

J'ai pense a une autre methode : une liste chainee, qui a l'avantage de pas avoir trop de déplacement de données en memoire, cependant, pour chercher la ou il faut inserer un nouveau element, il faut parcourir la liste linéairement ....

**icer** · 11/12/2007, 23h01

Bonjour,

As tu pensé à utiliser un gestionnaire base données pour manipuler tes scores.

C'est un outil adapté pour ce genre de choses

**Pacorabanix** · 12/12/2007, 02h04

Envoyé par mhtrinh

Les scores calculés arrivent au fur et a mesure. Je les ai pas tous d'un coup. Et je veux pas non plus tous les stocker (10^9 double en memoire ca fait mal ... )

oui pardon ^^, je n'avais pas fait le "calcul".

et bien c'est tout vu : si ça arrive au fur et à mesure il est clair que tu gardes une liste des meilleurs scores triée continuellement comme tu l'as dit.

J'ai pense a une autre methode : une liste chainee, qui a l'avantage de pas avoir trop de déplacement de données en memoire, cependant, pour chercher la ou il faut inserer un nouveau element, il faut parcourir la liste linéairement ....

c'est faisable si c'est surtout pour apprendre à programmer, et en théorie des lectures sont plus rapides que des écritures mais

Envoyé par icer

Bonjour,

As tu pensé à utiliser un gestionnaire base données pour manipuler tes scores.

C'est un outil adapté pour ce genre de choses

c'est mieux je pense aussi

**mhtrinh** · 12/12/2007, 09h41

Bonjour,
Pouvez vous detailler un peu plus sur les gestionnaires de bases de données de scores ?? Sur les bases de donnees, je connais MySql ... mais je vois pas comment je vais l'utiliser avec mon programme en C ....
Merci.

**nolofinwe** · 12/12/2007, 09h54

Bonjour,

je vais peut etre dire une betise mais voila comment je ferai...
a chaque fois qu'un score est calculé il est trié est placé dans le tableau a la bonne place,
une fois que les 10^6 premiers score sont arrivé le tableau est plein. A partir de ce moment la on teste chaque nouveau score avec celui se trouvant dans la derniere case du tableau (donc le plus petit) puis si il est plus grand on décale comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
long i=(10^6)-2;
while(score>tab[i]){
tab[i+1]=tab[i];
i--;
}
tab[i]=score;

ainsi tu conserve a chaque fois les 10^6 meilleurs scores.

a +

**icer** · 12/12/2007, 10h37

Bonjour,
Pouvez vous detailler un peu plus sur les gestionnaires de bases de données de scores ?? Sur les bases de donnees, je connais MySql ... mais je vois pas comment je vais l'utiliser avec mon programme en C ....
Merci.

D'une façons général les systèmes de gestion de base données (MySql entre autres (qui n'est pas le meilleur à mon gout) ) serve à stocker, récupérer, modifier des informations. De plus ces systèmes sont déja optisés pour la recherche, le trie... Pour ton jeux, où tu as énormément de scores à gérer, tu pourrais déléguer cette tache à un gestionnaire de base de données et tu n'aurais plus à de soucier de la façons dont tes données sont stockées, triées... le language SQL permettant d'avoir cette abstraction.

Ces systèmes proposes des API pour manipuler les données avec SQL depuis un language de programmation, inclue le language c. Tu n'aura donc aucune difficulté majeur à l'intégré à ton jeux.

**Jean-Marc.Bourguet** · 12/12/2007, 10h46

Garder a tout moment les 10^6 meilleurs scores deja vu. Plutot qu'un tableau trie, prendre une structure telle qu'un tas (le tas du heap sort, pas celui qui gere la memoire). Pour le probleme tel que decrit, utiliser un db telle que MySql revient a prendre une presse hydraulique destinee a l'emboutissage a froid de pieces metalliques pour casser une noix.

**mhtrinh** · 12/12/2007, 17h12

Youpi !!! C'est bien ce que je cherche : HEAP SORT
Un algo qui permet de maintenir un minimum (ou maximum) sans se soucier du reste.
J'ai donc fait un heap avec le minimum à la racine de l'arbre.

Merci Jean-Marc.Bourguet. Il est pas VIP par hazard

**icer** · 13/12/2007, 12h43

Pour le probleme tel que decrit, utiliser un db telle que MySql revient a prendre une presse hydraulique destinee a l'emboutissage a froid de pieces metalliques pour casser une noix.

Pour continuer dans l'analogie de Jean-Marc.Bourguet, je dirais que quand on a pas de casse-noix, une presse hydraulique destinée à l'emboutissage à froid de pièces métalliques peut être très utile pour casser sa malheureuse noix, au lieu d'extraire du fer à partir de sable brut, de se fabriquer un moule de casse-noix en argile et d'y coulé le fer fondu à 1000°C pour fabriquer son casse-noix adapté à la taille de notre malheureuse noix.

**Jean-Marc.Bourguet** · 13/12/2007, 15h15

Envoyé par icer

Pour continuer dans l'analogie de Jean-Marc.Bourguet, je dirais que quand on a pas de casse-noix, une presse hydraulique destinée à l'emboutissage à froid de pièces métalliques peut être très utile pour casser sa malheureuse noix, au lieu d'extraire du fer à partir de sable brut, de se fabriquer un moule de casse-noix en argile et d'y coulé le fer fondu à 1000°C pour fabriquer son casse-noix adapté à la taille de notre malheureuse noix.

Tu prends deux cailloux. Toujours mieux que la presse hydraulique: tu as fini avant de lire les consignes de securite.

Il fut un temps ou j'avais a me battre contre le NIH. Maintenant il faut se battre aussi contre la tendance a batir des usines a gaz sous pretexte d'eviter le NIH.

(Au fait, on est sur le forum algorithme).