[ Révisions ] Questions sur les structures de données

Questions sur les structures de données [ Révisions ] - Aide aux devoirs - Emploi & Etudes

Marsh Posté le 01-04-2004 à 17:50:38    

:hello:
Je révise pour mon interro de structures de données, il y a 2 questions que je me pose.
 
La première, les tables de hachage:
J'ai bien compris que c'était des tableaux de listes mais je ne comprends pas comment fonctionne la recherche dans le tableau si les listes ne sont pas ordonnées.
Dans le cas d'un annuaire par exemple, qu'est ce qui fait que l'on rentre chercher dans telle liste qui correspond à une case X du tableau et pas dans une autre ?
 
La seconde, les listes et la recopie. Je vous copie colle la partie de cours concernée. J'ai quoted ce qui me http://forum.hardware.fr/icones/icon16.gif plus bas.


 
4.6 Copie et partage
Le problème de la copie et du partage consiste à faire une choix important dans la sémantique des opérations.
Dans le monde mathématique les objets sont immuables (le nombre 6 ne peut pas devenir 12)
 
Dans un système informatique les objets sont mutables, leur valeur peut changer.
 
Si deux variables font référence au même objet, une modification de cet objet change simultanément la valeur
référencée par ces variables, on dira alors que ces variables se partagent un objet.
 
 
Exemple :
List a ;
vide(a) ;
b = cons ( a, 'toto')
c = cons ( b, 'maman')
 
 
D'après la spécification de cons, le résultat de b = cons ( a, 'toto') est un nouvel objet de Liste tel que sa tête vaut 'toto'
et son reste vaut a.
 
Cette opération introduit donc un partage de structure entre b et a, puisque le reste de b est l'objet a.
 
De même c = cons ( b, 'maman') introduit un partage entre c et b.
La liste c a pour contenu ('maman' ('toto' vide)), si maintenant nous faisons vide(b), c deviendra ('maman' vide).
 
Le partage de structure n'est donc pas sans danger car une modification de b modifie également c sans qu'il y ait accès
explicite à c.
 
Si l'on veut éviter le partage de structure on peut recourir à la copie.
 
La copie d'un objet x consiste à fabriquer un nouvel objet y distinct de x mais portant la même valeur.
 
Il faut bien entendu faire des copies de tous les objets qui composent x.
 
Dans le cas des listes, si x a pour reste la liste x' et pour tête l'objet o, il faut commencer par faire une copie de x' en y' et
une copie de o en o', puis construire y avec o' et y'. La copie de x' peut elle-même nécessiter la copie de son reste, et ainsi
de suite.
 
Méthode copie (o suppose qu'il existe une méthode copie qui effectue une copie d'un élément de la liste)
 
Element copieElement ;
Liste result ; vide(result) ;
Liste aCopier = self ;
While not (estVide(aCopier))
copieElement = copie(aCopier.tete) ;
result = cons (copieElement, result) ;
aCopier = aCopier.reste ;
}
return result ; //la liste a été inversée
 
Si le partage présente certains dangers, il évite par contre de recopier inutilement des parties de liste.
 
Par exemple,
pour accéder au second élément de c on fera:
second := (c.reste).tete.
 
S'il y a partage de structure cette opération est très simple. Si au contraire la méthode reste recopie tous les éléments de
c sauf la tête pour créer une nouvelle liste, le simple accès au second élément de c devient très coûteux lorsque c est
longue.
 


 

Citation :

Le partage de structure n'est donc pas sans danger car une modification de b modifie également c sans qu'il y ait accès
explicite à c.
 
Si l'on veut éviter le partage de structure on peut recourir à la copie.
 
La copie d'un objet x consiste à fabriquer un nouvel objet y distinct de x mais portant la même valeur.


 
C'est surtout ce passage là que je ne comprends pas, pourquoi on doit forcèment recopier. En quoi ne pas le faire nuit au programme ???
 
Un exemple siouplaît :'(.
 
Merci :)
 
P.S. Au besoin les modos peuvent déplacer ça dans la cat programmation ;).


Message édité par jeoff le 01-04-2004 à 17:57:15
Reply

