J'ai besoin d'un moyen plus rapide de générer toutes les permutations d'une liste, puis vérifiez si chacun est dans un dictionnaire.
for x in range (max_combo_len, 0, -1):
possible_combos = []
permutations = list(itertools.permutations(bag,x))
for item in permutations:
possible_combos.append(" ".join(item))
#then check to see if each possible combo is in a specific Dict
5 Réponses :
Une optimisation très basique: peut devenir ...
I.e., vous n'avez pas besoin de le convertir en une liste en premier.
Je ne peux pas très bien le tester sans de meilleurs cas d'entrée, mais voici quelques améliorations:
for x in xrange(max_combo_len, 0, -1):
possible_combos = (" ".join(item) for item in itertools.permutations(bag,x))
#then check to see if each possible combo is in a specific Dict
combos = (c for c in possible_combos if c in specific_dict)
quelque chose comme ça?
OP semblait vouloir vérifier si la combinaison de mots est possible de produire du dictionnaire des mots, alors j'ai pensé à "penser à la boîte", inverse de ce qu'il semble essayer. Cela sort de la complexité exponentielle (factorielle?) Du programme.
for x in xrange(max_combo_len, 0, -1):
for item in itertools.permutations(bag,x):
combo = " ".join(item)
if combo in specificDict:
yield combo
This way you don't have any large (and getting larger) lists, you just yield the passing comobs out of the function.
Vous pouvez vous débarrasser des nombreuses opérations de jointure actives (jetées), si vous préparez votre dict spécial: il suffit de scinder les valeurs ou les touches, en fonction de ce que vous comparez. Cela suppose bien sûr que la dicte est plus petite que le nombre de toutes les combos.
Si vous avez besoin de la jointure, vous devez modifier légèrement cela. Je pense sans que vous soyez plus descriptif, le problème n'est pas mieux optimisé que cela. Et ça ne va pas être beaucoup plus rapide juste en utilisant une autre langue.
Quelle est la taille d'un nombre pour
max_combo_len et la longueur du sac ? En outre, si vous nous avez donné une idée de ce que c'était dans un contexte plus important, nous pourrions peut-être fournir plus d'aide.Pour une chose, il n'est pas nécessaire de tourner
permutations dans une liste si vous allez itérer sur celui-ci avec une boucle de toute façon.Merci. Max_combo_len n'ira pas au-dessus de 4 ou 5. La longueur du sac est la longueur d'une phrase standard. Le sac est essentiellement une liste de mots ["tels", "comme", "ceci", "one"], où je veux créer toutes les combinaisons possibles de cette liste.
Qu'entendez-vous par dict spécifique? Un dict pour chaque taille ou un total de dict?
Les suggestions jusqu'à présent peuvent aider, mais elles ne vont pas changer la complexité; Si c'est beaucoup trop lent, ce n'est probablement pas ce que vous cherchez. Veuillez inclure le code pour générer une quantité réaliste de données de test réelles, une fonction bancaire autonome à l'aide de celle-ci et des repères sur votre système pour montrer quelles performances vous voyez et combien vous souhaitez l'améliorer.
Glenn fait de bons points. Si vous avez spécifié ce que vous essayez de faire (probablement dans une nouvelle question), il pourrait y avoir une Way meilleur algorithme, puis brute forçant les permutations. Cela dit, je m'attends à ce que mon code affiché ait surperformer le code posté de l'OP par un facteur d'environ quatre.