blocks|key|143027|text|提高n倍的一个非常简单的方法是更改以下代码：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|143028|def+innerproduct(A,+B):
++++assert+(len(A)+==+len(B))
++++for+j+in+xrange(len(A)):
++++++++s+=+0+
++++++++for+k+in+xrange(0,n):
++++++++++++s%2B=A[k]*B[k]
++++return+s|code-block|syntax|javascript|143029|至|143030|def+innerproduct(A,+B):
++++assert+(len(A)+==+len(B))
++++s+=+0+
++++for+k+in+xrange(0,n):
++++++++s%2B=A[k]*B[k]
++++return+s|143031|(我不知道为什么在j上有循环，但它每次都进行相同的计算，所以没有必要。)|143032|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|R|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|S|8|@]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

One very simple speed up of a factor of n is to change this code:

<pre><code>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
</code></pre>

to

<pre><code>def innerproduct(A, B):
 assert (len(A) == len(B))
 s = 0 
 for k in xrange(0,n):
 s+=A[k]*B[k]
 return s
</code></pre>

(I don't know why you have the loop over j, but it just does the same calculation each time so is unnecessary.)

blocks|key|2933398|text|我已经尝试将它转换到NumPy数组中，并借用了这个问题：itertools+product+speed+up|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2933399|这就是我所得到的(这里可能有更多的加速)：|2933400|def+find_leading_zeros(n):
++++if+n+%25+2:
++++++++return+numpy.zeros(n)
++++m+=+n%2B1
++++leading_zero_counts+=+numpy.zeros(m)
++++product_list+=+[-1,+1]
++++repeat+=+n
++++s+=+(numpy.array(product_list)[numpy.rollaxis(numpy.indices((len(product_list),)+*+repeat),
++++++++++++++++++++++++++++++++++++++++++++++++++0,+repeat+%2B+1).reshape(-1,+repeat)]).astype('int8')
++++i+=+0
++++size+=+s.shape[0]+/+2
++++products+=+numpy.zeros((size,+size),+dtype=bool)
++++while+i+<+m:
++++++++products+%2B=+(numpy.tensordot(s[0:size,+0:size],
+++++++++++++++++++++++++++++++++++++numpy.roll(s,+i,+axis=1)[0:size,+0:size],
+++++++++++++++++++++++++++++++++++++axes=(-1,-1))).astype('bool')
++++++++leading_zero_counts[i]+=+(products.size+-+numpy.sum(products))+*+4
++++++++i+%2B=+1

++++return+leading_zero_counts|code-block|syntax|javascript|2933401|为n=14运行时，我得到：|2933402|>>>+find_leading_zeros(14)
array([+56229888.,++23557248.,+++9903104.,+++4160640.,+++1758240.,
++++++++755392.,++++344800.,++++172320.,++++101312.,+++++75776.,
++++++++65696.,+++++61216.,+++++59200.,+++++59200.,+++++59200.])|2933403|所以一切看起来都很好。至于速度：|2933404|>>>+timeit.timeit("find_leading_zeros_old(10)",+number=10)
28.775046825408936
>>>+timeit.timeit("find_leading_zeros(10)",+number=10)
2.236745834350586|2933405|看看你怎么想的。|2933406|编辑：|2933407|最初的版本使用了2074MB的内存用于N=14，所以我删除了连接数组，转而使用numpy.roll。此外，将数据类型更改为使用布尔数组，将使n=14的内存降至277MB。|style|CODE|2933408|在时间上，编辑速度又快了一点：|2933409|>>>+timeit.timeit("find_leading_zeros(10)",+number=10)
1.3816070556640625|2933410|EDIT2：|2933411|加上David指出的对称性，我再减少一次。它现在使用213MB。与之前的编辑相比的比较时间：|2933412|>>>+timeit.timeit("find_leading_zeros(10)",+number=10)
0.35357093811035156+|2933413|我现在可以在我的mac上在14秒内完成n=14，我认为这对“纯python”来说是不错的。|2933414|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/4709510/itertools-product-speed-up^0|S|Q|0|0|0|0|0|0|0|0|0|0|13|A|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|1K|8|@]|9|@$A|1L|B|1M|1|1N]]|C|$]]|$1|D|3|E|5|6|7|1O|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|1P|8|@]|9|@]|C|$I|J]]|$1|K|3|L|5|6|7|1Q|8|@]|9|@]|C|$]]|$1|M|3|N|5|H|7|1R|8|@]|9|@]|C|$I|J]]|$1|O|3|P|5|6|7|1S|8|@]|9|@]|C|$]]|$1|Q|3|R|5|H|7|1T|8|@]|9|@]|C|$I|J]]|$1|S|3|T|5|6|7|1U|8|@]|9|@]|C|$]]|$1|U|3|V|5|6|7|1V|8|@]|9|@]|C|$]]|$1|W|3|X|5|6|7|1W|8|@$A|1X|B|1Y|Y|Z]]|9|@]|C|$]]|$1|10|3|11|5|6|7|1Z|8|@]|9|@]|C|$]]|$1|12|3|13|5|H|7|20|8|@]|9|@]|C|$I|J]]|$1|14|3|15|5|6|7|21|8|@]|9|@]|C|$]]|$1|16|3|17|5|6|7|22|8|@]|9|@]|C|$]]|$1|18|3|19|5|H|7|23|8|@]|9|@]|C|$I|J]]|$1|1A|3|1B|5|6|7|24|8|@]|9|@]|C|$]]|$1|1C|3|-4|5|6|7|25|8|@]|9|@]|C|$]]]|1D|$1E|$5|1F|1G|1H|C|$1I|1J]]]]

