我有一些简单的代码,它执行以下操作。
它遍历所有可能的长度为n的列表 F
,其中每个条目为+1或-1。 对于每个列表,它遍历所有可能的长度为2n
的列表 S
,其中每个条目为+1或-1,其中的前半部分是后半部分的复制。 该代码计算F
与长度为n
的S
的每个子列表的内积。 对于每个F和S,它计算了内积为零直到第一个非零内积的数量。
这是代码:
#!/usr/bin/python
from __future__ import division
import itertools
import operator
import math
n=14
m=n+1
def innerproduct(A, B):
assert (len(A) == len(B))
s = 0
for k in xrange(0,n):
s+=A[k]*B[k]
return s
leadingzerocounts = [0]*m
for S in itertools.product([-1,1], repeat = n):
S1 = S + S
for F in itertools.product([-1,1], repeat = n):
i = 0
while (i<m):
ip = innerproduct(F, S1[i:i+n])
if (ip == 0):
leadingzerocounts[i] +=1
i+=1
else:
break
print leadingzerocounts
n=14
的正确输出为
[56229888, 23557248, 9903104, 4160640, 1758240, 755392, 344800, 172320, 101312, 75776, 65696, 61216, 59200, 59200, 59200]
使用pypy,n = 14时需要1分18秒。不幸的是,我真的想要运行它的16、18、20、22、24、26。如果有可能,我不介意使用numba或cython,但我希望尽可能接近Python。
非常感谢任何帮助加速这个程序。
我会在这里记录最快的解决方案。(如果我错过了更新的答案,请告诉我。)
- Eisenstat(C)以9m35.081s获得n = 22
- Eisenstat(pypy)以1m16.344s获得n = 18
- Tupteq(pypy)以2m54.998s获得n = 18
- Neil(numpy)以26秒获得n = 14
- kslote1(pypy)以11m59.192s获得n = 14
IP(A,B) = IP(A[:n/2 + 1], B[:n/2 + 1]) + IP(A[n/2 + 1:], B[n/2 + 1:])
这一点,可以基于 subset sum 中使用的类似技术进行改进。这应该可以实现O(2^N)
的算法而不是O(2^(2N))
,尽管可能需要O(2^N)
的空间。这利用了查找所有大小为N / 2
的配对的所有IP地址(其中有O(2^N)
个),然后使用它来构建解集。可以使用图来处理while循环中找到的状态转换。 - NuclearmanO(2^N)
,但我认为这很不可能,否则它很可能不会比David Eisenstat的答案更好。 - Nuclearman