Méthode la plus rapide pour passer un string déjà connu

Version imprimable

23/07/2022, 21h44
Invité

Méthode la plus rapide pour passer un string déjà connu
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 :aie:)

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

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 ! :D

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.

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:

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

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

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:

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:

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

Citation:

Envoyé par LeNarvalo

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:

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:

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:

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

Citation:

Envoyé par LeNarvalo

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

24/07/2022, 14h33
Invité
Merci !

Belle performance de PC ! :ccool: (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.

Citation:

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

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.
24/07/2022, 17h41
wiztricks

Citation:

Envoyé par LeNarvalo

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
24/07/2022, 20h34
Sve@r
Citation:

Envoyé par LeNarvalo

Belle performance de PC ! :ccool: (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.

Citation:

Envoyé par LeNarvalo

Oui évidemment :oops:. 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 8-)
Citation:
Envoyé par LeNarvalo

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

Code:

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.

Citation:

Envoyé par LeNarvalo

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)...
24/07/2022, 22h06
Invité

Citation:

Envoyé par Sve@r

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

Mais oui cette erreur que nous avons eu un peu plus tôt dans une autre discussion mais d'une autre manière ! :marteau:
Je te décerne à nouveau une médaille pour ta participation très appréciable sur ce forum🏅 (à bon entendeur !)

Merci aussi à Wiz, je te décerne la médaille de la concision 🎖️ :mouarf:
25/07/2022, 11h17
wiztricks

Citation:

Envoyé par Sve@r

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.

Le fonctionnement d'une table de hash n'est pas une opinion, mais un savoir "scientifique" que l'on a pris le temps d'apprendre (ou pas).

Citation:

Envoyé par LeNarvalo

Merci aussi à Wiz, je te décerne la médaille de la concision 🎖️

Je profite de tout ce qui a déjà été écrit sur le sujet... et je vous invite à faire de même.

- W

Dans autre sujet:

Citation:

Envoyé par LeNarvalo

Toujours pas trouvé d'intérêt à coder en POO

une réponse poo (oui, on perd quelques nanosecondes :mrgreen:)

Se créer un objet pour ce besoin.
- L'algo est masqué par l'objet (ici, utilise set)
- puisque l'on surcharge les opérateurs (à notre façon), l'intérieur de l'objet est masqué et modifiable si on trouve une meilleure solution algorithmique un jour
- Possible d'avoir un objet plus générique, réutilisable (presque partout ?)

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
import contextlib
 
class ContextUniqueStr:
 
    def __init__(self, items) -> None:
        self._data = set(items)
 
    def __enter__(self):
        return self
 
    def __iadd__(self, item: str):
        self._data.add(item)
        return self
 
    def __add__(self, item: str) -> bool:
        return not self.__contains__(item)
 
    def __contains__(self, item: str) -> bool:
        return item in self._data
 
    def __ge__(self, item: str):
        for chaine in self._data:
            if chaine.startswith(item):
                yield chaine
        return None
 
    def __exit__(self, *exc):
        self._data.clear()  # on ne désire pas le dico hors contexte...
        return True    # pas d'Exceptions dans ce contexte ...
 
    @property
    def uniques(self) -> set:
        return self._data
 
    def __str__(self):
        return str(self._data)

Utilisation :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
inputs = ["maman", "papa", "b", "maman", "pierre", "mama"]  # entrées utilisateur
with ContextUniqueStr(["maman", "papa", "maman", "mamamia"]) as ls:
 
    for item in inputs:
        if item in ls:
        #if not ls + item:  # ou syntaxe alternative - pouvons PAS ajouter
            print("   duplicate:", item)
        else:
            if holder := list(ls >= item):   # lent ! plus pour un usage "autocomplétion"
                print("?", item, "mot incomplet ? Existe dans dico:", holder)
                # continue ? si mot doit être dans le dico - par exemple
            print("add au dico:", item)
            ls += item
    print()
    print("mon dico de mots:", ls.uniques)
    print("dico:", ls)
print("dico hors contexte:", ls.uniques)  # vide hors contexte

27/07/2022, 17h41
Invité

C'est beau mais c'est pas simple !

Ca fait très pro ! :bravo: Je n'utiliserais très probablement jamais ce genre de choses, pour le moment je ne vois toujours pas d'intérêt à mon usage de python... Davantage si tu développes un module "publique" !