I have had a go transferring this into NumPy arrays and borrowed from this question: <a href="https://stackoverflow.com/questions/4709510/itertools-product-speed-up">itertools product speed up</a> 

This is what I have got, (there may be more speed ups here):

<pre><code>def find_leading_zeros(n):
 if n % 2:
 return numpy.zeros(n)
 m = n+1
 leading_zero_counts = numpy.zeros(m)
 product_list = [-1, 1]
 repeat = n
 s = (numpy.array(product_list)[numpy.rollaxis(numpy.indices((len(product_list),) * repeat),
 0, repeat + 1).reshape(-1, repeat)]).astype('int8')
 i = 0
 size = s.shape[0] / 2
 products = numpy.zeros((size, size), dtype=bool)
 while i &lt; m:
 products += (numpy.tensordot(s[0:size, 0:size],
 numpy.roll(s, i, axis=1)[0:size, 0:size],
 axes=(-1,-1))).astype('bool')
 leading_zero_counts[i] = (products.size - numpy.sum(products)) * 4
 i += 1

 return leading_zero_counts
</code></pre>

Running for n=14 I get:

<pre><code>&gt;&gt;&gt; find_leading_zeros(14)
array([ 56229888., 23557248., 9903104., 4160640., 1758240.,
 755392., 344800., 172320., 101312., 75776.,
 65696., 61216., 59200., 59200., 59200.])
</code></pre>

So all looks good. As for speed:

<pre><code>&gt;&gt;&gt; timeit.timeit("find_leading_zeros_old(10)", number=10)
28.775046825408936
&gt;&gt;&gt; timeit.timeit("find_leading_zeros(10)", number=10)
2.236745834350586
</code></pre>

See what you think. 

EDIT:

The original version used 2074MB of memory for N=14 so I have removed the concatenated array and used <code>numpy.roll</code> instead. Also changing the data types to use a boolean array, brings the memory down to 277MB for n=14. 

Time wise the edit is a little faster again:

<pre><code>&gt;&gt;&gt; timeit.timeit("find_leading_zeros(10)", number=10)
1.3816070556640625
</code></pre>

EDIT2:

Ok so adding in the symmetry as pointed out by David I reduce this again. It now uses 213MB. The comparison timing compared to previous edits:

<pre><code>&gt;&gt;&gt; timeit.timeit("find_leading_zeros(10)", number=10)
0.35357093811035156 
</code></pre>

I can now do the n=14 case in 14 seconds on my mac book which is not bad for "pure python" I think.

