Version imprimable
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 :mrgreen:
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.
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 ....
Bonjour,
As tu pensé à utiliser un gestionnaire base données pour manipuler tes scores.
C'est un outil adapté pour ce genre de choses
oui pardon ^^, je n'avais pas fait le "calcul".Citation:
Envoyé par mhtrinh
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.
c'est faisable si c'est surtout pour apprendre à programmer, et en théorie des lectures sont plus rapides que des écritures maisCitation:
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 mieux je pense aussiCitation:
Envoyé par icer
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.
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 :
ainsi tu conserve a chaque fois les 10^6 meilleurs scores.Code:
2
3
4
5
6
7
a +
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.Citation:
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.
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.
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.
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 :king:
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.Citation:
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.
Tu prends deux cailloux. Toujours mieux que la presse hydraulique: tu as fini avant de lire les consignes de securite.Citation:
Envoyé par icer
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).
Je suis aussi pour la simplicité :
Utiliser des solutions toutes faites, c'est aussi faire simple.
Qu'est-ce que le NIH ?
Pas toujours. Et dans ce cas ci, utiliser une db est dans le pas.Citation:
Envoyé par icer
Not Invented HereCitation:
Qu'est-ce que le NIH ?