[ 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 à 23:48:01
| jeoff a écrit :
|
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 
| jeoff 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
---------------
[03:06] <hellstrike> squi L au fait ?
Marsh Posté le 02-04-2004 à 01:38:20
Merci 
| Hazar a écrit : |
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 
Message édité par jeoff le 02-04-2004 à 01:39:33
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 
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 !! 
---------------
[03:06] <hellstrike> squi L au fait ?
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 |
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 ... 
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
Sujets relatifs:
- [La Rochelle] Développeur bases de données cherche CDI
- • Topic Unique • Les questions relatives aux SALAIRES
- Questions sur certaines ecoles d'ingénieur !!!
- Questions sur les concours prepa intégrée
- [Topic unique] ULM-Normale Sup-Et gde écoles- Questions et temoignages
- [RCH] stage fin d'études bases de donnees
- Quels métiers dans l'univers de la sécurité des données
- Quel DESS en Bases de données?
- [Offre de stage] Assistant chef de projet Base de données
Marsh Posté le 01-04-2004 à 17:50:38
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
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.
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