blocks|key|145333|text|这个新的代码通过利用问题的循环对称性获得了另一个数量级的加速。此Python版本使用Duval算法枚举项链；C版本使用蛮力。两者都包含了下面描述的加速。在我的机器上，C版本在100秒内解决了n=+20！粗略的计算表明，如果你让它在单个内核上运行一周，它可以解决n=+26，并且，如下所述，它符合并行性。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|145334|import+itertools


def+necklaces_with_multiplicity(n):
++++assert+isinstance(n,+int)
++++assert+n+>+0
++++w+=+[1]+*+n
++++i+=+1
++++while+True:
++++++++if+n+%25+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+%2B=+1
++++++++for+j+in+range(n+-+i):
++++++++++++w[i+%2B+j]+=+w[j]


def+leading_zero_counts(n):
++++assert+isinstance(n,+int)
++++assert+n+>+0
++++assert+n+%25+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]+%2B=+multiplicity+*+2
++++++++++++++++product+=+0
++++++++++++++++for+j+in+range(n):
++++++++++++++++++++product+%2B=+v[j+-+(i+%2B+1)]+*+w[j]
++++++++++++++++if+product+!=+0:
++++++++++++++++++++break
++++return+counts


if+__name__+==+'__main__':
++++print(leading_zero_counts(12))|code-block|syntax|javascript|145335|C版本：|145336|#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%2B%2B)+{
++++int+multiplicity;
++++unsigned+int+w+=+v;
++++for+(multiplicity+=+2;+multiplicity+<+2+*+N;+multiplicity+%2B=+2)+{
++++++w+=+((w+&+1)+<<+(N+-+1))+%7C+(w+>>+1);
++++++unsigned+int+x+=+w+%5E+((1U+<<+N)+-+1);
++++++if+(w+<+v+%7C%7C+x+<+v)+goto+nope;
++++++if+(w+==+v+%7C%7C+x+==+v)+break;
++++}
++++g_necklace[g_necklace_count].v+=+v;
++++g_necklace[g_necklace_count].multiplicity+=+multiplicity;
++++g_necklace_count%2B%2B;
+++nope:
++++;
++}
}

int+main(void)+{
++initialize_necklace();
++long+long+leading_zero_count[N+%2B+1];
++for+(int+i+=+0;+i+<+N+%2B+1;+i%2B%2B)+leading_zero_count[i]+=+0;
++for+(unsigned+int+v_xor_w+=+0;+v_xor_w+<+(1U+<<+(N+-+1));+v_xor_w%2B%2B)+{
++++if+(__builtin_popcount(v_xor_w)+!=+N+/+2)+continue;
++++for+(int+k+=+0;+k+<+g_necklace_count;+k%2B%2B)+{
++++++unsigned+int+v+=+g_necklace[k].v;
++++++unsigned+int+w+=+v+%5E+v_xor_w;
++++++for+(int+i+=+0;+i+<+N+%2B+1;+i%2B%2B)+{
++++++++leading_zero_count[i]+%2B=+g_necklace[k].multiplicity;
++++++++w+=+((w+&+1)+<<+(N+-+1))+%7C+(w+>>+1);
++++++++if+(__builtin_popcount(v+%5E+w)+!=+N+/+2)+break;
++++++}
++++}
++}
++for+(int+i+=+0;+i+<+N+%2B+1;+i%2B%2B)+{
++++printf("+%25lld",+2+*+leading_zero_count[i]);
++}
++putchar('\n');
++return+0;
}|145337|145338|您可以通过利用符号对称性(4x)并仅迭代通过第一个内积测试的向量(渐近地，O(sqrt(n))x)来获得一些加速。|145339|import+itertools


n+=+10
m+=+n+%2B+1


def+innerproduct(A,+B):
++++s+=+0
++++for+k+in+range(n):
++++++++s+%2B=+A[k]+*+B[k]
++++return+s


leadingzerocounts+=+[0]+*+m
for+S+in+itertools.product([-1,+1],+repeat=n+-+1):
++++S1+=+S+%2B+(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]+%2B=+4
++++++++for+i+in+range(1,+m):
++++++++++++if+innerproduct(F,+S1S1[i:i+%2B+n]):
++++++++++++++++break
++++++++++++leadingzerocounts[i]+%2B=+4
print(leadingzerocounts)|145340|C版本，以了解我们的性能在多大程度上输给了PyPy+(+PyPy的16大致相当于C的18+)：|145341|#include+<stdio.h>

