natto Le 20/02/2004 à 21:12 mais tu peux pas chercher sur le net des comparatifs ou reflechir avec ton cerveau bordel de merde ?
納 豆パワー！
I becamed a natto!!!1!one!
Peut-être qu'un trac serait plus adapté. non ?
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas
. »
vince Le 20/02/2004 à 21:21 peut-être qu'en testant toi même tu te ferais une meilleure idée, non ?
C'est vraiment très critique ?
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas
. »
geogeo Le 20/02/2004 à 22:25Edité par geogeo le 20/02/2004 à 22:45 Hum vous me les cassez grave là franchement j'en est ras le cul des réponses cherche sur le net ou réalise le truc!
Pour gouverne j'ai mon arbre bianire en ce moment avec mes fonctions j'ai réalisé il y a peu de temps une table de hachage mais vraiment simpliste sans malheuresement après un temps de recherche trouvé des infos concrètes. Alors épargniez moi votre sauce genre je me fous de votre gueule et je ne fais que poser des questions à la con en vous demandant de macher mon travail, vous êtes débile ou quoi?
En fait j'ai un programme qui à besoin de rechercher des mots stockés dans un dictionnaire, sans ma table de hachage simpliste il tourne à 1ko/s avec table, environ 100 ko/s mais ça ne me suffit pas, le traitement sur des fichiers de taille considérable supérieur à 20 Mo est horriblement lente, de plus il faut que j'exploite la méthode Burrows & Wheeler qui demande un algorithme de trie rapide or arbre de recherche avec une dérivée. Mais le problème est que malgré les recherches effectués je le répété je n'arrive pas à savoir les complexités des algos type arbre binaire de recherche (ARB) ou tables de hachages ou encore la quantité de mémoire requise.
[EDIT] Content monsieur Microbug, toujours HS.
Si tu n'arrives pas à déterminer quelle quantité de mémoire bouffe ton programme, demande-nous de t'aider sur un point précis plutôt que de nous demander de balancer le résultat final, ce qui ne t'apprendra rien du tout...
« The biggest civil liberty of all is not to be killed by a terrorist. » (Geoff Hoon, ministre des transports anglais)
Arbre binaire de recherche -> lookup en O(longueur de la chaîne).
Table de hachage -> lookup en (temps de calcul du hash)+O(1+(probabilité de collision))
Ce sont des chaînes d'octets ou de bits? Parce que pour des chaînes d'octets, tu peux aussi essayer les arbres d'ordre 256 (l'ordre est le nombre de nœuds fils, par exemple arbre binaire == arbre d'ordre 2), ça te fera en théorie un lookup 8 fois plus rapide.
Mais tu vois ça où que je te demande de me balancer le résultat final, je veux pas d'algos???
Je vais détaillez encore plus loin:
J'exploite l'algorithme de compression LZW, celui-ci demande la création d'un dictionnaire, pour mon cas ce dictionnaire est de taille variable mais par défaut de 8192 éléments plus précisément 8192-259=7933 éléments réellement utilisés.
Chaque éléments que j'appel définitions peuvent contenir une chaîne de caractères de taille maximal de 4096 caractères.
L'algorithme de compression demande la recherche d'une chaîne de caractère nommé tampon dans le dictionnaire et donc si la recherche est réussie de renvoyer l'index où ce trouve la définition. Or le problème de cette algo de compression c'est qua lé recherche d'une définition dans le dictionnaire est très longue et demande une organisation des données pour effectuer la recherche plus rapidement.
J'ai donc décidé d'organiser mon dictionnaire en sommaires, chaque sommaire contient toutes les défintiions commençant par le même caractère cette méthode demande dans mon cas 8 Mo de mémoire avec un dico de 8192 éléments et n'augmente pas assez la vitesse de compression je trouve.
Avant de développer la méthode avec tables de hachages je me demande si s'est réellement utile dans mon cas, vous allez encore me dire que je suis une faigniasse de ne pas la faire mais vous en ferez autant.
Donc je voudrais savoir les avantages entre un ABR et table(s) de hachage(s).
Pour la mémoire:
Arbre binaire de recherche -> environ O(n ln(n)), avec n le nombre de chaînes présentes
Arbre d'ordre 256 -> à peu près 4 fois la mémoire d'un arbre binaire ((256/2)/2log(256)==4)
Table de hachage -> (taille de la table de hachage) + (probabilité de collision)
Bon, je vois comment tu trouves 8 MO (4*256*8192). Il y a moyen de consommer beaucoup moins de mémoire que ça! Tu n'as pas besoin de tous les 8192 pointeurs dans chaque sommaire, tu peux mettre un tableau compact d'indices short, plus un seul tableau de 8192 pointeurs pour le dictionnaire entier. Total: 48 KO.
De même, si tu veux faire un arbre d'ordre 256, pour économiser de la mémoire, n'alloue pas un tableau vide. S'il n'y a aucun mot qui commence par "x", n'alloue pas un tableau pour le nœud "xa...xz" (ça ne sert à rien s'il n'y a rien dans ce nœud), mais mets NULL dans la case qui correspond à "x".
Et tu peux même économiser encore plus de mémoire en ne mettant pas toutes les 256 entrées, mais juste une paire (lettre,entrée) pour chaque entrée non-vide. Le désavantage de cette dernière méthode est que le lookup devient plus lent parce que tu ne peux plus te contenter de regarder dans un tableau (O(1)), mais tu dois faire une recherche (O(ln(n)) si tu as maintenu tes entrées à l'état trié, O(n) sinon, avec n le nombre d'entrées non-vides de ton nœud).
Enfin de compte j'ai mélangé table de hachage avec arbre binaire voici comment je procéde:
J'ai une table de pointeurs pointant vers des ABRs il y a un total de 65536 pointeurs.
Un index de cette table correspond au 2 premiers caractères d'une chaîne.
Chaque ABR est construit suivant la taille de la chaîne.
Grâce à cette méthode je ne consomme seulement que 400 ko de mémoire environ pour un dico de 8192 éléments. Le gain en vitesse est assez important mais je trouve insuffisant.
Pour un ordre d'idée je met 2min à compresser un fichier de 48 mo dans les pires conditions c'est à dire un parcours presque complet des ABRs avec un dico de 8192, méthode LZW.
N'y a t-il pas d'autres moyens mieux adapter pour effectuer la recherche encore plus rapidement. Ou encore créer un ABRs suivant les caractères de la chaîne et non ses infos (taille, première lettre...)?
Vraiment désolé de poser cette question mais je ne vois réllement pas comment faire mieux et aucuns sites ne donnent des infos sur ce sujet.
Encore merci de votre aide.
)
