Accès à une propriété via sa clé [performance]

Version imprimable

31/10/2024, 20h40
Beginner.

Accès à une propriété via sa clé [performance]

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 ?
01/11/2024, 09h26
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
01/11/2024, 15h03
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...
01/11/2024, 15h30
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 ? :roll:
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.
01/11/2024, 16h16
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 ?
01/11/2024, 16h33
Beginner.
Citation:

Envoyé par papajoker

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:

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"] ?
01/11/2024, 16h34
wiztricks

Citation:

Envoyé par Beginner.

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.

Citation:

Envoyé par Beginner.

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
01/11/2024, 16h52
f-leb
Bonjour,
Citation:
Envoyé par Beginner.

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...
01/11/2024, 17h00
Beginner.

Citation:

Envoyé par wiztricks

(*) 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 ?

Citation:

Envoyé par wiztricks

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...
01/11/2024, 17h05
Beginner.

Citation:

Envoyé par f-leb

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...

Citation:

Envoyé par f-leb

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 !
01/11/2024, 17h33
wiztricks

Citation:

Envoyé par Beginner.

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

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 ?)

Citation:

Envoyé par Beginner.

Je pourrais utiliser :
un dictionnaire

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

en gros:
Code:

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 !)

Citation:

Envoyé par Beginner.

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:

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

01/11/2024, 19h20
wiztricks

Citation:

Envoyé par papajoker

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

Citation:

Envoyé par wiztricks

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:

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é")

01/11/2024, 22h07
wiztricks

La question posée est:

Citation:

Envoyé par Beginner.

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:

Citation:

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

Bonjour

Citation:

Envoyé par papajoker

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:

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:

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)

04/11/2024, 14h04
wiztricks

Citation:

Envoyé par Sve@r

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
04/11/2024, 17h46
Beginner.

Salut,

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

Merci en particulier à Sve@r pour le teste.
04/11/2024, 18h30
wiztricks

Citation:

Envoyé par Beginner.

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

Citation:

Envoyé par Beginner.

Merci en particulier à Sve@r pour le teste.

Mais ce test est-il nécessaire ? :roll:

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:

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"(:D) à 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))

05/11/2024, 14h58
Beginner.

Salut,

Citation:

Envoyé par papajoker

Mais ce test est-il nécessaire ?

Ben c'est toujours bon à prendre, cela nous informe et confirme la théorie comme vous l'avez vous-mêmes rappelé dans ce fil...

Après, à la base, j'ai aussi ouvert ce fil pour discuter, échanger des idées, des informations...
Par exemple en discutant de ce sujet j'ai appris qu'une table de hachage était utilisée pour les clés des dictionnaires et c'est ce qui explique que l’accès à une propriété via sa clé est rapide et ce temps d’accès n'augmente pas avec le nombre de propriétés...

Citation:

Envoyé par papajoker

Alors pourquoi vouloir optimiser une chose qui ne compte pas ? C'est simplement une perte de temps pour rien.

Ben la question de mettre en œuvre une optimisation ne se pose éventuellement qu’après les tests... On ne va effectivement pas chercher à optimiser si cela ne vaut pas le coup... Mais pour choisir entre plusieurs solutions il faut bien les comparer auparavant...

Citation:

Envoyé par papajoker

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"(:D) à 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))

Merci, oui j'avais vu qu'on pouvait utiliser Gemini via une api avec un quota gratuit... Mais en fait pour la traduction, je ne suis pas sûr que ce soit la meilleure solution... Il existe des services de traduction qui sont plus rapide et moins chers avec un quota gratuit...

Même certains services en ligne gratuits peuvent être utilisés "automatiquement" (via programmation) mais par contre je ne sais pas si cela est légal/autorisé...
05/11/2024, 15h36
wiztricks

Citation:

Envoyé par Beginner.

Par exemple en discutant de ce sujet j'ai appris qu'une table de hachage était utilisée pour les clés des dictionnaires et c'est ce qui explique que l’accès à une propriété via sa clé est rapide et ce temps d’accès n'augmente pas avec le nombre de propriétés...

Certes mais vous êtes supposé chercher un peu par vous même avant de poser des questions non?

- W
05/11/2024, 16h46
Beginner.

Citation:

Envoyé par wiztricks

Certes mais vous êtes supposé chercher un peu par vous même avant de poser des questions non?

Ben comme déjà dit, j'ai déjà fait une recherche avant d'ouvrir ce fil (ce n'est pas durant cette présente discussion que j'ai appris qu'une table de hachage était utilisée pour les clés des dictionnaires).

Ensuite on peut toujours chercher ailleurs avant de venir ici mais du coup, pourquoi venir ici ? Ben oui les moyens de recherche sont devenus plus efficaces avec l'IA du coup on aura souvent nos réponses ailleurs et alors le forum ne sert plus à trouver des réponses...

Mais si on raisonne comme ça, pourquoi garder ce forum ? On peut renvoyer tout le monde aux moteurs de recherche et aux services d'IA (pour chercher sous forme de discussion)...

En ce qui me concerne, j'aime bien discuter avec d'autres être humains, j'aime connaitre les idées des autres, voir comment ils abordent tel ou tel sujet, connaitre leur truc et astuces...

L'IA par exemple nous donnera une solution toute faite, on peut même interroger plusieurs IA différentes pour comparer ... Mais n’empêche que je pourrais quand même avoir envie de discuter avec des humains pour connaitre leurs solutions, leurs idées, leurs truc et astuces, leur façon de travailler...

Mais je peux comprendre que certaines personnes n'aiment pas discuter/échanger après c'est vrai qu'il y a "discuter" et "discuter" (discutailler)...
05/11/2024, 18h57
wiztricks

Citation:

Envoyé par Beginner.

Mais si on raisonne comme ça, pourquoi garder ce forum ? On peut renvoyer tout le monde aux moteurs de recherche et aux services d'IA (pour chercher sous forme de discussion)...

Parce qu'on n'est pas toujours capable de (re)formuler son problème pour avoir des réponses pertinentes. Un forum sert à "discuter" pour avoir un autre éclairage (et reformuler).

Dans mon expérience des moteurs de recherche, on y trouve a peu près tout pourvu qu'on sorte les bons mots clefs. Réciproquement, si on ne trouve pas quelque chose de satisfaisant, c'est peut être qu'on pose mal le problème et s'il mérite notre attention, ca demande à être revisité (pour mieux comprendre ce qu'on veut). Après on va solliciter la planète en fonction de l'urgence... à la retraite, je ne suis pas "pressé" et si un sujet m'intéresse je peux y passer quelques heures.

Le forum est utile pour les débutants. Les moins débutants apprennent à utiliser d'autres ressources... la documentation, les codes qu'ils ont écrit, bien avant chercher sur le Web ou chatter avec une IA (parce que ca demande une certaine expertise tant pour formuler les questions que pour jauger les réponses).

Citation:

Envoyé par Beginner.

Mais n’empêche que je pourrais quand même avoir envie de discuter avec des humains pour connaitre leurs solutions, leurs idées, leurs truc et astuces, leur façon de travailler...

Ben ouais mais on a crée Internet et le Web pour cela. C'est une mine de connaissances que les humains ont mis à disposition pour diffuser leurs solutions, trucs et astuces... Ceci dit, tant que vous ne mettrez pas la main a la patte, vous ne saurez pas si ces solutions/trucs/.... répondent à vos besoins a vous.

note: relisez les règles à suivre avant de poster! Vous êtes dans un forum de professionnels supposé avoir cherché un peu avant de demander de l'aide. Je n'ai pas écrit ces règles mais tout membre du club est supposé les respecter...

- W