Discussion :

[Invité]

Bonsoir !

Quel est le moyen le plus rapide que vous connaissiez pour vérifier si un string n'est pas déjà passé par là ? (Je trouve pas mieux comme formulation )

Pour vous éclairer j'ai pensé à un truc comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
def toto():
	dico = {}
	while True:
		string = get_string()
		try:
			if dico[string]:
				continue
		except KeyError:
			dico[string]=True
		#suite du code
		#...
		#...

Je me dis que c'est plus rapide qu'un element in list/dico/set/tuple ?

C'est pour gagner 3 femtosecondes =)

En espérant vous divertir un minimum, je vous remercie d'avance !

PS : Pour donner un ordre de grandeur, il peut y avoir un string par seconde si une touche a été saisie (grosso-modo), sinon 0.

[Sve@r]

Bonjour
A mon avis, sans même parler de 3 femtosecondes, utiliser seulement la clef d'un dictionnaire ça réduit l'utilité d'un dictionnaire. Rien que pour cette raison...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
def toto():
	check = set()		# Explicit better than implicit
	while True:
		string = get_string()
		if string in check: continue
		check.add(string)
		#suite du code
		#...
		#...
	# while
# toto()

[Invité]

J'avoue avoir du mal à comprendre comme ça marche, voici quelques tests :
• Dico versus in list :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> def toto():
	import time
	dico = {k:True for k in range(10**8)}
	liste = [i for i in range(10**8)]
	st = time.time()
	dico[9*10**7]
	print(time.time()-st)
	st = time.time()
	9*10**7 in liste
	print(time.time()-st)
 
 
>>> toto()
0.0
1.1505334377288818

• Dico versus in set :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> def toto():
	import time
	dico = {k:True for k in range(10**8)}
	ens = set(i for i in range(10**8))
	st = time.time()
	dico[9*10**7]
	print(time.time()-st)
	st = time.time()
	9*10**7 in ens
	print(time.time()-st)
 
 
>>> toto()
0.0
0.0

• Idem + temps de création :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
>>> def toto():
	import time
	st = time.time()
	dico = {k:True for k in range(10**8)}
	print(time.time()-st)
	st = time.time()
	ens = set(i for i in range(10**8))
	print(time.time()-st)
	st = time.time()
	dico[9*10**7]
	print(time.time()-st)
	st = time.time()
	9*10**7 in ens
	print(time.time()-st)
 
 
>>> toto()
6.901718616485596
9.620110511779785
0.0
0.0

Le set semble un peu plus lent pour gober les 100 millions, je pensais que le dictionnaire était plus lent.

Comment python arrive à trouver si rapidement le chiffre dans l'ensemble comparé à la liste ? Je ne me suis pas intéressé au hash, tout ça, tout ça...

[Sve@r]

voici quelques tests

Si tu veux tester, faut tester la réalité. Le but de ton programme est de manger des mots quand ça vient, tout en vérifiant si le mot a ou n'a pas déjà été vu (enfin c'est ce que j'ai compris). Donc il te faut faire un test sur un truc qui mange des mots tout en vérifiant si le mot a ou n'a pas été vu. Et non pas un test sur un accès unique au sein d'un dictionnaire (même gros)

Donc de fait...

Code python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#!/usr/bin/env python3
# coding: utf-8
 
import random
import string
 
# Génération de n mots de s lettres
def genere(n:int, s:slice):
	mot=list()
	# Le nb de lettres
	for i in range(s.start, s.stop+1):
		# Nb de mots (tous uniques)
		tmp=set()
		while len(tmp) < n: tmp.add("".join(random.sample(string.ascii_lowercase, i)))
		mot+=list(tmp)
	# for
 
	# On doit pouvoir faire ça en une ligne mais bon, faut pas non plus pousser mémé dans les orties
	return mot
# genere()
 
# La liste des mots de base (tous uniques)
base=genere(25000, slice(4, 8))
print("Base : %s" % len(base))
#print(base)
#exit(0)
 
