J'ai un petit projet où je dois déchiffrer (trouver tous les mots possibles pouvant être écrits en utilisant uniquement des lettres dans un ensemble de lettres) 100 000 lettres, chaque lettres contient 12 lettres. Je voudrais trouver le meilleur moyen en termes de vitesse pour gérer cette tâche dans Python. Jusqu'à présent, cela me fallut déjà 10 heures, mais la commande n'a pas encore fini de courir.
J'ai examiné le problème exact dans d'autres messages et j'ai vu la méthode de permutation d'itertools. Je pense que c'est beaucoup plus lent que cette méthode que je emprunte à un site Web (code ci-dessous). En fait, une permutation d'une lettre d'une lettre de 12 lettres prend déjà une durée importante pour mon ordinateur portable. Ou peut-être que j'ai mal compris quelque chose. P>
Le dictionnaire que je travaille avec est l'espagnol. Pour le but de présentation, je génère des lettres comme 1 chaîne, au lieu d'une liste. P> définir la fonction de déchiffrement p> vocab : est un dictionnaire qui contient environ 170 000 mots. Je mets ce mot dans une liste Python. P> lettres: est une liste de lettres. Par exemple: ['X', 'D', 'A', 'A', 'A', 'A', 'O', 'O', 'U', 'E', 'E', 'G', 'G', 'M', 'N', 'F' ']. P> Le code suivant fonctionne pendant 10 heures mais n'a pas encore été terminé. Il est toujours opérationnel que je tape ce post. P> exemple de vocabulaire Dictionnaire:
Exemple de lettres: P> es_vocab = ['Ame', 'Amo', 'Año', 'Apio', 'EMA', 'EMA', 'EMPAÑ O', 'MI', 'MI', 'MIOPE', 'OPIMA', "OPIMA", "Paño '," PE "," Peña "," Pi "," Pia "," Pie "," Piña "," Pio "," Poema "," A ", 'E', 'XL', 'KL', 'ML'] CODE> #Les dernières valeurs ne sont pas des mots réels p> letterset_list = ['oiwóeaópñmóó']
3 Réponses :
def charCount(s):
s = s.lower()
answer = [0]*26
for char in s: answer[ord(char)-97] += 1
return tuple(answer)
def preprocess(vocab):
answer = collections.defaultdict(list)
for word in vocab: answer[charCount(word)].append(word)
return answer
def possible_words(vocab, scrambled):
'''note that the `vocab` parameter is actually intended to be preceprocess(list_of_dictionary_words)'''
return vocab[charCount(scrambled)]
def get_all_possible_words(vocab, lettersets):
vocab = preprocess(vocab)
answer = {}
for letterset in lettersets:
answer[tuple(letterset)] = possible_words(vocab, letterset)
return answer
N'a pas travaillé pour moi depuis que peu de lettres en espagnol seraient en dehors de la plage de points de code Unicode que vous avez définie dans la première fonction. Par exemple. Charcount ('Abajeños')
@ GAM780: Vous pouvez contourner cela en remplaçant simplement ORD (char) -97 avec la valeur UNICODE et augmente de manière appropriée la taille du vecteur
Je voudrais probablement approcher cela quelque chose comme ceci: et assurez-vous que lettres est un définit
real 10m42,351s user 10m38,069s sys 0m3,854s
Je suis vraiment impatient de votre réponse et je mesure réellement le temps qu'il a fallu. (Juste au cas où) je veux souligner que l'ES_VOCAB compte environ 170 000 mots.
@ Gam780 qui ne devrait pas être un problème, car nous avons index qui est dict, de sorte que la valeur de DICT est O (1).
Cela fonctionne vite! En outre, c'est en fait une façon correcte de le faire. Après avoir comparer votre méthode avec la méthode que j'ai postée. J'ai découvert que ma solution est vraiment fausse! Essayant toujours de comprendre pourquoi ma solution a trouvé moins de mots que la tienne. Merci un tas!
FYI Vous pouvez simplement utiliser un
collections.Counter au lieu de votrecharcant (il fait exactement la même chose), vous ne devez pas nommer une variabledict comme cette ombre du type intégré.Merci beaucoup, je ne savais pas sur Collections.Conter. En effet, c'est une mauvaise nommée pour une variable de «dict».