enum+{
++HALFN+=+9,
++N+=+2+*+HALFN
};

int+main(void)+{
++long+long+lzc[N+%2B+1];
++for+(int+i+=+0;+i+<+N+%2B+1;+i%2B%2B)+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]%2B%2B;
++++++unsigned+int+f+=+xor+%5E+s;
++++++for+(int+i+=+1;+i+<+N+%2B+1;+i%2B%2B)+{
++++++++f+=+((f+&+1)+<<+(N+-+1))+%7C+(f+>>+1);
++++++++if+(__builtin_popcount(f+%5E+s)+!=+HALFN)+break;
++++++++lzc[i]%2B%2B;
++++++}
++++}
++}
++for+(int+i+=+0;+i+<+N+%2B+1;+i%2B%2B)+printf("+%25lld",+4+*+lzc[i]);
++putchar('\n');
++return+0;
}|145342|这个算法的并行性令人尴尬，因为它只是累加xor的所有值。对于C版本，粗略的计算表明，几千个小时的CPU时间足以计算n+=+26，按照EC2上的当前汇率，这相当于几百美元。毫无疑问，有一些优化需要进行(例如，矢量化)，但对于这样的一次性优化，我不确定程序员的更多努力是值得的。|offset|length|style|CODE|145343|entityMap^0|0|0|0|0|0|0|0|0|0|K|3|1L|6|0^^$0|@$1|2|3|4|5|6|7|11|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|12|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|13|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|14|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|15|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|16|8|@]|9|@]|A|$]]|$1|N|3|O|5|D|7|17|8|@]|9|@]|A|$E|F]]|$1|P|3|Q|5|6|7|18|8|@]|9|@]|A|$]]|$1|R|3|S|5|D|7|19|8|@]|9|@]|A|$E|F]]|$1|T|3|U|5|6|7|1A|8|@$V|1B|W|1C|X|Y]|$V|1D|W|1E|X|Y]]|9|@]|A|$]]|$1|Z|3|-4|5|6|7|1F|8|@]|9|@]|A|$]]]|10|$]]

This new code gets another order of magnitude speedup by taking advantage of the cyclic symmetry of the problem. This Python version enumerates necklaces with Duval's algorithm; the C version uses brute force. Both incorporate the speedups described below. On my machine, the C version solves n = 20 in 100 seconds! A back-of-the-envelope calculation suggests that, if you were to let it run for a week on a single core, it could do n = 26, and, as noted below, it's amenable to parallelism.

<pre><code>import itertools


def necklaces_with_multiplicity(n):
 assert isinstance(n, int)
 assert n &gt; 0
 w = [1] * n
 i = 1
 while True:
 if n % i == 0:
 s = sum(w)
 if s &gt; 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 &gt; 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))
</code></pre>

C version:

<pre><code>#include &lt;stdio.h&gt;

enum {
 N = 14
};

struct Necklace {
 unsigned int v;
 int multiplicity;
};

static struct Necklace g_necklace[1 &lt;&lt; (N - 1)];
static int g_necklace_count;

