How to speed up numpy code

Question

I have the following code. In principle it takes 2^6 * 1000 = 64000 iterations which is quite a small number. However it takes 9s 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 ``` Is it possible to speed this up a lot or should I rewrite it in C? Profiling indicates it spends most of it 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'…

Accepted Answer

An almost fully vectorized version of your code is much faster (16.9%), suppose yours is named `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
```

Timing result:

```
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
```

How to speed up numpy code

Solution

Problem