How to speed up numpy code

Question

I have the following code. In principle, 2 ^ 6 * 1000 = 64000 iterations are required, which is quite small. However, it takes 9 seconds on my computer, and I would like to run it for n = 15 at least.

from __future__ import division
import numpy as np
import itertools

n=6
iters = 1000
firstzero = 0
bothzero = 0
for S in itertools.product([-1,1], repeat = n+1):
    for i in xrange(iters):
        F = np.random.choice(np.array([-1,0,0,1], dtype=np.int8), size = n)
        while np.all(F ==0):
            F = np.random.choice(np.array([-1,0,0,1], dtype=np.int8), size = n)
        FS = np.convolve(F,S, 'valid')
        if (FS[0] == 0):
            firstzero += 1
        if np.all(FS==0):
            bothzero += 1

print "firstzero",    firstzero
print "bothzero",  bothzero

Can this be accelerated or rewritten in C?

Profiling indicates that he spends most of his time in

   258003    0.418    0.000    3.058    0.000 fromnumeric.py:1842(all)
   130003    1.245    0.000    2.907    0.000 {method 'choice' of 'mtrand.RandomState' objects}
   388006    2.488    0.000    2.488    0.000 {method 'reduce' of 'numpy.ufunc' objects}
   128000    0.731    0.000    2.215    0.000 numeric.py:873(convolve)
   258003    0.255    0.000    2.015    0.000 {method 'all' of 'numpy.ndarray' objects}
   258003    0.301    0.000    1.760    0.000 _methods.py:35(_all)
   130003    0.470    0.000    1.663    0.000 fromnumeric.py:2249(prod)
   644044    1.483    0.000    1.483    0.000 {numpy.core.multiarray.array}
   130003    0.164    0.000    1.193    0.000 _methods.py:27(_prod)
   258003    0.283    0.000    0.624    0.000 numeric.py:462(asanyarray)

Answer 1

An almost fully vectorized version of your code runs much faster (16.9%), suppose your name is f():

def g():
        n=6
        iters = 1000
        S=np.repeat(list(itertools.product([-1,1], repeat = n+1)),iters, axis=0).reshape((-1,n+1))
        F=np.random.choice(np.array([-1,0,0,1], dtype=np.int8), size = (iters*(2**(n+2)),n)) #oversampling
        F=F[~(F==0).all(1)][:iters*(2**(n+1))]
        FS=np.asanyarray(map(lambda x, y: np.convolve(x, y, 'valid'), F, S))
        firstzero=(FS[:,0]==0).sum()
        bothzero=(FS==0).all(1).sum()
        print "firstzero",    firstzero
        print "bothzero",  bothzero

Result of synchronization:

In [164]:

%timeit f()
firstzero 27171
bothzero 12151
firstzero 27206
bothzero 12024
firstzero 27272
bothzero 12135
firstzero 27173
bothzero 12079
1 loops, best of 3: 14.6 s per loop
In [165]:

%timeit g()
firstzero 27182
bothzero 11952
firstzero 27365
bothzero 12174
firstzero 27318
bothzero 12173
firstzero 27377
bothzero 12072
1 loops, best of 3: 2.47 s per loop

Answer 2

I got acceleration of 35-40% very easily, creating all the random options in one shot:

for S in itertools.product([-1,1], repeat = n+1):
    Fx = np.random.choice(np.array([-1,0,0,1], dtype=np.int8), size=(iters,n))                                       
        for F in Fx:

for i in xrange(iters).

, , scipy.signal.fftconvolve (np.convolve 1D-). , , scipy.org , , , , . , Python, .