# On duplique la liste de base n fois (comme ça on aura des mots déjà vus)
mots=base * 4
print("Mots : %s" % len(mots))
 
# Check des mots via set
def check_set(mots):
	check=set()
	for m in mots:
		if m in check: continue
		check.add(m)
	# for
	#print(len(check))
# check_set()
 
# Check des mots via list
def check_list(mots):
	check=list()
	for m in mots:
		if m in check: continue
		check.append(m)
	# for
	#print(len(check))
# check_list()
 
# Check des mots via dict
def check_dict(mots):
	check=dict()
	for m in mots:
		if m in check: continue
		check[m]=None
	# for
	#print(len(check))
# check_dict()
 
# Les fonctions à tester
import timeit
from functools import partial
fct={
	"set" : check_set,
	#"list" : check_list,
	"dict" : check_dict,
}
# Pour vérifier que les fonctions... fonctionnent
#for v in fct.values():
	#v(mots)
#exit(0)
 
# Le nombre de répétitions (les moyennes se feront sur cette valeur)
repeat=20
 
# Appel des fonctions dans un ordre aléatoire et affichage du chrono
print("start=%d, repeat=%d" % (len(mots), repeat))
for (k, v) in random.sample(fct.items(), len(fct)):
	t=timeit.Timer(partial(v, mots)).repeat(repeat=repeat, number=100)
	print("%s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t)/len(t)))
# for

Déjà, tu remarqueras que j'ai shunté la fonction check_list. Parce qu'elle est 15 fois plus longue que les autres.
Exemple avec une liste de 500 mots (base=genere(25, slice(4, 8)))...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
Base : 125
Mots : 500
start=500, repeat=20
set: min=0.001435, max=0.006349, avg=0.001699
dict: min=0.001553, max=0.001614, avg=0.001574
list: min=0.023052, max=0.023215, avg=0.023111

Donc quand je suis passé à une liste de 500 000 mots j'ai préféré ne plus la faire tourner (pas envie d'attendre 45 minutes !!!).
Et donc avec 500 000 mots (base=genere(25000, slice(4, 8)))...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Base : 125000
Mots : 500000
start=500000, repeat=20
dict: min=3.006534, max=3.409227, avg=3.137333
set: min=2.626279, max=2.834728, avg=2.714757

Et là, le set reprend ses droits ce qui me semble assez normal (plus léger qu'un dico car il offre moins de possibilités, ça me semble donc normal qu'il soit plus rapide).

Je ne me suis pas intéressé au hash, tout ça, tout ça...

Hum... tu as bien conscience que si ça t'intéresse, alors tu dois t'y intéresser un minimum car on ne pourra pas s'y intéresser pour toi (ceux qui s'y sont intéressés ne peuvent pas te transmettre le résultat de leur intéressement par télépathie). Et donc quand on s'y intéresse, on se rend alors compte qu'un dico c'est super chouette quand on l'utilise, mais qu'en réalité, au bout du bout de l'assembleur, on n'a que des tableaux. Donc traduire dico[truc] en tableau[indice] quelque part il faut un peu de techno et cette techno c'est le hash.

Et puis intéresse-toi aussi à timeit car comme tu peux le voir avec les différents exemples que je t'ai montrés, c'est pas super difficile à utiliser. Le plus compliqué c'est de créer les datas et les fonctions qui font le job et qu'on veut tester. Ensuite la procédure que j'utilise est toujours la même

• je stocke les fonctions dans un iterable qui permettra de les traiter via une boucle. Ici un dictionnaire est alors sympa car il permet d'associer la fonction à son nom, ce qui est pratique lors de l'affichage
• je demande un timeit.Timer().repeat() sur chaque fonction à laquelle j'associe automatiquement via partial les datas à traiter (cette partie a été au départ le plus difficile à comprendre mais maintenant c'est réglé). Et ça me retourne une liste de tous les temps d'exécutions lors des appels. Ne me reste plus qu'à traiter cette liste

