algo de hashtable trés rapide...voire même ULTRA RAPIDE...

bonjour,

je voudrais coder (en C) un tableau qui contiendrait
-des chaines de caracteres (identifiants)
-la structure qui correspond

et il faudrait que les accés en lecture et en ecriture soient les plus rapides possibles.

quelqu'un a une idée ?

Si tu veux juste l'algo, c'est cool... si tu le veux en c, tu t'es trompé de forum.... :wink:


Maintenant, ce que je ne comprends pas c'est "la structure qui correspond" .... tu veux dire quoi ??

Edité par Gael.

oui en fait mon algo que je veux (mais si mais si, c'est français comme phrase ! :wink: ) c'est une méthode qui permette d'entrer et de sortir des infos dans cette table de la façon la plus rapide possible. parce que si à chaque fois que je veux un objet, je dois parcourir la table séquentiellement et comparer l'identificateur avec celui que je recherche, mon code va mettre une éternité à s'executer.
j'ai voulu m'inspirer des methodes de direct mapping utilisées par les memoires caches pour retrouver des valeurs, mais j'ai rien trouvé de vraiment efficace.

j'espère que j'ai été clair maintenant (je ferais un bien mauvais prof, je suis nul pour expliquer qqchose :cry: )

Ok... alors après ca dépend fortement du nombre d'entrée de ta table... mais tu peux faire un tableau a coté avec les numéros de cellule de chaque lettre de l'alphabet par exemple, comme ca tu ne "compareras" que des chaines potentielles...

ouais, c'est une idée qu'il faudrait creuser, je t'explique l'utilité du truc:

je code un compilateur PASCAL, et ce fameux tableau constitue la pile de données qui sera utilisée pour la génération du code de bas niveau.
l'identifiant dont je parlais n'est autre que le nom de la variable (la structure contient quelque conneries utiles pour la suite du proj).
et si je tombe sur un code PASCAL, genre avec tous les noms de variables començant par "var", je gagnerai pas de temps par rapport à du sequentiel..., et même j'en perdrais puisque je stockerai des trucs dans les tableau d'index de chaque lettre de l'alphabet.

Edité par Gael.

ouaip.... peut etre dirrectement une fonction qui te rend la structure (barbare, comme méthode, mais efficace)

je vois pas bien ce que tu veux dire... elles seraient stockées où les données :?: plus de tableau ?

ds les paramètres de ta fonction..... lol.....

Puisque les chaînes de charactères sont uniques pourquoi ne pas utiliser simplement un arbre binaire? En attendant de trouver mieux.

Sinon, Ecclesiaste Dworkin, pourquoi tu voulais mettre tes données dans les paramètres de ta fonction? Il faudrait les copier à la sortie de la fonction en dehors de la pile... En fait je ne te suis plus vraiment, là...

Je viens de faire du ménage dans ce topic hautement instructif. Merci de clore ce débat et de revenir au sujet originel.

Est-ce que la liste des chaînes de caractères (des identifiants je suppose) est intégralement connue avant d'avoir à créer ta hashtable, ou celle-ci est-elle remplie au fur et à mesure ?

J'attire aussi ton attention sur un point important : ce n'est pas la peine de mettre 10 s à créer une hashtable qui te ferait gagner 1 s au total. Une hashtable ne sert à rien si tu as 100 enregistrements que tu vas lire 50 fois, car dans ce cas une lecture séquentielle en mémoire est largement assez performante.

ben en fait, je lis le programme pascal et au fur et à mesure que je tombe sur des déclarations de variables, je les ajoute à la pile de données avec le nom de la variable (qui pourrait servir de clé), et la classe de la variable, ainsi que quelque broutilles sans interêt.
donc le contenu de la liste est inconnu au début, je la remplis au fur et à mesure de la compilation.

si je garde du sequentiel, je suis d'accord avec toi pour dire que ce sera efficace sur un programme d'ampleur restreinte. mais il faut aussi que mon compilateur soit performant pour compiler de trés gros programmes (beaucoup de données, et beaucoup d'accés)

Est-ce que ton compilo est multi-passe ?
Une première passe permettant de vérifier un minimum de syntaxe et de stocker l'ensemble des noms de variables, puis de faire la table de hashage (donc en connaissant toutes les variables).

Sinon, tu peux espérer une distribution aléatoire des noms de variables avec quelques astuces : partir de la fin, ou du milieu (un coup en avant, puis un coup en arrière...).

en fait c'est parfait, je pense que j'ai trouvé.
j'ai établi bien précisément mes besoins, et j'ai conclus qu'il me fallait tout simplement un algorithme de hachage dont la clé générée est au moins de 16 bits (possibilité de déclarer 65 000 variables dans le code pascal, ça me semble assez confortable :))
j'ai pas encore fini de lire le truc mais je crois que cette page répond à ma question:
http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacques.Levy/poly/main1/node17.html

dans tous les cas merci à tous de vous être penché sur mon problème, ça m'a vachement aidé quand même !

Un petit Résolu ?