La comparaison des entiers en Python ralentit tout à un rythme très lent

Question

Le code suivant me cause d'énormes maux de tête :

def extract_by_letters(letters, dictionary):

    for word in dictionary:
       for letter in letters:
           if word.count(letter) != letters.count(letter):
               if word in dictionary: #Je ne peux pas laisser cette ligne dehors
                   dictionary.remove(word)

    return dictionary

Tout d'abord : la ligne 'if word in dictionary'. Pourquoi je ne peux pas la laisser dehors ? Je reçois une erreur disant ValueError: list.remove(x): x not in list

Mais il est, évidemment.

Deuxièmement : Dictionnaire est un fichier d'environ 50 000 mots séparés par des sauts de ligne. Le code ci-dessus prend environ 2 minutes pour s'exécuter... Trop longtemps. J'ai joué avec le code pendant un moment, et j'ai trouvé que la ligne :

if word.count(letter) != letters.count(letter):

semble causer tous mes problèmes. Si je retire cette ligne (ce qui perturbe totalement la sortie), la fonction met environ 2 secondes pour parcourir le dictionnaire.

J'ai pensé que c'était les fonctions de comptage, mais ce n'est pas le cas.

si je change l'instruction if à quelque chose comme :

print word.count(letter) 
print letters.count(letter)

la fonction met environ 3 secondes pour s'exécuter.

Je suis convaincu que c'est la comparaison. D'autres suggestions ? Y a-t-il une meilleure façon de faire cela ?

Merci d'avance !

Answer 1

La raison pour laquelle vous obtenez l'exception est que si le nombre de lettres correspond pour plus d'une lettre, vous essayez de supprimer le mot plus d'une fois

La raison pour laquelle c'est si lent est que vous avez des boucles à l'intérieur des boucles à l'intérieur des boucles.

Si vous écriviez une phrase ou deux sur ce que la fonction est censée faire, il serait beaucoup plus facile de refactoriser. En attendant, cela vous empêcherait de vérifier si un mot doit être supprimé une fois que vous l'avez déjà supprimé.

def extract_by_letters(letters, dictionnaire):
    for mot in dictionnaire[:]:  # mauvaise idée de changer cela pendant que vous itérez dessus
        for lettre in letters:
            if mot.count(lettre) != letters.count(lettre):
                dictionnaire.remove(mot)
                break
    return dictionnaire

Si le dictionnaire est un set vous devriez obtenir une accélération. Si le dictionnaire est une liste cela devrait donner une énorme accélération

Answer 2

Essayez de construire la sortie au lieu de supprimer à partir de celle-ci :

def extract_by_letters(letters, dictionary):
    d = []
    for word in dictionary:
       for letter in letters:
           if word.count(letter)>0:
               d.append(word)
               break
    return d

Ou, vous pourriez utiliser des expressions régulières :

import re
def extract_by_letters(letters, dictionary):
    regex = re.compile('['+letters+']')
    d=[]
    for word in dictionary:
       if regex.search(word):
           d.append(word)
    return d

Ou, peut-être la manière la plus simple :

import re
def extract_by_letters(letters, dictionary):
    regex = re.compile('['+letters+']')
    return [word for word in dictionary if regex.search(word)]

Cette dernière ne prend pas de temps notable pour analyser /usr/share/dict/words sur mon Mac, qui est une liste de 234936 mots.

Answer 3

Voici une fonction qui devrait offrir une nette amélioration de vitesse :

def extract_by_letters(letters, dictionnaire):
    letdict = zip(set(letters), [letters.count(let) for let in set(letters)])
    outarr = []
    for mot in dictionnaire:
        bonmot = True
        for lettre in letdict:
            if mot.count(lettre) != letdict[lettre]:
                bonmot = False
                break
        if bonmot:
            outarr.append(mot)
    return outarr

Voici les optimisations que j'ai faites :

1. J'ai créé un dictionnaire des lettres avec leurs fréquences correspondantes. De cette façon, vous n'utilisez pas la fonction letters.count encore et encore alors que vous n'avez besoin de faire ce processus qu'une seule fois et de stocker les résultats.

2. Au lieu de supprimer les mots du dictionnaire, je les ajoute à un tableau qui est renvoyé par la fonction. Si vous avez un énorme dictionnaire, il y a des chances que seuls quelques mots correspondent. De plus, si la variable dictionnaire est un tableau (ce que je soupçonne), alors chaque fois que vous appeliez remove, il devait d'abord rechercher le mot dans le dictionnaire (linéairement en commençant par le début) puis le supprimer. Il est plus rapide de supprimer en utilisant l'index du mot à supprimer.

3. Sortir de la boucle vérifiant les comptages de lettres dès qu'une incohérence est trouvée. Cela nous évite de faire des vérifications inutiles lorsque nous avons déjà notre réponse.

