IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Python Discussion :

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


Sujet :

Python

  1. #1
    Invité
    Invité(e)
    Par défaut 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 )

    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.

  2. #2
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 840
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 840
    Billets dans le blog
    1
    Par défaut
    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()
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  3. #3
    Invité
    Invité(e)
    Par défaut
    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...

  4. #4
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 840
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 840
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par LeNarvalo Voir le message
    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).

    Citation Envoyé par LeNarvalo Voir le message
    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
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  5. #5
    Invité
    Invité(e)
    Par défaut
    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.

  6. #6
    Expert éminent
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 762
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 762
    Par défaut
    Citation Envoyé par LeNarvalo Voir le message
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  7. #7
    Membre prolifique
    Avatar de Sve@r
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Février 2006
    Messages
    12 840
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Oise (Picardie)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : Aéronautique - Marine - Espace - Armement

    Informations forums :
    Inscription : Février 2006
    Messages : 12 840
    Billets dans le blog
    1
    Par défaut
    Citation Envoyé par LeNarvalo Voir le message
    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.

    Citation Envoyé par LeNarvalo Voir le message
    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

    Citation Envoyé par LeNarvalo Voir le message
    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.

    Citation Envoyé par LeNarvalo Voir le message
    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)...
    Mon Tutoriel sur la programmation «Python»
    Mon Tutoriel sur la programmation «Shell»
    Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
    Et on poste ses codes entre balises [code] et [/code]

  8. #8
    Invité
    Invité(e)
    Par défaut
    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 !
    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 🎖️

  9. #9
    Expert éminent
    Homme Profil pro
    Architecte technique retraité
    Inscrit en
    Juin 2008
    Messages
    21 762
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Manche (Basse Normandie)

    Informations professionnelles :
    Activité : Architecte technique retraité
    Secteur : Industrie

    Informations forums :
    Inscription : Juin 2008
    Messages : 21 762
    Par défaut
    Citation Envoyé par Sve@r Voir le message
    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 Voir le message
    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
    Architectures post-modernes.
    Python sur DVP c'est aussi des FAQs, des cours et tutoriels

  10. #10
    Expert confirmé Avatar de papajoker
    Homme Profil pro
    Développeur Web
    Inscrit en
    Septembre 2013
    Messages
    2 324
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nièvre (Bourgogne)

    Informations professionnelles :
    Activité : Développeur Web
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Septembre 2013
    Messages : 2 324
    Par défaut
    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 )

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

  11. #11
    Invité
    Invité(e)
    Par défaut
    C'est beau mais c'est pas simple !

    Ca fait très pro ! 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" !

Discussions similaires

  1. Méthode la plus rapide pour une sauvegarde , Restauration ?
    Par SQLpro dans le forum Installation
    Réponses: 8
    Dernier message: 18/01/2017, 23h21
  2. Réponses: 9
    Dernier message: 08/02/2012, 18h40
  3. Réponses: 1
    Dernier message: 03/01/2010, 14h36
  4. [XL-2003] Méthode la plus rapide pour vérifier des conditions sur trois colonnes
    Par neiluj26 dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 24/08/2009, 16h38
  5. Réponses: 16
    Dernier message: 19/05/2005, 16h20

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo