排列操作的 Python 性能

Question

我有一个包含 2000 个单词的数据框。我正在尝试一次创建 4 个所有单词的排列。

perms = it.permutations(words.col, 4)
done=object()
nextperm=next(perms,done)
while(nextperm is not done):
#perform operations...
permutedString=' '.join(nextperm )
if(permutedString.count('a')==2 and permutedString.count('b')==3 and 
permutedString.count('c')==1):
//calculate  Md5 hash with 
hash=hashlib.md5(permutedString.encode('utf-8')).hexdigest()
nextperm=next(perms,done)

上面的脚本对我来说太长了。它已经运行了几个小时。有没有办法提高这方面的性能。

非常感谢对此的任何帮助。

Answer 1

正如扎曼所指出的，循环内部发生的事情是想出解决问题的更好方法的关键。 基本思想是，您希望最小化需要执行的成对(或 N 向(操作的数量。

在您的情况下，您显然正在尝试选择具有正确数量特定字母的短语，试图破解某种"正确的马电池订书钉"密码方案，并限制字母计数。 在这种情况下，由于您只允许使用1个字母"c"，因此处理任何具有两个"c"的排列都没有意义。 等。

我们也可以做得更好，而不仅仅是排除无用的单词：我们实际上不需要比较所有单词以查看它们是否匹配，我们可以简单地比较字数集。 也就是说，我们可以按字母的 a、b 和 c 字母计数对所有单词进行分组，我们可以在线性时间内做到这一点，然后我们可以迭代其中四个计数集，看看它们的总和是否为正确的字母数。 现在我们只需要对从一组 ~10 而不是 ~2000 中提取的元素执行计数逻辑。 (实际上，我们可以做得更好，因为我们可以直接递归或使用分区技术直接构建适当的可能计数集，但让我们从简单开始。

现在，您已经说过"只有一两个字符串符合此条件"，我将相信您的话，并限制我将要做的优化量来处理这样的情况。

如果只有少数几个满足约束，则一定只有几个字母计数组也满足约束，并且该组中的单词不多。 所以这样的事情应该有效：

from collections import Counter
from itertools import permutations, product, combinations_with_replacement
import hashlib
# make a fake set of words
with open('/usr/share/dict/words') as fp:
words = [word.lower() for word in fp.read().split()]
words = set(words[::len(words)//2000][:2000])
# set the target to something which has <2000 matching 4-words
target_counts = Counter({"a": 5, "b": 4, "d": 8})
# collect the words by counts
by_count = {}
for word in words:
lcount = {letter: word.count(letter) for letter in target_counts}
by_count.setdefault(tuple(sorted(lcount.items())), []).append(word)
collected_hashes = {}
# loop over every possible collection of word count groups
for i, groups in enumerate(combinations_with_replacement(by_count, 4)):
if i % 10000 == 0:
print(i, groups)
# check to see whether the letter set sums appropriately
total_count = sum((Counter(dict(group)) for group in groups), Counter())
if total_count != target_counts:
continue
# the sums are right! loop over every word draw; for simplicity
# we won't worry about duplicate word draws, we'll just skip
# them if we see them
for choices in product(*(by_count[group] for group in groups)):
if len(set(choices)) != len(choices):
# skip duplicate words
continue
for perm in permutations(choices):
joined = ' '.join(perm)
hashed = hashlib.md5(joined.encode("utf-8")).hexdigest()
collected_hashes.setdefault(hashed, set()).add(joined)

生成哈希字典大约需要 10 秒，例如

In [25]: len(collected_hashes)
Out[25]: 960
In [26]: collected_hashes
Out[26]: 
{'67a0da67d938a6090beedcb849f66596': {'barbed badlands saddlebag skidded'},
'8da55149bf66f89f27b658a7ef7d7126': {'barbed badlands skidded saddlebag'},
'69dd0f1c7af2e9973fedcc585af15df4': {'barbed saddlebag badlands skidded'},
'106a366ef772a5f68ebb4800b2281a09': {'barbed saddlebag skidded badlands'},
...

每个密码确实具有正确数量的目标字母计数：

In [30]: c = Counter('barbed badlands saddlebag skidded')
In [31]: c['a'], c['b'], c['d']
Out[31]: (5, 4, 8)

Answer 2

除了P(2000, 4)是一个巨大的数字之外，你不需要用哨兵手动检查你的循环，你可以直接迭代perms对象。这与你提供的代码所期望的优化差不多，循环内发生的任何事情都将是决定因素。

perms = it.permutations(words.col, 4)
for perm in perms:
# do stuff with perm