Discussion :

[Beginner.]

Salut,

Je m’interroge sur les performances concernant l’accès à une propriété via sa clé des dictionnaire (ou des objets en JS)...

Je pense que c'est plus rapide que de rechercher une clé dans une liste (ou un tableau) mais qu'en est-il de la recherche par dichotomie dans une liste triée ?

[wiztricks]

Salut,

Les tables de hash et la rechercher dans des arbres/listes est un sujet d'algorithmique et non spécifique à Python.
Et comme pour n'importe quel sujet, chercher un peu sur Internet avant de demander de l'aide peut être intéressant. On y trouve des article comme celui ci qui explique relativement bien tout ça.

- W

[Beginner.]

Merci.

Dans le lien ils comparent surtout avec la recherche classique (non dichotomique) dans un tableau or pour ce cas comme déjà dit je me doute que l’accès à une propriété via sa clé est plus rapide...

Je m'interrogeais surtout sur la comparaison avec une recherche par dichotomie dans une liste triée...

Bon en fait j'avais déjà eu une réponse via une IA mais je voulais aussi en discuter ne serait-ce par qu'il nous faut vérifier les réponses des IA...

[papajoker]

En fait , je ne comprends rien à ta question.

Si on utilise un dico, alors ce n'est pas une recherche, c'est un accès direct à un seul l'élément.

Si tu désires une recherche (sur la clé du dico ????), quel que soit l'algo, tu va remplacer un accès direct à des dizaines... milliers d'accès. Quel est le plus rapide ?
Si tu travailles avec une list() python, pourquoi ne pas faire dès le départ un dict() ?

Tu parles d'une recherche sur le contenu ? alors pourquoi nous parler de clé ... c'est comparer des voitures à des maisons.

[Beginner.]

Ok je vais donc donner un exemple pour expliquer :

Supposons que j'ai une liste de mots en français et une autre en anglais (traduction des mots français).

Je pourrais utiliser :

un dictionnaire

• les clés --> les mots français
• les valeurs --> les mots en anglais correspondants

ou deux listes :

• une liste triée des mots français
• une liste des mots anglais correspondants

J'ai un mot français (exemple "porte") dont je cherche la traduction en anglais...

• Je peux chercher "porte" par dichotomie dans la liste triée des mots français, récupérer l'indice pour ensuite récupérer le mot anglais correspondant...
• Je peux utiliser la clé "porte" dans le dictionnaire

Qu'est-ce qui est le plus rapide ?

[Beginner.]

Si on utilise un dico, alors ce n'est pas une recherche, c'est un accès direct à un seul l'élément.

Oui mais est-ce un accès direct comme l’accès à une valeur contenue dans une variable via le nom de cette dernière ?

Apparemment non, une table de hachage est utilisée...

Code python :

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

1
2
3
4
5
6
7
porte="door"
dic= {
"porte": "door",
}

print(porte)
print(dic["porte"])

L’accès au mot "door" via la variable porte est-il identique à l’accès via la clé porte dic["porte"] ?

[wiztricks]

Qu'est-ce qui est le plus rapide ?

Ca se teste après avoir étudié la complexité (algorithmique) de chaque solution (sinon le plan de test risque de ne pas les tester "correctement" (*)).
(*) chercher séquentiellement dans une liste ordonnée sera plus rapide lorsqu'on trouve dans les premiers items que quand on devra parcourir toute la liste pour réaliser qu'il n'existe pas.

L’accès au mot "door" via la variable porte est-il identique à l’accès via la clé porte dic["porte"] ?

On fait un get dans le dictionnaire globals() pour récupérer l'objet associé à porte ou à dic (2 variables globales) puis un autre get pour aller chercher l'objet associé à la clef "porte".

2 get au lieu d'un seul seront plus couteux mais est ce qu'on peut s'en passer? Il y a une différence entre voilà comment python fonctionne (il faut souvent faire avec) et les algorithmes que je vais pouvoir utiliser pour résoudre un problème particulier (là on peut choisir en fonction de critères +/- objectifs).

- W

[f-leb]

Bonjour,

un dictionnaire

• les clés --> les mots français
• les valeurs --> les mots en anglais correspondants

ou deux listes :

