IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Caml Discussion :

Table de hachage, fonctionnement !


Sujet :

Caml

  1. #1
    Nouveau membre du Club
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2008
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Avril 2008
    Messages : 32
    Points : 27
    Points
    27
    Par défaut Table de hachage, fonctionnement !
    Bonsoir,
    j'ai un projet à faire en utilisant le module Hashtbl ! vu que je ne connais pas vraimentle principes des tables de hachage, donc cela m'empeche d'avancer.
    Ce que je vu savoir :
    1- la fin d'une table de hachage ( les listes : [] par exemple).
    2- comment définir des fonctions récursive en parcourant les tables de hachage.
    3-comment connaitre les clefs de la suite d'une table de hachage .

    merci pour os réponse !

  2. #2
    alex_pi
    Invité(e)
    Par défaut
    Je suis désolé, je n'ai pas le temps de répondre ce soir, mais as-tu bien lu http://caml.inria.fr/pub/docs/manual...f/Hashtbl.html ? Ca devrait répondre à certaines questions je pense.

    Bon courage et bonne nuit

  3. #3
    LLB
    LLB est déconnecté
    Membre expérimenté
    Inscrit en
    Mars 2002
    Messages
    967
    Détails du profil
    Informations forums :
    Inscription : Mars 2002
    Messages : 967
    Points : 1 410
    Points
    1 410
    Par défaut
    Une table de hachage n'est pas une liste. C'est une structure qui permet un accès direct aux éléments, en temps constant (quand tout va bien). Fais une recherche pour en savoir plus.

    Les fonctions du module devraient te donner pas mal de pistes sur ce qu'on peut faire (n'essaie pas de travailler avec de la même façon qu'avec une liste). N'essaie pas de faire un parcours avec une récursion. Dans la majorité des cas, tu n'as même pas besoin de parcourir.

  4. #4
    Nouveau membre du Club
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2008
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Avril 2008
    Messages : 32
    Points : 27
    Points
    27
    Par défaut
    merci pour vos réponse
    en fait j'avais regarder la doc mais je n'ai y pas trouvé des réponse a mes question !!
    en fait ma question est comment savoir qu'une table de hachage est vide ?
    j'ai trouve la fonction hashtbl.clear -> mais c'est utiliser juste pour vider une table de hashage.
    Pour le parcour d'une table de hachage je crois que la fonction Hashtbl.find_all pourra m'aider a parcourir la table sans passer par la création d'une fonction récursive. est ce vrai ??

  5. #5
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut
    • Hashtbl.length pour la taille (0 si vide)
    • Hashtbl.add pour l'insertion
    • Hashtbl.find pour la recherche
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  6. #6
    Nouveau membre du Club
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Avril 2008
    Messages
    32
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels

    Informations forums :
    Inscription : Avril 2008
    Messages : 32
    Points : 27
    Points
    27
    Par défaut
    en fait ce que je veux faire c'est de créer un graphe avec une table de hachage ayant comme clefs les arcs associés aux valeur qui son des noeuds

    donc mon probleme est comment parcourir une structure de données basé sur une table de hachage que je maitrise pas vraiment !!!

    parcourir les noeud jusqu'à qd faut s'arreter (exemple les liste ya la liste vide ) ...etc

    merci

  7. #7
    Membre actif Avatar de Steki-kun
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    222
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Janvier 2005
    Messages : 222
    Points : 281
    Points
    281
    Par défaut
    Ces tables de hachage sont des structures abstraites auxquelles tu accèdes par leur interface. Donc pas d'équivalent de la liste vide à vérifier toi-même, et de manière générale pas de "parcours à la main". Les fonctions qui permettent de parcourir la table sont Hashtbl.iter et Hashtbl.fold, qu'on appelle des "itérateurs".
    I'm the kind of guy that until it happens, I won't worry about it. - R.H. RoY05, MVP06

  8. #8
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Je ferais remarquer que même dans le cas des listes, il est fortement recommandé d'éviter la récursion explicite. Il est beaucoup plus propre d'utiliser des fonctions de parcours comme les fold ou map.
    C'est généralement vrai pour toute structure de donnée en fonctionnel : il faut éviter les récursions explicites et préférer les fonctions d'ordre supérieur encodant le type de parcours nécessaire.

    Un certain nombre de débutants se trompent sur ce point et après une introduction à la programmation fonctionnelle où on les a fait tout reprogrammer avec de la récursion explicite pensent que la récursion caractérise le style fonctionnel, alors que l'objectif en général du fonctionnel est justement de construire des abstractions suffisamment fortes pour éviter d'avoir à recourir à de la récursion brute (et la capacité à faire cela est précisément l'un de ses avantages par rapport à la programmation impérative où beaucoup continue à réinventer la roue (boucle) chaque fois qu'ils veulent parcourir une structure de donnée).

    Dans une application sérieuse écrite en fonctionnel, il ne devrait pas y avoir beaucoup de fonctions récursives explicites parcourant les données (pour une librairie créant une nouvelle structure de donnée, les choses sont différentes bien sûr).

    --
    Jedaï

  9. #9
    Membre actif Avatar de Steki-kun
    Profil pro
    Inscrit en
    Janvier 2005
    Messages
    222
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Janvier 2005
    Messages : 222
    Points : 281
    Points
    281
    Par défaut
    Je suis entièrement d'accord avec toi. Non seulement c'est plus propre, mais ça évite de tout simplement de se planter en écrivant son propre parcours (assez rare sur les listes, mais au combien fréquent sur des arbres, des graphes, etc).
    Je me suis fait récemment la même réflexion sur les effets néfastes des introductions à la programmation fonctionnelle: en corrigeant les programmes écrits par des élèves de master, j'ai été étonné du nombre de parcours de listes faits "à la main", et même après leur avoir expliqué le fonctionnement des itérateurs, ils restaient très réticents à les utiliser. Quand j'étais en prépa, on ne nous a quasimment jamais fait utiliser un itérateur non plus, ce qui crée de mauvasies habitudes.
    De tte façon, je crois que malheureusement ça prend un certain temps pour s'habituer à programmer à grands coup de fold_left :-) Et je vois bcp de gens qui y viennent que lorsqu'ils sont forcés, ie. sur les Sets et les Hashtbl, et qui une fois l'habitude prise, programment également de cette manière sur les listes.
    I'm the kind of guy that until it happens, I won't worry about it. - R.H. RoY05, MVP06

  10. #10
    Membre éprouvé
    Avatar de InOCamlWeTrust
    Profil pro
    Inscrit en
    Septembre 2006
    Messages
    1 036
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Septembre 2006
    Messages : 1 036
    Points : 1 284
    Points
    1 284
    Par défaut
    Citation Envoyé par Jedai Voir le message
    Je ferais remarquer que même dans le cas des listes, il est fortement recommandé d'éviter la récursion explicite. Il est beaucoup plus propre d'utiliser des fonctions de parcours comme les fold ou map.
    C'est généralement vrai pour toute structure de donnée en fonctionnel : il faut éviter les récursions explicites et préférer les fonctions d'ordre supérieur encodant le type de parcours nécessaire.
    Vvoouui, mais en Haskell... car le compilateur OCaml est très bête (pour l'avoir étudié un peu)... de plus, si tu regardes le code de List (en général toujours fourni quelque part dans lib/ocaml/), tu te rendras compte que n'importe quel débutant aurait pu écrire ce genre de code.

    Personnelement, je n'ai pas d'idée arrêtée sur le sujet : je pense, et j'en suis convaincu pour l'avoir déjà expérimenté, que les meilleurs codes OCaml (meilleurs en tous sens) sont les plus naturels. Donc, si il est naturel d'utiliser un itérateur, et bien vat pour l'itérateur, sinon, c'est de la récursion explicite.
    When Colt produced the first practical repeating handgun, it gave rise to the saying God created men, but Colt made them equal.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 4
    Dernier message: 19/03/2007, 11h34
  2. table de hachage
    Par mrtatou dans le forum Langage
    Réponses: 4
    Dernier message: 18/01/2006, 10h41
  3. Table de hachage
    Par Gryzzly dans le forum Algorithmes et structures de données
    Réponses: 1
    Dernier message: 25/12/2005, 18h31
  4. [Conception] Table de hachage et doublons de clés
    Par mammou dans le forum Collection et Stream
    Réponses: 2
    Dernier message: 13/05/2004, 20h16
  5. Réponses: 2
    Dernier message: 05/02/2004, 13h54

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo