Ci-dessous, les différences entre deux révisions de la page.
Les deux révisions précédentes Révision précédente Prochaine révision | Révision précédente | ||
dichotomie [2009/04/20 08:36] tyrtamos |
dichotomie [2009/04/20 09:06] (Version actuelle) tyrtamos |
||
---|---|---|---|
Ligne 1: | Ligne 1: | ||
====== Recherche rapide par dichotomie dans une liste triée ====== | ====== Recherche rapide par dichotomie dans une liste triée ====== | ||
+ | |||
+ | Dernière modification le 20/4/2009 | ||
===== Principe ===== | ===== Principe ===== | ||
Ligne 247: | Ligne 249: | ||
import time | import time | ||
- | def creafic(fichier, | + | def creafic(fichier, |
# fabrication de la liste à enregistrer | # fabrication de la liste à enregistrer | ||
- | L = [random.randint(i1, i2) for i in xrange(0, | + | L = [random.randint(I1, I2) for i in xrange(0, |
# tri de la liste | # tri de la liste | ||
Ligne 266: | Ligne 268: | ||
lg = 1000000 | lg = 1000000 | ||
lge = 5 | lge = 5 | ||
- | i1 = 1000 | + | I1 = 1000 |
- | i2 = 9999 | + | I2 = 9999 |
- | creafic(fichier, | + | |
- | print u" | + | t = time.clock() |
+ | creafic(fichier, | ||
+ | t = time.clock()-t | ||
+ | print u"création du fichier:", | ||
</ | </ | ||
- | Par exemple, avec creafic(" | + | Par exemple, avec creafic(" |
- | On va maintenant créer une fonction de lecture d'un enregistrement connaissant son indice, ainsi qu'une liste des indices croissants: | + | On va maintenant créer une fonction de lecture d'un enregistrement connaissant son indice, ainsi qu'une liste des indices croissants |
<code python> | <code python> | ||
Ligne 285: | Ligne 290: | ||
</ | </ | ||
- | On a toujours | + | Vous pouvez vérifier |
+ | |||
+ | <code python> | ||
+ | # verification | ||
+ | f = open(fichier, ' | ||
+ | for i in I: | ||
+ | print litdata(i) | ||
+ | |||
+ | f.close() | ||
+ | </ | ||
+ | |||
+ | On va utiliser maintenant les fonctions de recherche précédentes: dichot() pour la recherche dichotomique et seq() pour les recherches séquentielles. | ||
Et voilà le code d' | Et voilà le code d' | ||
Ligne 297: | Ligne 313: | ||
try: | try: | ||
c += 1 | c += 1 | ||
- | x = random.randint(i1-1, i2+1) | + | x = random.randint(I1-1, I2+1) |
t = time.clock() | t = time.clock() | ||
- | | + | |
t1 += time.clock()-t | t1 += time.clock()-t | ||
t = time.clock() | t = time.clock() | ||
- | | + | |
t2 += time.clock()-t | t2 += time.clock()-t | ||
- | print [r, i], litdata(i), t2/t1, t1/c | + | print x, [r1, i1], [r2, i2], litdata(i1), litdata(i2), t2/t1, t1/c |
except: | except: | ||
break | break | ||
f.close() | f.close() | ||
+ | </ | ||
+ | |||
+ | Ce qui affiche, par exemple: | ||
+ | |||
+ | < | ||
+ | 9097 [0, 900121] [0, 900121] 9097 9097 17305.7813651 0.000167109172573 | ||
+ | 4026 [0, 337762] [0, 337762] 4026 4026 17271.2771325 0.000167086643643 | ||
+ | 5159 [0, 463844] [0, 463844] 5159 5159 17267.2479243 0.000167060928584 | ||
+ | 8676 [0, 853399] [0, 853399] 8676 8676 17356.9558071 0.000167023901043 | ||
</ | </ | ||
Ligne 385: | Ligne 410: | ||
</ | </ | ||
- | Voilà. Maintenant, tout est en place pour la recherche | + | On va utiliser maintenant les fonctions de recherche précédentes: |
<code python> | <code python> |