• une liste triée des mots français
• une liste des mots anglais correspondants

J'ai un mot français (exemple "porte") dont je cherche la traduction en anglais...

• Je peux chercher "porte" par dichotomie dans la liste triée des mots français, récupérer l'indice pour ensuite récupérer le mot anglais correspondant...
• Je peux utiliser la clé "porte" dans le dictionnaire

Qu'est-ce qui est le plus rapide ?

En termes de complexité en temps, l'accès à une valeur du dictionnaire par sa clé se fait en temps constant en général O(1), voir TimeComplexity.

L'algo dichotomique est sans doute plus performant qu'une recherche séquentielle, mais il faut quand même trier la liste avant...

[Beginner.]

(*) chercher séquentiellement dans une liste ordonnée sera plus rapide lorsqu'on trouve dans les premiers items que quand on devra parcourir toute la liste pour réaliser qu'il n'existe pas.

C'est le cas avec une recherche classique mais avec une recherche dichotomique cela ne devrait pas changer grand chose si l’élément est au début ou à la fin, non ? Dans les deux cas on ne parcourt pas toute la liste, non ?

On fait un get dans le dictionnaire globals() pour récupérer l'objet associé à porte ou à dic (2 variables globales) puis un autre get pour aller chercher l'objet associé à la clef "porte".

2 get au lieu d'un seul seront plus couteux mais est ce qu'on peut s'en passer? Il y a une différence entre voilà comment python fonctionne (il faut souvent faire avec) et les algorithmes que je vais pouvoir utiliser pour résoudre un problème particulier (là on peut choisir en fonction de critères +/- objectifs).

Oui ok, c'est donc moins direct quand même... Mais sinon oui on ne va se passer d'un dictionnaire à cause de ça...

[Beginner.]

En termes de complexité en temps, l'accès à une valeur du dictionnaire par sa clé se fait en temps constant en général O(1), voir TimeComplexity.

Oui effectivement j'avais vu que c'était O(1) sauf cas particulier... Je vais regarder le lien...

L'algo dichotomique est sans doute plus performant qu'une recherche séquentielle, mais il faut quand même trier la liste avant...

Oui c'est vrai qu'il faut trier la liste !

[wiztricks]

C'est le cas avec une recherche classique mais avec une recherche dichotomique cela ne devrait pas changer grand chose si l’élément est au début ou à la fin, non ? Dans les deux cas on ne parcourt pas toute la liste, non ?

Chaque algo a sa complexité. Il y a des tas d'articles de wikipedia détaillés pour vous forger une opinion informée. Et pour chaque algo. il y aura sans doute des cas "favorables" et des cas "defavorables".
Mon exemple était là pour dire qu'il fallait étudier les choses et faire attention a ce qu'on faisait, pas pour que vous rebondissiez dessus pour remarquer que cet exemple n'était pas vrai partout.

Après en plus de la complexité de l'algo, des cas favorables ou pas,... il y a aussi le profil des requêtes qui seront fait et qui iront taper là où il faut ou pas.

Et ce boulot là c'est des lignes de code à écrire pour "tester"... boulot que des discutailles dans un forum ne feront pas.

- W

[papajoker]

Comme écrit plus haut, je ne comprends pas que tu ne fases pas un mini test avec une dizaine de lignes (+ long que de demander à IA et plus ici ?)

Je pourrais utiliser :
un dictionnaire

• les clés --> les mots français
• les valeurs --> les mots en anglais correspondants

en gros:

Code :

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

1
2
3
4
5
6
7
NB = 200_000  # 100 000 est plus juste ?
cherches = list(f"{randint(0, NB-1)}_fr" for x in range(12_000))
 
en = {f"{x}_fr": f"{x}_en" for x in range(NB)}
for key_fr in cherches:
    trad = en[key_fr]
    print(key_fr, trad)

