Python - ускоряет генерацию перестановок списка (и процесс проверки перестановок в Dict)

Question

Мне нужен более быстрый способ создания всех перестановок списка, а затем проверьте, есть ли каждая из них в словаре.

        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

Если это поможет, все списки будут списками строк. [такие как ',' это ',' один ']

Мое решение работает, но оно очень медленное. Может быть, мне нужно прекратить использовать Python, но я подумал, что сначала я проведу его у экспертов!

Лучший, Gary

Answer 1

Очень базовая оптимизация:

permutations = list(itertools.permutations(bag,x))
for item in permutations:

может стать ...

for item in itertools.permutations(bag,x):

Answer 2

вы можете избавиться от многих бесполезных (выброшенных) операций объединения, если подготовите свой особый запрос: просто разделите значения или ключи, в зависимости от того, что вы сравниваете.Это предполагает, конечно, что dict меньше, чем количество всех комбо.

Если вам нужно объединение, вы должны немного изменить это.Я думаю без того, чтобы вы были более описательными, проблема не лучше, чем эта.И это не будет намного быстрее, просто используя другой язык.

(filtered_combo for filtered_combo in      
        itertools.chain.from_iterable(
                combo for combo in (itertools.permutations(bag, x) 
                        for x in xrange(max_combo_len, 0, -1)))
        if filtered_combo in special_dict)

Answer 3

    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

Таким образом, у вас нет больших (и увеличивающихся) списков, вы просто выводите переданные комбы из функции.

Answer 4

Я не могу проверить это очень хорошо без лучшего ввода, но вот несколько улучшений:

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)

Во-первых, предполагая, что вы используете Python 2.x, xrange поможет, не создавая явный список, а просто выдавая каждый x, как вам нужно.

Что еще более важно, вы можете бросить основное усилие в выражения генератора и получить его значения по требованию.

Answer 5

Как то так?

sentences = ['such as', 'this', 'ten eggs', 'one book', 'six eggs']
bag_of_words = set(['such', 'one','ten','book','eggs'])

possible = [sentence
            for sentence in sentences
            if all(word in bag_of_words for word in sentence.split())
            ]

print 'Possible to produce from bag words are:\n\t%s' % '\n\t'.join(possible)