Je n'étais pas sûr si vous aviez des lettres répétées dans la variable letters ou non, donc j'ai veillé à ce qu'elle puisse gérer cela en utilisant letdict. Si vous aviez des lettres répétées dans votre variable letters auparavant, alors vous vérifiiez les comptages de ces lettres dans le mot à plusieurs reprises.

Answer 4

import pprint
from collections import defaultdict

# Ceci est une meilleure approximation de ce que Bryan essaie de faire.
# Cependant, les résultats sont sans signification car la liste est modifiée
# pendant l'itération dessus. Donc je n'ai pas montré la sortie.

def extract_by_letters_0(letters, input_list):
    dictionary = input_list.copy()
    for word in dictionary:
       for letter in letters:
           if word.count(letter) != letters.count(letter):
               if word in dictionary: #Je ne peux pas laisser cette ligne dehors
                   dictionary.remove(word)
    return dictionary

# Cela évite la mutation.
# Les résultats sont des anagrammes PLUS des lettres qui n'apparaissent pas
# dans la requête. Par exemple, "same" produit "samehood" mais pas "sameness"
# ("sameness" a 3*"s" et 2*"e" au lieu de 1 de chaque)

def extract_by_letters_1(letters, input_list):
    dictionary = set(input_list)
    ripouts = set()
    for word in dictionary:
       for letter in letters:
           if word.count(letter) != letters.count(letter):
               ripouts.add(word)
    return dictionary - ripouts

def anagram_key(strg):
    return ''.join(sorted(list(strg)))

def check_anagrams(str1, str2):
    return sorted(list(str1)) == sorted(list(str2))

# Conseil: essayez des algorithmes comme celui-ci sur un PETIT ensemble de données d'abord.
# Faites-le fonctionner correctement. Utilisez différentes cas de test. Ayez un code de test
# aussi primitif soit-il pour vérifier vos résultats.
# Ensuite, si cela fonctionne lentement, les aides
# ne doivent pas deviner ce que vous faites.

raw_text = """
twas brillig and the slithy toves
did gyre and gimble in the wabe
same mesa seam sameness samehood
"""

lexicon = sorted(set(raw_text.split()))
print "\nlexicon:", lexicon
#
# En supposant que nous voulons des anagrammes:
#
# Construire un dictionnaire d'anagrammes
#
anagram_dict = defaultdict(set)
for word in lexicon:
    anagram_dict[anagram_key(word)].add(word)

print "\nanagram_dict (len == %d):" % len(anagram_dict)
pprint.pprint(anagram_dict)

# maintenant purger les entrées triviales

temp = {}
for k, v in anagram_dict.iteritems():
    if len(v) != 1:
        temp[k] = v
anagram_dict = temp
print "\nanagram_dict (len == %d):" % len(anagram_dict)
pprint.pprint(anagram_dict)

# Cas de test

tests = "sam same mesa sameness samehood xsame samex".split()
default_set = frozenset()
for test in tests:
    print
    results = extract_by_letters_1(test, lexicon)
    print test, [(result, check_anagrams(test, result)) for result in results]
    # Dans l'instruction suivante, vous pouvez utiliser set([test]) comme valeur par défaut
    # si cela produit un résultat plus utile ou orthogonal.
    results = anagram_dict.get(anagram_key(test), default_set)
    print test, [(result, check_anagrams(test, result)) for result in results]

Output:

lexicon: ['and', 'brillig', 'did', 'gimble', 'gyre', 'in', 'mesa', 'same', 'samehood', 'sameness', 'seam', 'slithy', 'the', 'toves', 'twas', 'wabe']

anagram_dict (len == 14):
defaultdict(, {'abew': set(['wabe']), 'eht': set(['the']), 'egry': set(['gyre']), 'begilm': set(['gimble']), 'hilsty': set(['slithy']), 'aems': set(['mesa', 'seam', 'same']), 'bgiillr': set(['brillig']), 'ddi': set(['did']), 'eostv': set(['toves']), 'adehmoos': set(['samehood']), 'in': set(['in']), 'adn': set(['and']), 'aeemnsss': set(['sameness']), 'astw': set(['twas'])})

anagram_dict (len == 1):
{'aems': set(['mesa', 'same', 'seam'])}

sam [('mesa', False), ('samehood', False), ('seam', False), ('same', False)]
sam []

same [('mesa', True), ('samehood', False), ('seam', True), ('same', True)]
same [('mesa', True), ('seam', True), ('same', True)]

mesa [('mesa', True), ('samehood', False), ('seam', True), ('same', True)]
mesa [('mesa', True), ('seam', True), ('same', True)]

sameness [('sameness', True)]
sameness []

samehood [('samehood', True)]
samehood []

xsame []
xsame []

samex []
samex []

Answer 5

Vous essayez de trouver tous les anagrammes de 'lettres' ?

def anagrammes(lettres, mots):
    lettres = sorted(lettres)
    resultat = []
    for mot in mots:
        if sorted(mot.strip()) == lettres:
            resultat.append(mot)
    return resultat