Algo le plus rapide pour trouver une répétition ?

Bonjour :D

Quelle serait l'algo le plus rapide pour trouver le caractère(0 à 255) qui se répète le plus dans un fichier ?

La seule méthode que j'ai trouvé est de faire un tableau de 256 éléments et de parcourir le fichier octet par octet puis avec sa valeur aller dans la même position dans le tableau puis incrémenter la valeur.

Mais quand on a un fichier d'une centaine de mb c'est long. :o

Déplacé depuis le forum Assembleur par Alcatîz

Mmm :?
C vrai que le parcours de tableau n'est pas particulièrement optimal.
Je me tournerais vers un algo de tri pour faire ça moi comme ça au débotter:)
Regarde dans le 3ème volume de Knuth Sorting and Searching là tu devrais pouvoir trouver des algos plus performants. Les algos de tris et de recherche sont très proches.
A titre informatif ce sont de tels algos que j'utilise en perl pour déterminer le nombre de récurrences de tel ou tel mot dans un article du monde les articles et autres prépositions non comprises :lol:

La méthode que tu évoques est celle du tri par casiers qui est parfaitement adpatée à ton problème, c'est sans doute la plus rapide, d'autant que tu connais déjà le mini (0) et le maxi (255) des valeurs : un seul parcours du fichier et un parcours relativement rapide (256 éléments) du tableaux final.
En génral les autres tris sont de l'ordre de n * log n dans le meilleur des cas, le tien est en n.
Je ne crois pas que le fait que tu cherches uniquement la valeur maxi change grand chose.

+1 pour Trap D.

Je vois pas comment on pourrait faire plus efficace: on lit chaque caractère du fichier une seule fois, on ne fait pas de manipulations memoires (pas de creation d'objets)... A chaque caractere lu, c'est une indirection pour lire la valeur dans le tableau, une addition, puis on re-enregistre la valeur dans le tableau.
Et à la fin, on parcourt linéairement le tableau (256 éléments, ça va vite) pour chercher le max.

Même du point de vue matériel, un tableau de 256 octets (ou 256*n, n étant la taille du type entier que tu as choisie) tiendra facilement dans un cache processeur et, si tu lis ton fichier par blocs assez grands, tu limites les IO... (et pour un gros fichier, bah c'est l'OS qui gère le cache).

Je serais étonné qu'on puisse trouver plus rapide...