static void initialize_necklace(void) {
 g_necklace_count = 0;
 for (unsigned int v = 0; v &lt; (1U &lt;&lt; (N - 1)); v++) {
 int multiplicity;
 unsigned int w = v;
 for (multiplicity = 2; multiplicity &lt; 2 * N; multiplicity += 2) {
 w = ((w &amp; 1) &lt;&lt; (N - 1)) | (w &gt;&gt; 1);
 unsigned int x = w ^ ((1U &lt;&lt; N) - 1);
 if (w &lt; v || x &lt; 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 &lt; N + 1; i++) leading_zero_count[i] = 0;
 for (unsigned int v_xor_w = 0; v_xor_w &lt; (1U &lt;&lt; (N - 1)); v_xor_w++) {
 if (__builtin_popcount(v_xor_w) != N / 2) continue;
 for (int k = 0; k &lt; g_necklace_count; k++) {
 unsigned int v = g_necklace[k].v;
 unsigned int w = v ^ v_xor_w;
 for (int i = 0; i &lt; N + 1; i++) {
 leading_zero_count[i] += g_necklace[k].multiplicity;
 w = ((w &amp; 1) &lt;&lt; (N - 1)) | (w &gt;&gt; 1);
 if (__builtin_popcount(v ^ w) != N / 2) break;
 }
 }
 }
 for (int i = 0; i &lt; N + 1; i++) {
 printf(" %lld", 2 * leading_zero_count[i]);
 }
 putchar('\n');
 return 0;
}
</code></pre>

<hr>

You can get a bit of speedup by exploiting the sign symmetry (4x) and by iterating over only those vectors that pass the first inner product test (asymptotically, O(sqrt(n))x).

<pre><code>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)
</code></pre>

C version, to get a feel for how much performance we're losing to PyPy (16 for PyPy is roughly equivalent to 18 for C):

<pre><code>#include &lt;stdio.h&gt;

enum {
 HALFN = 9,
 N = 2 * HALFN
};

int main(void) {
 long long lzc[N + 1];
 for (int i = 0; i &lt; N + 1; i++) lzc[i] = 0;
 unsigned int xor = 1 &lt;&lt; (N - 1);
 while (xor-- &gt; 0) {
 if (__builtin_popcount(xor) != HALFN) continue;
 unsigned int s = 1 &lt;&lt; (N - 1);
 while (s-- &gt; 0) {
 lzc[0]++;
 unsigned int f = xor ^ s;
 for (int i = 1; i &lt; N + 1; i++) {
 f = ((f &amp; 1) &lt;&lt; (N - 1)) | (f &gt;&gt; 1);
 if (__builtin_popcount(f ^ s) != HALFN) break;
 lzc[i]++;
 }
 }
 }
 for (int i = 0; i &lt; N + 1; i++) printf(" %lld", 4 * lzc[i]);
 putchar('\n');
 return 0;
}
</code></pre>

This algorithm is embarrassingly parallel because it's just accumulating over all values of <code>xor</code>. With the C version, a back-of-the-envelope calculation suggests that a few thousand hours of CPU time would suffice to calculate <code>n = 26</code>, which works out to a couple hundred dollars at current rates on EC2. There are undoubtedly some optimizations to be made (e.g., vectorization), but for a one-off like this I'm not sure how much more programmer effort is worthwhile.

blocks|key|143110|text|我试图加快速度，但我失败了:(但我发送了代码，它在某种程度上更快，但对于像n=24这样的值来说还不够快。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|143111|我的假设|143112|你的列表是由值组成的，所以我决定使用数字而不是列表-每一位代表一个可能的值:如果位被设置，那么这意味着1，如果它被设置为0，它意味着-1。乘法{-1,+1}的唯一可能结果是1或-1，因此我使用按位XOR而不是乘法。我还注意到有一个对称性，所以你只需要检查可能列表的子集(四分之一)，并将结果乘以4+(David在他的答案中解释了这一点)。|143113|最后，我将可能的操作结果放到表中，以消除计算的需要。它需要很大的内存，但谁在乎呢(对于n=24来说大约是150MB)？|143114|然后@David+Eisenstat回答了这个问题:)所以，我采用了他的代码并将其修改为基于位的。它的速度大约是n=26的2-3倍(+n=16需要大约30秒，而David的解决方案需要大约90秒)，但我认为这仍然不足以获得n=26的结果。|143115|import+itertools

n+=+16
m+=+n+%2B+1
mask+=+(2+**+n)+-+1

#+Create+table+of+sum+results+(replaces+innerproduct())
tab+=+[]
for+a+in+range(2+**+n):
++++s+=+0
++++for+k+in+range(n):
++++++++s+%2B=+-1+if+a+&+1+else+1
++++++++a+>>=+1
++++tab.append(s)

#+Create+combination+bit+masks+for+combinations
comb+=+[]
for+C+in+itertools.combinations(range(n+-+1),+n+//+2):
++++xor+=+0
++++for+i+in+C:
+++++++xor+%7C=+(1+<<+i)
++++comb.append(xor)

leadingzerocounts+=+[0]+*+m
for+S+in+xrange(2+**+(n-1)):
++++S1+=+S+%2B+(1+<<+(n-1))
++++S1S1+=+S1+%2B+(S1+<<+n)

++++for+xor+in+comb:
++++++++F+=+S1+%5E+xor

++++++++leadingzerocounts[0]+%2B=+4
++++++++for+i+in+range(1,+m):
++++++++++++if+tab[F+%5E+((S1S1+>>+i)+&+mask)]:
++++++++++++++++break
++++++++++++leadingzerocounts[i]+%2B=+4

print(leadingzerocounts)|code-block|syntax|javascript|143116|结论|BOLD|143117|我以为我发明了一些很棒的东西，希望所有这些乱七八糟的比特都能给我带来很大的速度提升，但提升的幅度小得令人失望:(|143118|我认为原因在于Python使用运算符的方式-它为每个算术(或逻辑)操作调用函数，即使它可以通过单个汇编程序命令来完成(我希望pypy能够将操作简化到那个级别，但它没有)。因此，如果将C(或ASM)与这种位操作解决方案一起使用，它的性能可能会很好(也许您可以使用n=24)。|143119|entityMap^0|11|4|0|0|1F|1|1U|2|1Z|7|2E|1|2G|2|2Q|3|0|17|4|0|1K|4|1V|4|33|4|0|0|0|2|0|0|1Q|4|3M|4|0^^$0|@$1|2|3|4|5|6|7|11|8|@$9|12|A|13|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|14|8|@]|D|@]|E|$]]|$1|H|3|I|5|6|7|15|8|@$9|16|A|17|B|C]|$9|18|A|19|B|C]|$9|1A|A|1B|B|C]|$9|1C|A|1D|B|C]|$9|1E|A|1F|B|C]|$9|1G|A|1H|B|C]]|D|@]|E|$]]|$1|J|3|K|5|6|7|1I|8|@$9|1J|A|1K|B|C]]|D|@]|E|$]]|$1|L|3|M|5|6|7|1L|8|@$9|1M|A|1N|B|C]|$9|1O|A|1P|B|C]|$9|1Q|A|1R|B|C]]|D|@]|E|$]]|$1|N|3|O|5|P|7|1S|8|@]|D|@]|E|$Q|R]]|$1|S|3|T|5|6|7|1T|8|@$9|1U|A|1V|B|U]]|D|@]|E|$]]|$1|V|3|W|5|6|7|1W|8|@]|D|@]|E|$]]|$1|X|3|Y|5|6|7|1X|8|@$9|1Y|A|1Z|B|C]|$9|20|A|21|B|C]]|D|@]|E|$]]|$1|Z|3|-4|5|6|7|22|8|@]|D|@]|E|$]]]|10|$]]