une recherche/traduction de 12 000 mots différents ... (ordre d'une seconde !)

ou deux listes :

• une liste triée des mots français
• une liste des mots anglais correspondants

• Je peux chercher "porte" par dichotomie dans la liste triée des mots français, récupérer l'indice pour ensuite récupérer le mot anglais correspondant...
• Je peux utiliser la clé "porte" dans le dictionnaire

suis perdu, si je te lis et écrit exactement ce que tu décris ...

Code :

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

1
2
3
4
5
6
fr = list(f"{x}_fr" for x in range(NB))
en = list(f"{x}_en" for x in range(NB))
for key_fr in cherches:
    fr_id = monAlgo_search(fr, key_fr)   # chercher "porte" par dichotomie dans la liste triée des mots français
    trad = en[fr_id]     # utiliser la clé "porte" dans le dictionnaire
    print(key_fr, trad)

reste à utiliser timeit si tu as un doute / réel besoin

[wiztricks]

Comme écrit plus haut, je ne comprends pas que tu ne fase pas un mini test avec une dizaine de lignes (+ long que de demander à IA et plus ici ?)

Le problème des tests n'est pas juste mesurer et prendre ce qui est meilleur mais de le calculer à priori et vérifier ensuite que ça le fait ou comprendre pourquoi ca ne le fait pas. Surtout lorsqu'on projette d'écrire une application qui devra gérer des requêtes d'utilisateurs humains.

- W

[papajoker]

pas juste mesurer et prendre ce qui est meilleur

Je n'ai pas comparé ! Avec un simple dico de 200 000 mots, je retrouve la valeur de 12 000 "clés" (existantes ou pas) en moins d'une seconde sur une mini-machine. Pourquoi, je penserais à complexifier la chose pour gagner des nano secondes. Il y a un réel besoin ? ou plutôt, Beginner. se pose la question sans avoir fait le moindre test ?

A mon avis, le traitement de ce que l'on va faire de ce mot trouvé peut prendre autant de temps ou bien plus (on va "reconstruire" dans cette boucle un énorme texte ?)

Code :

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

1
2
3
4
5
6
7
8
9
10
NB = 200_000
cherches = list(f"{randint(0, NB*2)}_fr" for x in range(120_000))
en = {f"{x}_fr": f"{x}_en" for x in range(NB)}
for key_fr in cherches:
    try:
        trad = en[key_fr]
        # print(trad)       # resultat = f"{resultat} {trad}"  # 
    except:
        pass
        # print("non trouvé")

[wiztricks]

La question posée est:

Je pense que c'est plus rapide que de rechercher une clé dans une liste (ou un tableau) mais qu'en est-il de la recherche par dichotomie dans une liste triée ?

Ce qui se résume à comparer les O... ou a se fier à la remarque du chapitre performance du module bisect:

When writing time sensitive code using bisect() and insort(), keep these thoughts in mind:

Bisection is effective for searching ranges of values. For locating specific values, dictionaries are more performant.

et on se pose des questions suivant le résultat de tests.

- W

[Sve@r]

Bonjour

Comme écrit plus haut, je ne comprends pas que tu ne fases pas un mini test avec une dizaine de lignes

J'ai tenté d'écrire un tel test avec timeit pour mesurer les différences en essayant d'être le plus impartial et exhaustif possible

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
#!/usr/bin/env python
# coding: utf-8
 
nb=2_000_000
prec=len(str(nb))
mot_fr_l=tuple("fr_%*d" % (prec, i) for i in range(nb))
mot_en_l=tuple("en_%*d" % (prec, i) for i in range(nb))
mot_list=(mot_fr_l, mot_en_l)
 
mot_dict=dict(("fr_%*d" % (prec, i), "en_%*d" % (prec, i)) for i in range(nb))
 
import bisect
def algo_list(mots, key):
	idx=bisect.bisect_left(mots[0], key)
	if idx == len(mots[0]): return None
	return mots[1][idx]
 
def algo_dict(mots, key): return mots.get(key)
 
import timeit
import random
from functools import partial
 
# Les fonctions à tester
fct={
	"list" : partial(algo_list, mot_list),
	"dict" : partial(algo_dict, mot_dict),
}
 
# Le nombre de répétitions
repeat=20
 
print("taille data=%d, repeat=%d" % (nb, repeat))
# Mot dans la première moitié
for (k, v) in random.sample(tuple(fct.items()), len(fct)):
	# Création du mot à chercher
	find="fr_%*d" % (prec, random.randint(0, nb // 2))
 
	# Vérification algorithmes renvoient la même valeur
	assert fct["list"](find) == fct["dict"](find)
	t=timeit.Timer(partial(v, find)).repeat(repeat=repeat, number=500_000)
	print("avec mot première moitié: %s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t)/len(t)))
# for
 
# Mot dans la seconde moitié
for (k, v) in random.sample(tuple(fct.items()), len(fct)):
	# Création du mot à chercher
	find="fr_%*d" % (prec, random.randint(nb // 2, nb-1))
 
	# Vérification algorithmes renvoient la même valeur
	assert fct["list"](find) == fct["dict"](find)
	t=timeit.Timer(partial(v, find)).repeat(repeat=repeat, number=500_000)
	print("avec mot seconde moitié: %s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t)/len(t)))
# for
 
# Mot inexistant
for (k, v) in random.sample(tuple(fct.items()), len(fct)):
	# Création du mot à chercher
	find="fr_xxx"
 
	# Vérification algorithmes renvoient la même valeur
	assert fct["list"](find) == fct["dict"](find)
	t=timeit.Timer(partial(v, find)).repeat(repeat=repeat, number=500_000)
	print("avec mot non existant: %s: min=%f, max=%f, avg=%f" % (k, min(t), max(t), sum(t)/len(t)))
# for

Résultat

Code :

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

1
2
3
4
5
6
7
8
$ python3 test.py 
taille data=2000000, repeat=20
avec mot première moitié: dict: min=0.041890, max=0.042464, avg=0.042110
avec mot première moitié: list: min=0.233721, max=0.252171, avg=0.238610
avec mot seconde moitié: dict: min=0.041898, max=0.052899, avg=0.042898
avec mot seconde moitié: list: min=0.215820, max=0.233953, avg=0.222467
avec mot non existant: dict: min=0.037993, max=0.052689, avg=0.039179
avec mot non existant: list: min=0.198439, max=0.212129, avg=0.202436

Il semble que la recherche par dictionnaire soit dans tous les cas la plus rapide (x6)

[wiztricks]

Il semble que la recherche par dictionnaire soit dans tous les cas la plus rapide (x6)

Ce qui est réconfortant puisque conforme à la théorie.

- W

[Beginner.]

Salut,

Merci à vous tous pour vos réponses...

Merci en particulier à Sve@r pour le teste.

[wiztricks]

Merci en particulier à Sve@r pour le teste.

Si vous ne testez pas en fonction du profil des requêtes des utilisateurs, on vérifie juste que les calculs théoriques sont "justes".
Le test aurait été instructif si les résultats étaient différents de ceux calcules: là, il aurait fallu chercher pourquoi et se poser des questions sur le code et/ou le profil des requetes.

- W

[papajoker]

Merci en particulier à Sve@r pour le teste.

Mais ce test est-il nécessaire ?

Comme écrit plus haut, il y a toutes les chances que le goulot d'étrangement est avant et après (la recherche dans le dico) ! Donc pourquoi demandes-tu ceci ????

Etait a faire:
1) mon premier test : énorme boucle sur énorme dico juste pour voir si lent
2) second test (uniquement si test1 est trop lent pour moi !): avec tes (propres) entrées et sorties et, dévalider ou non le dico, par exemple:

Code :

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

1
2
3
4
5
with open(fichier) as ffrancais:
   for mot_fr in ffrancais:
        if mot_en := dictionnaire.get(mot_fr):  # test 2 : ralentisseur d'utiliser un dict ?
        #if mot_en := mot_fr:                         # test 1 : est négligeable ?
              f_sortie.write(mot_en+"\n")

Il y a toutes les chances que "test1" et test2 sont équivalents en vitesse
Alors pourquoi vouloir optimiser une chose qui ne compte pas ? C'est simplement une perte de temps pour rien.


#########################

J'espère que ton besoin n'est pas de traduire des phrases car le remplacement mot par mot donne clairement des choses plus que approximatives.

Si le texte n'est pas confidenciel, application a usage unique, on peut regarder du coté des api ...
Par exemple gemini nous propose une api gratuite "limitée"() à 15 requetes par minute / 1 million de jetons par minute / 1 500 requêtes par jour (1 mot ≈ 2..3 tokens en entrée(fr) et en sortie(en))