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 07:25]
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 245: / Ligne 247: @@
 <code python>
 import random
+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 261: / Ligne 264: @@
         f.write(v + esp[:lge-len(v)])
     f.close()
+fichier = "datas.fad"
+lg = 1000000
+lge = 5
+I1 = 1000
+I2 = 9999
+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 276: / 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:
 <code python>
+f = open(fichier, 'rb')
+t1 = 0
+t2 = 0
+c = 0
+while True:
+    try:
+        c += 1
+        x = random.randint(I1-1, I2+1)
+        t = time.clock()
+        r1,i1 = dichot(x, I, key=litdata)
+        t1 += time.clock()-t
+        t = time.clock()
+        r2,i2 = seq(x, I, key=litdata)
+        t2 += time.clock()-t
+        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>
+Le résultat est époustouflant: on trouve une valeur au hasard parmi un million de valeurs sur disque en moins d'1/1000 secondes, et c'est 17000 fois plus rapidement qu'avec la méthode séquentielle...
+Ça vous suffit comme performance? :-D
+NB: je ne connais pas l'impact des buffers disques sur ce résultat (essai fait sur Windows XP SP3 en raid 1). Cependant, le temps est le même quand on prend successivement une petite valeur (1500), une moyenne (5000) et une grande (9500).
+===== Recherche indexée dans un fichier sur disque =====
+On se propose ici de rechercher des valeurs par dichotomie avec un fichier disque **non trié**, et sans charger ce fichier en mémoire. On va donc créer un fichier d'index qui, lui, sera en mémoire, et qui permettra de retrouver triées les données du fichier sur disque. Grâce à ce fichier d'index, on va pouvoir chercher n'importe quelle valeur par dichotomie avec le même niveau de performance!
+On va d'abord créer un fichier d'essai comme précédemment, mais sans l'avoir trié avant de d'enregistrer les valeurs:
+<code python>
+import random
 import time
+def creafic(fichier, lg, lge, i1, i2):
+    # fabrication de la liste à enregistrer
+    L = [random.randint(i1, i2) for i in xrange(0,lg)]
+    # creation du fichier sur disque
+    f = open(fichier, 'wb')
+    esp = ' '*lge
+    for i in range(0, len(L)):
+        f.seek(i*lge)
+        v = "%s" % L[i]
+        f.write(v + esp[:lge-len(v)])
+    f.close()
 fichier = "datas.fad"
 lg = 1000000
 lge = 5
-i1 = int('1' + '0'*(lge-2))
+I1 = 1000
-i2 = int('9'*(lge-1))
+I2 = 9999
-print u"création du fichier:", 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>
+La création de ce fichier d'1 million d'entiers tirés au hasard prend environ 20 secondes.
+Maintenant, on va créer un fichier d'index et trier ce fichier pour retrouver les données du fichier sur disque dans l'ordre numérique croissant:
+<code python>
+def litdata(i):
+    global f, lge
+    f.seek(i*lge)
+    return int(f.read(lge).strip())
-creafic(fichier, lg, lge, i1, i2)
 I = [i for i in xrange(0,lg)]
-print u"fichier disque créé"
+f = open(fichier, 'rb')
+t = time.clock()
+I.sort(key=litdata)
+t = time.clock()-t
+f.close()
+print u"fichier d'index créé et trié en ", t, "secondes"
+</code>
+La création de ce fichier d'index a pris environ 7 secondes. Grâce à ce fichier, on peut retrouver toutes les données du fichier sur disques dans l'ordre numérique croissante.
+Si vous voulez le vérifier, vous pouvez afficher les données du disque dans cet ordre comme suit. Mais ne le faites pas pour le fichier de 1000000 de valeurs: cela demandera trop de temps pour l'affichage.
+<code python>
+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.
+<code python>
 f = open(fichier, 'rb')
 t1 = 0
@@ Ligne 301: / Ligne 420: @@
     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(I[i1]), litdata(I[i2]), t2/t1, t1/c
     except:
         break
@@ Ligne 317: / Ligne 436: @@
 </code>
-Le résultat est époustouflant:
+Le code ci-dessus (qu'on arrête avec Ctrl-C) affiche les résultats comme suit:
-  * On trouve une valeur au hasard parmi un million de valeurs sur disque en 1.7/10000 secondes, et c'est 17000 fois plus rapidement qu'avec la méthode séquentielle...
+<code>
+[0, 813361] [0, 813361] 8317 8317 17537.9140573 0.000173003674181
-Ça vous suffit comme performance? :-D
+[0, 830810] [0, 830810] 8476 8476 17587.4199338 0.000173009098294
+[0, 377556] [0, 377556] 4398 4398 17571.9584712 0.000172991006654
-NB1: je ne connais pas l'impact des buffers disques sur ce résultat (essai fait sur Windows XP SP3 en raid 1). Cependant, le temps est le même quand on prend successivement une petite valeur (1500), une moyenne (5000) et une grande (9500).
+[0, 504304] [0, 504304] 5537 5537 17575.2446774 0.000172973807046
+</code>
-NB2: j'ai pris ici un fichier disque trié, mais on peut prendre aussi facilement un fichier disque non trié et utiliser un fichier index.
+Ce qui montre une performance quasi identique au test précédent: le passage par une liste d'index n'a donc pas ralenti sensiblement le temps de recherche: la recherche dichotomique sur disque, avec ou sans index, est vraiment une méthode performante!
 \\

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page