I tried to speed this up and I failed badly :(
But I'm sending the code, it's somehow faster, but not fast enough for values like <code>n=24</code>.

My assumptions

Your lists consist from values, so I decided to use numbers instead of lists - each bit represents one of possible values: if bit is set, then this means <code>1</code>, if it's zeroed it means <code>-1</code>. The only possible result of multiplication <code>{-1, 1}</code> is <code>1</code> or <code>-1</code>, so I used bitwise <code>XOR</code> instead of multiplication. I also noticed that there's a symmetry, so you only need to check subset (one fourth) of possible lists and multiply result by 4 (David explained this in his answer).

Finally I put results of possible operations to tables to eliminate need of calculations. It takes a lot of memory, but who cares (for <code>n=24</code> it was about 150MB)?

And then @David Eisenstat answered the question :)
So, I took his code and modified to bit-based. It's about 2-3 times faster (for <code>n=16</code> it took ~30 seconds, compared to ~90 of David's solution), but I think it's still not enough to get results for <code>n=26</code> or so.

<pre><code>import itertools

n = 16
m = n + 1
mask = (2 ** n) - 1

# Create table of sum results (replaces innerproduct())
tab = []
for a in range(2 ** n):
 s = 0
 for k in range(n):
 s += -1 if a &amp; 1 else 1
 a &gt;&gt;= 1
 tab.append(s)

# Create combination bit masks for combinations
comb = []
for C in itertools.combinations(range(n - 1), n // 2):
 xor = 0
 for i in C:
 xor |= (1 &lt;&lt; i)
 comb.append(xor)

leadingzerocounts = [0] * m
for S in xrange(2 ** (n-1)):
 S1 = S + (1 &lt;&lt; (n-1))
 S1S1 = S1 + (S1 &lt;&lt; n)

 for xor in comb:
 F = S1 ^ xor

 leadingzerocounts[0] += 4
 for i in range(1, m):
 if tab[F ^ ((S1S1 &gt;&gt; i) &amp; mask)]:
 break
 leadingzerocounts[i] += 4

print(leadingzerocounts)
</code></pre>

Conclusions

I thought I invented something brilliant and hoped that all this mess with bits will give a great speed boost, but the boost was disappointingly small :(

I think the reason is the way Python uses operators - it calls function for every arithmetic (or logical) operation, even if it could be done by single assembler command (I hoped <code>pypy</code> will be able to simplify operations to that level, but it didn't). So, probably if C (or ASM) was used with this bit-operating solution, it would perform great (maybe you could get to <code>n=24</code>).

blocks|key|146786|text|在我看来，获得性能提升的一个好方法是使用python内置。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|146787|首先使用map计算条目的乘积：|146788|>>>+a+=[1,2,3]
>>>+b+=+[4,5,6]
>>>map(lambda+x,y+:+x*y,+a+,+b)
[4,+10,+18]|code-block|syntax|javascript|146789|然后使用reduce计算和：|offset|length|146790|>>>+reduce(lambda+v,w:+v%2Bw,+map(lambda+x,y+:x*y,+a,+b))
32|146791|那么你的函数就变成了|146792|def+innerproduct(A,+B):
++++assert+(len(A)+==+len(B))
++++return+reduce(lambda+v,w:+v%2Bw,+map(lambda+x,y+:x*y,+A,+B))|146793|接下来，我们可以删除所有这些"for循环“，并将它们替换为生成器并捕获StopIteration。|146794|#!/usr/bin/python

from+__future__+import+division
import+itertools
import+operator
import+math

n=14
m=n%2B1
def+innerproduct(A,+B):
++++assert+(len(A)+==+len(B))
++++return+reduce(lambda+v,w:+v%2Bw,+map(lambda+x,y+:x*y,+A,+B))


leadingzerocounts+=+[0]*m

S_gen+=+itertools.product([-1,1],+repeat+=+n)

try:
++++while(True):
+++++++S+=+S_gen.next()
+++++++S1+=+S+%2B+S
+++++++F_gen+=+itertools.product([-1,1],+repeat+=+n)
+++++++try:
+++++++++++while(True):
+++++++++++++++F+=+F_gen.next()
+++++++++++++++for+i+in+xrange(m):
+++++++++++++++++++ip+=+innerproduct(F,+S1[i:i%2Bn])
+++++++++++++++++++if+(ip+==+0):
+++++++++++++++++++++++leadingzerocounts[i]+%2B=1
+++++++++++++++++++++++i%2B=1
+++++++++++++++++++else:
++++++++++++++++++++++break
+++++++except+StopIteration:
+++++++++++pass

except+StopIteration+as+e:
++++print+e

print+leadingzerocounts|146795|我观察到小n的速度加快了，但我的jalopy没有足够的马力来计算我的版本，也没有n=14的原始代码。进一步加速的方法是记住这一行：|146796|++++F_gen+=+itertools.product([-1,1],+repeat+=+n)|146797|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.python.org/2/library/functions.html#reduce^0|0|0|0|4|6|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|18|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|19|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|1A|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|1B|8|@]|9|@$K|1C|L|1D|1|1E]]|A|$]]|$1|M|3|N|5|F|7|1F|8|@]|9|@]|A|$G|H]]|$1|O|3|P|5|6|7|1G|8|@]|9|@]|A|$]]|$1|Q|3|R|5|F|7|1H|8|@]|9|@]|A|$G|H]]|$1|S|3|T|5|6|7|1I|8|@]|9|@]|A|$]]|$1|U|3|V|5|F|7|1J|8|@]|9|@]|A|$G|H]]|$1|W|3|X|5|6|7|1K|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|F|7|1L|8|@]|9|@]|A|$G|H]]|$1|10|3|-4|5|6|7|1M|8|@]|9|@]|A|$]]]|11|$12|$5|13|14|15|A|$16|17]]]]

In my opinion, a good way to get a performance boost is to use the python builtins.

First use map to calculate the product of the entries:

<pre><code>&gt;&gt;&gt; a =[1,2,3]
&gt;&gt;&gt; b = [4,5,6]
&gt;&gt;&gt;map(lambda x,y : x*y, a , b)
[4, 10, 18]
</code></pre>

Then use <a href="https://docs.python.org/2/library/functions.html#reduce" rel="nofollow">reduce</a> to compute the sums:

<pre><code>&gt;&gt;&gt; reduce(lambda v,w: v+w, map(lambda x,y :x*y, a, b))
32
</code></pre>

So then your function becomes

<pre><code>def innerproduct(A, B):
 assert (len(A) == len(B))
 return reduce(lambda v,w: v+w, map(lambda x,y :x*y, A, B))
</code></pre>

Next, we can take all of those "for loops" out and replace them with generators and catch the StopIteration.

<pre><code>#!/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))
 return reduce(lambda v,w: v+w, map(lambda x,y :x*y, A, B))


leadingzerocounts = [0]*m

S_gen = itertools.product([-1,1], repeat = n)

try:
 while(True):
 S = S_gen.next()
 S1 = S + S
 F_gen = itertools.product([-1,1], repeat = n)
 try:
 while(True):
 F = F_gen.next()
 for i in xrange(m):
 ip = innerproduct(F, S1[i:i+n])
 if (ip == 0):
 leadingzerocounts[i] +=1
 i+=1
 else:
 break
 except StopIteration:
 pass

except StopIteration as e:
 print e

print leadingzerocounts
</code></pre>

I observed a speed up for smaller n, but my jalopy lacked the horse power to compute my version nor the original code for n=14. A way to speed this up further would be to memoize the line: 

<pre><code> F_gen = itertools.product([-1,1], repeat = n)
</code></pre>

I have some simple code that does the following.

It iterates over all possible length n lists <code>F</code> with +-1 entries. For each one, it iterates over all possible length <code>2n</code> lists <code>S</code> with +-1 entries, where the first half of $S$ is simply a copy of the second half. The code computes the inner product of <code>F</code> with each sublist of <code>S</code> of length <code>n</code>. For each F, S it counts the inner products that are zero until the first non-zero inner product. 

Here is the code. 

<pre><code>#!/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&lt;m):
 ip = innerproduct(F, S1[i:i+n])
 if (ip == 0):
 leadingzerocounts[i] +=1
 i+=1
 else:
 break

print leadingzerocounts
</code></pre>

The correct output for <code>n=14</code> is 

<pre><code>[56229888, 23557248, 9903104, 4160640, 1758240, 755392, 344800, 172320, 101312, 75776, 65696, 61216, 59200, 59200, 59200]
</code></pre>

Using pypy, this takes 1 min 18 seconds for n = 14. Unfortunately, I would really like to run it for 16,18,20,22,24,26. I don't mind using numba or cython but I would like to stay close to python if at all possible. 

Any help speeding this up is very much appreciated.

<hr>

I'll keep a record of the fastest solutions here. (Please let me know if I miss an updated answer.)

<ul>
<li>n = 22 at 9m35.081s by Eisenstat (C)</li>
<li>n = 18 at 1m16.344s by Eisenstat (pypy)</li>
<li>n = 18 at 2m54.998s by Tupteq (pypy)</li>
<li>n = 14 at 26s by Neil (numpy) </li>
<li>n - 14 at 11m59.192s by kslote1 (pypy)</li>
</ul>

How to speed up multiple inner products in python

Python

我有一些执行以下操作的简单代码。它遍历所有可能的长度为n的列表F和+-1个条目。对于每个条目，它都会迭代所有可能长度的2n列表S和+-1条目，其中$S$的前一半只是后半部分的副本。代码计算F与长度为n的S的每个子列表的内积。对于每个F，S，它计算直到第一个非零的内积为零的内积。下面是代码。#!/usr/bin/pyth...

问如何在python中加速多个内部产品
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在python中加速多个内部产品EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在python中加速多个内部产品
EN