Marsh Posté le 01-04-2004 à 17:50:38   

Reply

Marsh Posté le 01-04-2004 à 23:48:01    

jeoff a écrit :

:hello:
Je révise pour mon interro de structures de données, il y a 2 questions que je me pose.
 
La première, les tables de hachage:
J'ai bien compris que c'était des tableaux de listes mais je ne comprends pas comment fonctionne la recherche dans le tableau si les listes ne sont pas ordonnées.
Dans le cas d'un annuaire par exemple, qu'est ce qui fait que l'on rentre chercher dans telle liste qui correspond à une case X du tableau et pas dans une autre ?


 
Les listes ne sont pas ordonnees donc on fait une recherche sequentielle : pour chercher dedans tu va regarder le premier element, si c'est pas le bon tu passes a l'element suivant et ainsi de suite...
MAIS la fonction de hachage devrait te repartir tes elements correctement eparpilles dans le tableau, si il y a des collisions, on pourra les stocker sous forme de listes (qui seront normalement pas tres grande donc il n'est pas necessaire de les trier ou faire un algo pointu de recherche dessus)
 
Par exemple on pourrait repartir le nom des personnes dans un tableau de 26 elements en fonction de la premiere lettre de leur nom : 1 element = 1 lettre. Mais voila que Patrick, Pierre et Paul commencent par la meme lettre P donc on a une liste de nom commencant par "P".  
Quand on recherche Paul, on va aller a la case "P" du tableau, on trouve d'abord Patrick, c'est pas lui qu'on cherche on regarde le suivant, Pierre, pas lui non plus, Paul ensuite... Bien sur, stocker l'annuaire comme ca c'est pas une bonne idee  :jap:  
 

jeoff a écrit :


Citation :

Le partage de structure n'est donc pas sans danger car une modification de b modifie également c sans qu'il y ait accès
explicite à c.
 
Si l'on veut éviter le partage de structure on peut recourir à la copie.
 
La copie d'un objet x consiste à fabriquer un nouvel objet y distinct de x mais portant la même valeur.


 
C'est surtout ce passage là que je ne comprends pas, pourquoi on doit forcèment recopier. En quoi ne pas le faire nuit au programme ???
 
Un exemple siouplaît :'(.
 
Merci :)
 
P.S. Au besoin les modos peuvent déplacer ça dans la cat programmation ;).


 
Bah ca depends si tu veux modifier ton objet ou pas.. Par exemple tu veux connaitre le nombre de chiffres qui constitue un nombre... exemple : 1000 bah dans une fonction qui calcule ca, tu va diviser 1000 par 10 jusqu'a avoir 0 en comptant combien de divisions tu as fait pour en arriver la et tu retournes 4... Mais t'aimerais continuer tes calculs avec ton 1000 du depart donc t'as du donner une copie a ta fonction au lieu de partager le meme nombre 1000 sinon tu va avoir un 0 apres cette fonction, ce qui ppurrait etre embetant... Pareil pour des trucs plus compliques


---------------
[03:06] <hellstrike> squi L au fait ?
Reply

Marsh Posté le 02-04-2004 à 01:38:20    

Merci ;)
 

Hazar a écrit :


 
Bah ca depends si tu veux modifier ton objet ou pas.. Par exemple tu veux connaitre le nombre de chiffres qui constitue un nombre... exemple : 1000 bah dans une fonction qui calcule ca, tu va diviser 1000 par 10 jusqu'a avoir 0 en comptant combien de divisions tu as fait pour en arriver la et tu retournes 4... Mais t'aimerais continuer tes calculs avec ton 1000 du depart donc t'as du donner une copie a ta fonction au lieu de partager le meme nombre 1000 sinon tu va avoir un 0 apres cette fonction, ce qui ppurrait etre embetant... Pareil pour des trucs plus compliques


 
Ok pour le hachage, c'est bien ce que je pensai mais c'était pas très clair dans le sens ou le tableau ne mentionne pas explicitement que la case 0 est la première de l'alphabet ...  
Si tout le monde garde ses petites conventions dans la tête je risque pas de capter ou bien ce sera du "je pense que mais c'est pas sûr à 100% ..."
 
