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

[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