Classements des joueurs

[Foxglove]

hashtables

Dans un tableau tu associes une valeur à chaque index. t[0] vaut "a", t[1] vaut "b", t[2] vaut "c". Si tu veux rechercher un élément, tu dois parcourir toutes tes cases.

Dans une hashtable, tu associes une valeur à un hash, c'est-à-dire à une clé. Par exemple, tu peux dire qu'il y a deux clés : voyelles et consonnes. Si tu veux ajouter "a" dans ta hashtable, tu vas la mettre dans la case t[voyelle]. Si tu veux ajouter "b", tu le mets dans t[consonne]. Si tu veux ajouter "c", problème car il y a déjà quelqu'un dans t[consonne]... La solution utilisée par les hashtables est de pouvoir mettre plusieurs éléments dans une même case. On a donc :
t[voyelle] = {a, e, i, o, u}
t[consonne] = {b, c, d, f, g, ...}

A quoi ça sert ? Toute à l'heure, pour chercher une lettre dans un tableau, tu devais examiner toutes les cases. Maintenant, pour rechercher une lettre dans une hashtable, tu dois juste regarder t[voyelle] (donc 5 cases) si la lettre recherchée est une voyelle, et t[consonne] (donc 21 cases) si c'est une consonne.

En suivant ce principe, j'imagineais le truc suivant dans ton cas. Je suppose que tu as pleins de joueurs différents, disons 100 000. Les classements vont de 0 à 20 000 par exemple. Je découpe les classements en "paquets" de 1000, ça me fait 20 paquets. Le premier paquet c'est les classemets de 0 à 999, le deuxième de 1000 à 1999, etc.

Si je veux connaître les 20 classements autour d'un joueur donné, je regarde son score : 3375 par exemple. Je prend le quatrième paquet (contenant les scores de 3000 à 3999), je trie ce paquet, et je prend les 20 classements qui m'intéressent. J'aurais pas à trier 100 000 valeurs, à moins que les 100 000 joueurs aient un classement compris entre 3000 et 3999... En fait, j'espère que les classements sont bien répartis, et dans ce cas j'aurais que 5000 valeurs à trier (et si c'est toujours trop, j'ai qu'à faire plus de 200 paquets au lieu de 20 paquets).

Bon, il peut arriver que le paquet que je considère ne contienne pas tous les classements voulus. Ca arrive si le joueur a 3000 pile par exemple. Il faut que j'aille chercher des valeurs dans le paquets du dessous. Bon, mais c'est pas très grave, l'intérêt est que tu sais à peu près où sont les valeurs que tu recherches sans avoir à tout parcourir.

recherches dichotomiques

La recherche dichotomique, ça sert à retrouver rapidement une valeur dans un tableau trié.

Je reprends l'exemple de tout à l'heure. J'ai un paquet avec 5000 scores. Je sais que le joueur a 3375. S'il faut que je parcoure les 5000 scores pour trouver le score du joueur, c'est dommage, ça me fait perdre du temps (ok, trier ça m'a fait perdre plus de temps, mais une fois qu'on a trié, on va garder le tableau trié, on va pas le retrier à chaque fois non plus).

La recherche dichotomique, c'est comme quand tu recherches un nom dans l'annuaire. Tu fais pas les pages une par une dans l'ordre. Tu ouvres à peu près au milieu, tu regardes si tu es trop loin ou pas assez loin, et tu recommences.

Sur un dictionnaire de 100 000 pages, tu peux retrouver n'importe quel nom en regardant au plus 17 pages. C'est super efficace.

J'espère que c'est plus clair ?

Maintenant, c'est pas forcément la méthode la plus efficace de refaire ce genre de trucs en PHP. Ton SGBD fait lui aussi des opérations super efficaces lui aussi. Il fait pas ses recherches n'importe comment, et il a des méthodes très rapides pour trier, etc. Maintenant, elles sont pas forcément adaptées à tes données (à leur fréquence de changement, à l'intervalle de valeurs, etc), et il faut bien le connaître pour savoir s'il va supporter la charge. A mon avis, tant que tu as moins de 10000 valeurs, n'importe quelle méthode (même une mauvaise) marchera sans problème.