Pour la seconde, je me doute bien que si j'utilise 1000 pour un calcul, ça passe par une variable tampon. Donc à moins de modifier toute la liste pour un calcul, quelques variables buffer suffisent pour la plupart des cas, non  http://forum.hardware.fr/icones/icon16.gif


Message édité par jeoff le 02-04-2004 à 01:39:33
Reply

Marsh Posté le 02-04-2004 à 23:55:44    

Bon, soit j'ai pas compris ta question, soit tu connais pas tres bien ton cours :sarcastic:
 
C'est seulement pour l'exemple qu'une case du tableau correspond a une lettre (qui est la premiere du nom de celui qu'on cherche ici dans l'exemple ) Ensuite ce n'est pas obligatoire que la case 0 soit la premiere lettre de l'alphabet... Cela depend de ta fonction de hachage qui repartit les elements : tu as une fonction de hachage "f( cle )" qui retourne la case qui lui correspond.  
 
Selon comment elle est definie, elle peut te dire que :
 
- la case 2 corresponde a tout les mots commencant par "b" (b etant la 2eme lettre de l'alphabet ?)
- la case 2 corresponde aux mots constitues de 2 lettres  
- ou plus complique : la case 2 corresponde a la "somme des lettres" d'un mot + la longueur du mot modulo 9 (9 serait la taille du tableau) egal a 2.  
Exemple : Anne = 2 car A = 1, N = 14 et E = 5, longueur du mot "Anne" = 4
f( Anne ) retourne (( 1 + 14 + 14 + 5 ) + 4) mod 9 = 2
 
Bref la fonction de hachage est a definir comme on veux mais  doit respecter quelques criteres... elle doit etre deterministe (tout le temps renvoyer la meme valeur pour une meme cle, pas de random quoi), uniforme ( pour eviter les collisions au maximum et avoir des listes trop longues ) et rapide a calculer ... voila donc y'a pas de conventions personnelles...
 
Sinon pour tes copies de variable, j'ai pas comprit la question !! :na:


---------------
[03:06] <hellstrike> squi L au fait ?
Reply

Marsh Posté le 06-04-2004 à 19:41:23    

HaZaR a écrit :

Bon, soit j'ai pas compris ta question, soit tu connais pas tres bien ton cours :sarcastic:
 
C'est seulement pour l'exemple qu'une case du tableau correspond a une lettre (qui est la premiere du nom de celui qu'on cherche ici dans l'exemple ) Ensuite ce n'est pas obligatoire que la case 0 soit la premiere lettre de l'alphabet... Cela depend de ta fonction de hachage qui repartit les elements : tu as une fonction de hachage "f( cle )" qui retourne la case qui lui correspond.  
 
Selon comment elle est definie, elle peut te dire que :
 
- la case 2 corresponde a tout les mots commencant par "b" (b etant la 2eme lettre de l'alphabet ?)
- la case 2 corresponde aux mots constitues de 2 lettres  
- ou plus complique : la case 2 corresponde a la "somme des lettres" d'un mot + la longueur du mot modulo 9 (9 serait la taille du tableau) egal a 2.  
Exemple : Anne = 2 car A = 1, N = 14 et E = 5, longueur du mot "Anne" = 4
f( Anne ) retourne (( 1 + 14 + 14 + 5 ) + 4) mod 9 = 2
 
Bref la fonction de hachage est a definir comme on veux mais  doit respecter quelques criteres... elle doit etre deterministe (tout le temps renvoyer la meme valeur pour une meme cle, pas de random quoi), uniforme ( pour eviter les collisions au maximum et avoir des listes trop longues ) et rapide a calculer ... voila donc y'a pas de conventions personnelles...
 
Sinon pour tes copies de variable, j'ai pas comprit la question !! :na:


 
Merci, c'était le bout de cours qui manquait dans le pdf parceque je me souvient avoir entendu ça en cours mais lu nulle part ailleurs ... :)

Reply

Marsh Posté le 06-04-2004 à 20:26:15    

De rien, au moins ca verifie si j'ai assez bien compris pour etre capable de m'exprimer clairement :)

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed