- Partage ce devoir avec tes amis !
Sujet du devoir
a) Supposons qu’on ait une table de taille M et qu’on fait un ré-hachage vers une table plus petite (de taille M/2) quand le nombre d’éléments devient égal à p*M. Comment choisir la valeur de p?b) On regarde maintenant la nouvelle table de taille M/2. Soit n1 le nombre d’ajouts avant de faire un rebalancement vers une table plus grande. Soit n2 le nombre de retraits avant de faire un rebalancement vers une table plus petite. On choisit p pour que n1 = n2. Que faut-il prendre pour la valeur de p?
c) Cela fait combien de retraits/ajouts de la table de taille M/2 si M=600, par exemple?
Où j'en suis dans mon devoir
a) Je me dis que le p doit être au moins plus petit que 0.5 pour qu'on ait assez de place pour stocker tous les éléments dans une table de taille M/2. Est-ce de cette façon qu'il faut raisonner?b) J'ai répondu qu'on devrait prendre un p environ égal à 1 pour qu'on ait pas à changer la taille de la table. Donc, en moyenne, n1 resterait égal à n2.
c) Voilà ici j'ai un problème. Comme on est dans la table de taille M/2 (donc 300) et que p est environ égal à 1, le nombre d'ajouts et de retraits devraient être équivalents. Alors 300/2 = 150? Ça me semble beaucoup, je ne sais pas comment trouver la réponse...
Merci de votre aide!
1 commentaire pour ce devoir
Ils ont besoin d'aide !
- Aucun devoir trouvé, poste ton devoir maintenant.
je ne suis pas certaine d'avoir bien pigé le but du jeu, mais voici quelques réflexions :
si p=0,5 en effet, on pourra ranger tous les éléments de la table de dim M dans celle de M/2, mais alors celle-ci est immédiatement complète, ce qui empêche de la garder. Il faut tout-de suite re-basculer dans une table + grande.
Il me semble que si on prend p = 0.25 ça peut mieux marcher :
quand la table 1 ne contient plus que 25% d'éléments, on bascule sur une table de dimension M/2, qui est alors remplie à moitié.
On rebascule vers une table plus petite (de dimension M/4) quand cette table M2 est elle aussi remplie à 25% (donc après 75 retraits), ou vers une table + grande après 75 ajouts (elle est alors remplie à 75%)
on pourrait choisir p=0.33 par exemple, mais dans ce cas,
quand on bascule de table1 vers table2, on a 200 elements à placer, donc la table2 est remplie à 66%, et comme n1=n2, on devra la rebasculer immédiatement vers table1 ==> pas cool.
si on prend p<0.25, par exemple p=0.20
on passe de table1 à table2 quand on a 120 éléments, ça marche pour la question 1, et n1 = 60 mais ensuite comme n1=n2, on doit rebasculer vers une table + grande au bout de 60 ajouts, donc avce 180 elements.. on ne remplira plus la grande table à hauteur de moitié..
C'est pourquoi je crois que la meilleure valeur pour p est 0.25
qu'en penses tu ?