Warning: Undefined array key -1 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/html.php on line 1458

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

--- dichotomie [2009/04/20 08:36]
tyrtamos
+++ dichotomie [2009/04/20 09:06]
tyrtamos
@@ Ligne 1: / Ligne 1: @@
 ====== Recherche rapide par dichotomie dans une liste triée ======
+Dernière modification le 20/4/2009
 ===== Principe =====
@@ Ligne 247: / Ligne 249: @@
 import time
-def creafic(fichier, lg, lge, i1, i2):
+def creafic(fichier, lg, lge, I1, I2):
     # fabrication de la liste à enregistrer
-    L = [random.randint(i1, i2) for i in xrange(0,lg)]
+    L = [random.randint(I1, I2) for i in xrange(0,lg)]
     # tri de la liste
@@ Ligne 266: / Ligne 268: @@
 lg = 1000000
 lge = 5
-i1 = 1000
+I1 = 1000
-i2 = 9999
+I2 = 9999
-creafic(fichier, lg, lge, i1, i2)
-print u"fichier créé:", fichier, lg, lge, i1, i2
+t = time.clock()
+creafic(fichier, lg, lge, I1, I2)
+t = time.clock()-t
+print u"création du fichier:", fichier, lg, lge, I1, I2, "en", t, "secondes"
 </code>
-Par exemple, avec creafic("datas.fad", 1000000, 5, 1000, 9999), on crée un fichier d'environ 5 Mo qui contiendra 1000000 d'entiers triés compris entre 1000 et 9999, placés dans des enregistrements de 5 octets.
+Par exemple, avec creafic("datas.fad", 1000000, 5, 1000, 9999), on crée un fichier d'environ 5 Mo qui contiendra 1000000 d'entiers triés compris entre 1000 et 9999, placés dans des enregistrements de 5 octets. Cette création prend environ 20 secondes.
-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 tel que I[i]=i:
 <code python>
@@ Ligne 285: / Ligne 290: @@
 </code>
-On a toujours la fonction de recherche séquentielle utilisée comme référence (fonction seq(): voir le test précédent)
+Vous pouvez vérifier la validité du fichier sur disque comme suit. Mais ne le faites pas pour le fichier d'1000000 de valeurs: cela demanderait trop de temps d'affichage.
+<code python>
+# verification
+f = open(fichier, 'rb')
+for i in I:
+    print litdata(i)
+print
+f.close()
+</code>
+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'essai, qui va calculer une valeur au hasard, va la trouver par les 2 méthodes (dichot et seq), et va comparer les temps de réponse. Le programme est prévu pour s'exécuter en boucle afin de stabiliser les résultats. Il doit donc être arrêté avec Ctle-C:
@@ Ligne 297: / Ligne 313: @@
     try:
         c += 1
-        x = random.randint(i1-1, i2+1)
+        x = random.randint(I1-1, I2+1)
         t = time.clock()
-        r,i = dichot(x, I, key=litdata)
+        r1,i1 = dichot(x, I, key=litdata)
         t1 += time.clock()-t
         t = time.clock()
-        r,i = seq(x, I, key=litdata)
+        r2,i2 = seq(x, I, key=litdata)
         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:
         break
 f.close()
+</code>
+Ce qui affiche, par exemple:
+<code>
+[0, 900121] [0, 900121] 9097 9097 17305.7813651 0.000167109172573
+[0, 337762] [0, 337762] 4026 4026 17271.2771325 0.000167086643643
+[0, 463844] [0, 463844] 5159 5159 17267.2479243 0.000167060928584
+[0, 853399] [0, 853399] 8676 8676 17356.9558071 0.000167023901043
 </code>
@@ Ligne 385: / Ligne 410: @@
 </code>
-Voilà. Maintenant, tout est en place pour la recherche par dichotomie:
+On va utiliser maintenant les fonctions de recherche précédentes: dichot() pour la recherche dichotomique et seq() pour les recherches séquentielles.
 <code python>

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page