Différences

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

--- dichotomie [2009/04/20 07:25]
tyrtamos
+++ dichotomie [2009/04/20 08:36]
tyrtamos
@@ Ligne 245: / Ligne 245: @@
 <code python>
 import random
+import time
 def creafic(fichier, lg, lge, i1, i2):
@@ Ligne 261: / Ligne 262: @@
         f.write(v + esp[:lge-len(v)])
     f.close()
+fichier = "datas.fad"
+lg = 1000000
+lge = 5
+i1 = 1000
+i2 = 9999
+creafic(fichier, lg, lge, i1, i2)
+print u"fichier créé:", fichier, lg, lge, i1, i2
 </code>
@@ Ligne 281: / Ligne 290: @@
 <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()
+        r,i = dichot(x, I, key=litdata)
+        t1 += time.clock()-t
+        t = time.clock()
+        r,i = seq(x, I, key=litdata)
+        t2 += time.clock()-t
+        print [r, i], litdata(i), t2/t1, t1/c
+    except:
+        break
+f.close()
+</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>
+Voilà. Maintenant, tout est en place pour la recherche par dichotomie:
+<code python>
 f = open(fichier, 'rb')
 t1 = 0
@@ Ligne 301: / Ligne 395: @@
     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 411: @@
 </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