我有大约95000000个排列要检查。我有8个不同长度的列表，每个字符串都标识excel表中定义的属性(a-k(。例如
bcdgj
具有属性b、c、d、g和j
我只需要找到一个包含至少3个属性的排列，然后将这些属性与电子表格中的数据匹配
我已经制作了这个脚本(我第一次尝试使用python(
import numpy
import itertools
for x in itertools.product(['abfhj','bcdgj','fghij','abcj','bdgk','abgi','cdei','cdgi','dgik','aghi','abgh','bfhk'],['cdei','bcdgj','abcgi','abcj','abfj','bdfj','cdgi','bhjk','bdgk','dgik'],['afhk','cdgik','cegik','bdgi','cgij','cdei','bcgi','abgh'],['fhjk','bdgij','cgij','abk','ajk','bdk','cik','cdk','cei','fgj'],['abe','abcf','afh','cdi','afj','cdg','abi','cei','cgk','ceg','cgi'],['cdgi','bcgj','bcgi','bcdg','abfh','bdhi','bdgi','bdk','fhk','bei','beg','fgi','abf','abc','egi'],['bcdgik','cegik','chik','afhj','abcj','abfj'],['ceg','bcfg','cgi','bdg','afj','cgj','fhk','cfk','dgk','bcj']):
gear = ''.join(x)
count_a = gear.count('a')
count_b = gear.count('b')
count_c = gear.count('c')
count_d = gear.count('d')
count_e = gear.count('e')
count_f = gear.count('f')
count_g = gear.count('g')
count_h = gear.count('h')
count_i = gear.count('i')
count_j = gear.count('j')
count_k = gear.count('k')
score_a = numpy.clip(count_a, 0, 3)
score_b = numpy.clip(count_b, 0, 3)
score_c = numpy.clip(count_c, 0, 3)
score_d = numpy.clip(count_d, 0, 3)
score_e = numpy.clip(count_e, 0, 3)
score_f = numpy.clip(count_f, 0, 3)
score_g = numpy.clip(count_g, 0, 3)
score_h = numpy.clip(count_h, 0, 3)
score_i = numpy.clip(count_i, 0, 3)
score_j = numpy.clip(count_j, 0, 3)
score_k = numpy.clip(count_k, 0, 3)
rating = score_a + score_b + score_c + score_d + score_e + score_f + score_g + score_h + score_i + score_j + score_k
if rating == 33:
print(x)
print(rating)
我已经调整了评级要求，以测试它是否有效，但需要一段时间才能处理95000000个排列。有人对让它跑得更快有什么建议吗？我想我已经尽可能地减少了每个列表中的值的数量，数据来自excel表，每个列表有几百个条目，我已经设法将其减少到每个列表6-12个。
Python不是为编写计算密集型纯Python代码而设计的。它是用来作为粘合代码的。密集部分应该向量化，也就是说，在C等编译的本地语言中进行优化。CPython的默认实现是解释器，尤其如此。对函数的任何调用都非常昂贵(每个gear.count100 ns(。
尽管如此，经济放缓的许多原因是可以避免的。首先，字符串是基于unicode的字符串，unicode字符串的计算速度很慢(因为非平凡的编码和可变的大小(。您的代码在循环的每次迭代中都会创建一个新的字符串对象创建新对象的成本很高。问题是Python字符串是不可变的，所以除了根本不使用字符串之外，没有办法不创建新的字符串。此外，Numpy操作也是如此：Numpy不是为计算非常小的数组而设计的，因此它引入了大量开销。字符串是用''.join(...)从头开始重建的，但只需要修改最后一部分。计算字符也是如此：您只能重新计算从一次迭代到另一次迭代变化的部分。此外，不需要numpy.clip，因为项目的数量不能为负数：您可以用对score_xxx = min(count_xxx, 3)的调用来代替它。请注意，此操作可以并行执行(在纯Python中使用多处理(。也就是说，如果注意前面提到的几点，在C中重写这个应该会快很多数量级。
如果您绑定到Python，则可以使用像Numba这样的即时编译器来实现这一点。然而，Numba不支持井字符串。这不是什么大问题，因为我们无论如何都不应该为了性能而使用它。字符串可以转换为基于ASCII的整数数组，itertool生成器可以替换为基本循环。
在Numba中有效地做到这一点的一种方法是1。将笛卡尔乘积拆分为两部分，并计算两个相当大的数组和计数(使用基本循环(，2。然后计算两组的笛卡尔乘积(使用2个嵌套循环(。
from itertools import groupby, product
data = (
['abfhj','bcdgj','fghij','abcj','bdgk','abgi','cdei','cdgi','dgik','aghi','abgh','bfhk'],
['cdei','bcdgj','abcgi','abcj','abfj','bdfj','cdgi','bhjk','bdgk','dgik'],
['afhk','cdgik','cegik','bdgi','cgij','cdei','bcgi','abgh'],
['fhjk','bdgij','cgij','abk','ajk','bdk','cik','cdk','cei','fgj'],
['abe','abcf','afh','cdi','afj','cdg','abi','cei','cgk','ceg','cgi'],
['cdgi','bcgj','bcgi','bcdg','abfh','bdhi','bdgi','bdk','fhk','bei','beg','fgi','abf','abc ','egi'],
['bcdgik','cegik','chik','afhj','abcj','abfj'],
['ceg','bcfg','cgi','bdg','afj','cgj','fhk','cfk','dgk','bcj'],
)
REQ_PROPS = set("abcdefghijk")
for x in product(*data):
permu = ''.join(x)
# if the permutation does not contain all letters from a-k, skip it.
if REQ_PROPS.difference(permu):
continue
prop_map = dict.fromkeys(permu)
for prop, group in groupby(sorted(permu)):
group_rating = len(tuple(group))
# dont bother searching more props of this permutation if the current
# property has a rating less than 3
if group_rating < 3:
break
prop_map[prop] = group_rating
# check if this permutation satisfies the requirement and exit if it does.
if all(v is not None for v in prop_map.values()):
print(x)
print(prop_map) # total rating of each property
break
不确定这是否是你想要的，但最明显的优化是"；"短路"；只要一个排列不具有所有所需的属性或者当一个排列的属性不具有至少3个实例时就停止搜索。这是通过首先对排列进行排序，然后按属性对其进行分组来实现的。分组后，检查每个属性的频率是否不小于3。如果对所有属性的检查都没有失败，那么你就有了答案，否则就进入下一个排列。
我使用示例数据运行了该程序，但似乎没有包含所有a-k属性的解决方案。也许你需要一个更大的数据集。