ele*_*ora 18 python algorithm performance cython numba
我有一些简单的代码,可以执行以下操作.
它F使用+ -1条目迭代所有可能的长度n列表.对于每一个,它使用+ -1条目迭代所有可能的长度2n列表S,其中$ S $的前半部分只是下半部分的副本.代码计算F每个S长度子列表的内积n.对于每个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.
任何帮助加快这一点的人都非常感激.
我会在这里记录最快的解决方案.(如果我错过了更新的答案,请告诉我.)
Dav*_*tat 22
通过利用问题的循环对称性,这个新代码获得了另一个数量级的加速.这个Python版本使用Duval的算法枚举项链; C版本使用蛮力.两者都包含下面描述的加速.在我的机器上,C版本在100秒内解决了n = 20!一个背后的计算表明,如果你让它在一个核心上运行一周,它可以做n = 26,并且,如下所述,它可以顺应并行.
import itertools
def necklaces_with_multiplicity(n):
assert isinstance(n, int)
assert n > 0
w = [1] * n
i = 1
while True:
if n % i == 0:
s = sum(w)
if s > 0:
yield (tuple(w), i * 2)
elif s == 0:
yield (tuple(w), i)
i = n - 1
while w[i] == -1:
if i == 0:
return
i -= 1
w[i] = -1
i += 1
for j in range(n - i):
w[i + j] = w[j]
def leading_zero_counts(n):
assert isinstance(n, int)
assert n > 0
assert n % 2 == 0
counts = [0] * n
necklaces = list(necklaces_with_multiplicity(n))
for combo in itertools.combinations(range(n - 1), n // 2):
for v, multiplicity in necklaces:
w = list(v)
for j in combo:
w[j] *= -1
for i in range(n):
counts[i] += multiplicity * 2
product = 0
for j in range(n):
product += v[j - (i + 1)] * w[j]
if product != 0:
break
return counts
if __name__ == '__main__':
print(leading_zero_counts(12))
C版:
#include <stdio.h>
enum {
N = 14
};
struct Necklace {
unsigned int v;
int multiplicity;
};
static struct Necklace g_necklace[1 << (N - 1)];
static int g_necklace_count;
static void initialize_necklace(void) {
g_necklace_count = 0;
for (unsigned int v = 0; v < (1U << (N - 1)); v++) {
int multiplicity;
unsigned int w = v;
for (multiplicity = 2; multiplicity < 2 * N; multiplicity += 2) {
w = ((w & 1) << (N - 1)) | (w >> 1);
unsigned int x = w ^ ((1U << N) - 1);
if (w < v || x < v) goto nope;
if (w == v || x == v) break;
}
g_necklace[g_necklace_count].v = v;
g_necklace[g_necklace_count].multiplicity = multiplicity;
g_necklace_count++;
nope:
;
}
}
int main(void) {
initialize_necklace();
long long leading_zero_count[N + 1];
for (int i = 0; i < N + 1; i++) leading_zero_count[i] = 0;
for (unsigned int v_xor_w = 0; v_xor_w < (1U << (N - 1)); v_xor_w++) {
if (__builtin_popcount(v_xor_w) != N / 2) continue;
for (int k = 0; k < g_necklace_count; k++) {
unsigned int v = g_necklace[k].v;
unsigned int w = v ^ v_xor_w;
for (int i = 0; i < N + 1; i++) {
leading_zero_count[i] += g_necklace[k].multiplicity;
w = ((w & 1) << (N - 1)) | (w >> 1);
if (__builtin_popcount(v ^ w) != N / 2) break;
}
}
}
for (int i = 0; i < N + 1; i++) {
printf(" %lld", 2 * leading_zero_count[i]);
}
putchar('\n');
return 0;
}
通过利用符号对称性(4x)并仅迭代通过第一个内积测试的那些向量(渐近,O(sqrt(n))x),可以获得一点加速.
import itertools
n = 10
m = n + 1
def innerproduct(A, B):
s = 0
for k in range(n):
s += A[k] * B[k]
return s
leadingzerocounts = [0] * m
for S in itertools.product([-1, 1], repeat=n - 1):
S1 = S + (1,)
S1S1 = S1 * 2
for C in itertools.combinations(range(n - 1), n // 2):
F = list(S1)
for i in C:
F[i] *= -1
leadingzerocounts[0] += 4
for i in range(1, m):
if innerproduct(F, S1S1[i:i + n]):
break
leadingzerocounts[i] += 4
print(leadingzerocounts)
C版本,以了解我们输给PyPy的性能有多少(PyPy为16,C大致相当于18):
#include <stdio.h>
enum {
HALFN = 9,
N = 2 * HALFN
};
int main(void) {
long long lzc[N + 1];
for (int i = 0; i < N + 1; i++) lzc[i] = 0;
unsigned int xor = 1 << (N - 1);
while (xor-- > 0) {
if (__builtin_popcount(xor) != HALFN) continue;
unsigned int s = 1 << (N - 1);
while (s-- > 0) {
lzc[0]++;
unsigned int f = xor ^ s;
for (int i = 1; i < N + 1; i++) {
f = ((f & 1) << (N - 1)) | (f >> 1);
if (__builtin_popcount(f ^ s) != HALFN) break;
lzc[i]++;
}
}
}
for (int i = 0; i < N + 1; i++) printf(" %lld", 4 * lzc[i]);
putchar('\n');
return 0;
}
这个算法令人尴尬地平行,因为它只是积累了所有的值xor.对于C版本,一个背后的计算表明,几千小时的CPU时间就足以计算n = 26出来了,EC2上目前的速率可以达到几百美元.毫无疑问会有一些优化(例如,矢量化),但对于这样的一次性,我不确定程序员的努力是多少值得.
一个非常简单的加速因子是改变这个代码:
def innerproduct(A, B):
assert (len(A) == len(B))
for j in xrange(len(A)):
s = 0
for k in xrange(0,n):
s+=A[k]*B[k]
return s
至
def innerproduct(A, B):
assert (len(A) == len(B))
s = 0
for k in xrange(0,n):
s+=A[k]*B[k]
return s
(我不知道为什么你的循环超过j,但它每次只进行相同的计算,所以没必要.)