Comparaison vitesse algo

Bonjour,

Je suis en train de m'amuser à comparer la vitesse de différentes fonctions Python. Pour cela, j'ai écrit deux fonctions qui calculent les nombres premiers dans un intervalle de 1 à x. Bizarrement, les résultats vont à l'encontre de ce à quoi je m'attendais:

La première fonction, bête et méchante:

Code:

---

1 2 3 4 5 6 7 8 9 10 11

def prime1(x): a = time.time() liste = [] for i in range(1, x+1): for j in range(2, i+1): if i % j == 0 and i != j: break else: if j == i: liste.append(i) b = time.time() print b - a

---

La deuxième, implémente le crible d'Erathostène:

Code:

---

1 2 3 4 5 6 7 8

def prime2(x): a = time.time() liste = range(1,x+1,2) for i in range(2, x+1): liste = filter( lambda x: x % i != 0 or x == i, liste) b = time.time() print b - a

---

Intuitivement, je pensais que la seconde version sera beaucoup plus rapide, d'autant plus que l'on évite de vérifier tous les nombres pairs avec le range(1, x+1, 2) et que la fonction filter, implémentée en C est censée être plus rapide, et pourant:

>>> prime1(10000)
1.21399998665
>>> prime2(10000)
2.10899996758
>>> prime1(100000)
106.244999886
>>> prime2(100000)
167.480000019

Mais là où je suis encore plus étonné, c'est qu'en remplaçant les deux "range" par des "xrange", censés être plus économiques, la fonction prime2 n'accélère pas, voire parfois est légèrement encore plus lente....
Quelqu'un aurait-il une explication ? :roll:

Merci d'avance

Citation:

---

Envoyé par JacekB

Intuitivement, je pensais que la seconde version sera beaucoup plus rapide, d'autant plus que l'on évite de vérifier tous les nombres pairs avec le range(1, x+1, 2) et que la fonction filter, implémentée en C est censée être plus rapide.

---

Vous appelez .append pour ajouter un nombre premier à une liste, vous appelez filter + lambda beaucoup plus souvent.

Citation:

---

Envoyé par JacekB

Mais là où je suis encore plus étonné, c'est qu'en remplaçant les deux "range" par des "xrange", censés être plus économiques, la fonction prime2 n'accélère pas, voire parfois est légèrement encore plus lente....

---

La différence entre range et xrange est plutôt "économie" de mémoire utilisée (on crée la liste avant d'iterer avec range, on génére les nombres au fur et à mesure avec xrange) dont le bénéfice (l'overhead de l'allocation de la mémoire) n'est visible que lorsque N est (très) grand.

- W

salut,

j'ajouterai que dans prime2(), si x=4 par exemple, tu vas vérifier la totalité des nombres i de la liste, comme 4 % 75341 par exemple, là où dans prime1 ta boucle n'allait pour chaque nombre que jusqu'à x+1 (donc 5 dans l'exemple), m'est avis que la lenteur vient de là.

Edit: d'ailleurs à mieux y regarder, ton implémentation du crible est complètement fausse et la fonction ne calcule pas ce qu'elle devrait