Différences

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

--- tris_alpha [2011/09/18 10:06]
tyrtamos
+++ tris_alpha [2011/09/19 07:32]
tyrtamos
@@ Ligne 528: / Ligne 528: @@
 Avec Python 3.x, on utilise la même formule.
+===== Tests de performances =====
+Même si le tri utilisé (sort ou sorted) est très rapide, les fonctions de comparaison sont écrites en Python et analysent les chaines caractère par caractère: est-ce suffisamment rapide?
+Pour le vérifier, on va créer des chaines au hasard, et on va compter les temps de tri.
+Le nombre de chaines à créer est un paramètre. La longueur de chaque chaine est tirée au hasard entre 10 et 50 caractères. Et chaque caractère est tiré au hasard dans la chaine de référence alpha. Cela donne des chaines bizarres comme %%"+n?KMÏuK~fOA+$^-B Aå+ô)îg7mÊïbÇYè27Ÿ{x`Waks#iäïÏèp"%% mais qui conviennent parfaitement au test.
+<code python>
+from time import clock
+alpha = ur""" !"#$%&'()*+,-./0123456789:;<=>?@[\]^_`{|}~""" + \
+        u"\xA0" + \
+        u"€aAàÀâÂäÄåÅæÆbBcCçÇdDeEéÉèÈêÊëËfFgGhHiIîÎïÏjJ" + \
+        u"kKlLmMnNoOôÔöÖœŒpPqQrRsStTuUùÙûÛüÜvVwWxXyYÿŸzZ"
+lgalpha = len(alpha)
+L = []
+n = 1000
+for i in xrange(0,n):
+    lg = randint(10,50)
+    ch = u""
+    for j in xrange(0,lg):
+        ch += alpha[randint(0, lgalpha-1)]
+    L.append(ch)
+t = clock()
+L.sort(cmp=compalphafr)
+t = clock()-t
+print t
+</code>
+Résultats:
+  * 1000 chaines à trier: 5/100 seconde
+  * 10000 chaines à trier: 7/10 seconde
+  * 100000 chaines à trier: 10 secondes
+  * 1000000 chaines à trier: 2 minutes
+Ce qui n'est pas mal du tout pour du code interprété.
+Et pour la recherche dichotomique?
+Prenons la dernière liste de 1000000 (un million) de chaines, et voyons le temps nécessaire pour trouver l'une des chaines x dans cette liste:
+<code python>
+x = L[4999]
+t = clock()
+r = dichot(x, L, comp=compalphafr, key=None)
+t = clock()-t
+print r
+print t
+</code>
+ Le résultat correct ([0,4999]) est trouvé en... 2/10000 seconde! Ça vous suffira comme rapidité?

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page