[Invité]

Merci !

Belle performance de PC ! (2x plus rapide que mon PC, Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz )

Effectivement avec ton test ça me paraît plus cohérent même si j'imaginais une plus grosse différence. J'ai constaté également que remplacer le if m in check ... par try : check[m] ... est moins performant.

Hum... tu as bien conscience que si ça t'intéresse, alors tu dois t'y intéresser un minimum car on ne pourra pas s'y intéresser pour toi

Oui évidemment . Une question plus précise alors : est-ce que dans "mot" in set(["toto"]) python transforme "mot" en hash tout seul avant d'aller voir dans la table ? Ou c'est pas comme ça que marche le bazard ?

---

Si jamais tu tournes avec une "vieille" version de Python :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for (k, v) in random.sample(fct.items(), len(fct)):
DeprecationWarning: Sampling from a set deprecated
since Python 3.9 and will be removed in a subsequent version.

Pour l'instant je ne vois pas trop l'intérêt de timeit, la méthode que j'utilise semble donner les mêmes résultats.

[wiztricks]

est-ce que dans "mot" in set(["toto"]) python transforme "mot" en hash tout seul avant d'aller voir dans la table ? Ou c'est pas comme ça que marche le bazard ?

Le bazar marche a peu près comme décrit dans cet article de Wikipédia.

- W

[Sve@r]

Belle performance de PC ! (2x plus rapide que mon PC, Intel(R) Core(TM) i7-10750H CPU @ 2.60GHz )

OctalCore Intel Core i9-9900K, 3600 MHz (36 x 100), 64Go de RAM. Me suis fait un petit cadeau en 2020 (juste avant le COVID). Et mes tests sont faits sur une VM VirtualBox.

Oui évidemment . Une question plus précise alors : est-ce que dans "mot" in set(["toto"]) python transforme "mot" en hash tout seul avant d'aller voir dans la table ? Ou c'est pas comme ça que marche le bazard ?

Tu peux créer ton propre opérateur "in" sur ton objet en lui créant la méthode "__contains__". Ensuite tout truc in monObjet() fera appel à cette méthode. Nul doute que l'objet "set" possède cette méthode "__contains__" qui se charge de gérer "mot" in set(["toto"]).
Maintenant est-ce que "mot" est hashé lors de la recherche? A mon avis oui. Mais mon avis seul, bien que brillant, ne remplace pas ton propre test. Pour ça te suffit de regarder avec un truc "non hashable" (exemple un dict) et t'as ta réponse => dict() in set(). Et effectivement tu verras que mon avis était vraiment brillant

Si jamais tu tournes avec une "vieille" version de Python :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
for (k, v) in random.sample(fct.items(), len(fct)):
DeprecationWarning: Sampling from a set deprecated
since Python 3.9 and will be removed in a subsequent version.

Suis en 3.8.10. Je regarderai quand le moment sera venu. Si sample() disparait je pense que ce sera au bénéfice de choices() qui peut faire la même chose plus d'autres.

Pour l'instant je ne vois pas trop l'intérêt de timeit, la méthode que j'utilise semble donner les mêmes résultats.

Un check peut ne pas suffire. Ton PC peut avoir une faiblesse (ou au contraire la chance d'être dispo) à ce moment là. timeit fait "repeat" tests de "numbers" itérations. Le "repeat" c'est le nombre de chronos qu'il te sort et le "numbers" c'est le nombre de fois qu'il appelle la fonction à chaque chrono. Avec repeat=20 et numbers=100 il va créer 20 chronos, chaque chrono mesurant le temps d'exécution de 100 appels. Et en plus il se charge de la mesure lui-même (plus besoin de t'embêter avec tes time() en début et fin). C'est tout bénef (tu peux tout lui paramétrer, et même le paramétrer pour qu'il fasse pareil que ta méthode si tu veux, ou qu'il fasse mieux)...