How slow is Python really? (Or how fast is your language?) I have this code which I have written in Python/NumPy

from __future__ import division
import numpy as np
import itertools

n = 6
iters = 1000
firstzero = 0
bothzero = 0
""" The next line iterates over arrays of length n+1 which contain only -1s and 1s """
for S in itertools.product([-1, 1], repeat=n+1):
    """For i from 0 to iters -1 """
    for i in xrange(iters):
        """ Choose a random array of length n.
            Prob 1/4 of being -1, prob 1/4 of being 1 and prob 1/2 of being 0. """
        F = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n)
        """The next loop just makes sure that F is not all zeros."""
        while np.all(F == 0):
            F = np.random.choice(np.array([-1, 0, 0, 1], dtype=np.int8), size=n)
        """np.convolve(F, S, 'valid') computes two inner products between
        F and the two successive windows of S of length n."""
        FS = np.convolve(F, S, 'valid')
        if FS[0] == 0:
            firstzero += 1
        if np.all(FS == 0):
            bothzero += 1

print("firstzero: %i" % firstzero)
print("bothzero: %i" % bothzero)


It is counting the number of times the convolution of two random arrays, one which is one longer than the other, with a particular probability distribution, has a 0 at the first position or a 0 in both positions.

I had a bet with a friend who says Python is a terrible language to write code in that needs to be fast.  It takes 9s on my computer.  He says it could be made 100 times faster if written in a "proper language".

The challenge is to see if this code can indeed by made 100 times faster in any language of your choice.  I will test your code and the fastest one week from now will win.  If anyone gets below 0.09s then they automatically win and I lose.

Status  


Python. 30 times speed up by Alistair Buxon! Although not the fastest solution it is in fact my favourite.
Octave. 100 times speed up by @Thethos.
Rust. 500 times speed up by @dbaupp.
C++. 570 times speed up by Guy Sirton.
C. 727 times speed up by @ace.
C++. Unbelievably fast by @Stefan.


The fastest solutions are now too fast to sensibly time.  I have therefore increased n to 10 and set iters = 100000 to compare the best ones. Under this measure the fastest are.


C. 7.5s by @ace. 
C++. 1s by @Stefan.


My Machine The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor.  This also means I need to be able to run your code.

Follow up posted As this competition was rather too easy to get a x100 speedup, I have posted a followup for those who want to exercise their speed guru expertise. See How Slow Is Python Really (Part II)?
Python2.7 + Numpy 1.8.1: 10.242 s

Fortran 90+: 0.029 s 0.003 s 0.022 s  0.010 s

Damn straight you lost your bet! Not a drop of parallelization here too, just straight Fortran 90+.

EDIT I've taken Guy Sirton's algorithm for permuting the array S (good find :D). I apparently also had the -g -traceback compiler flags active which were slowing this code down to about 0.017s. Currently, I am compiling this as 

ifort -fast -o convolve convolve_random_arrays.f90


For those who don't have ifort, you can use

gfortran -O3 -ffast-math -o convolve convolve_random_arrays.f90


EDIT 2: The decrease in run-time is because I was doing something wrong previously and got an incorrect answer. Doing it the right way is apparently slower. I still can't believe that C++ is faster than mine, so I'm probably going to spend some time this week trying to tweak the crap out of this to speed it up.

EDIT 3: By simply changing the RNG section using one based on BSD's RNG (as suggested by Sampo Smolander) and eliminating the constant divide by m1, I cut the run-time to the same as the C++ answer by Guy Sirton. Using static arrays (as suggested by Sharpie) drops the run-time to under the C++ run-time! Yay Fortran! :D

EDIT 4 Apparently this doesn't compile (with gfortran) and run correctly (incorrect values) because the integers are overstepping their limits. I've made corrections to ensure it works, but this requires one to have either ifort 11+ or gfortran 4.7+ (or another compiler that allows iso_fortran_env and the F2008 int64 kind).

Here's the code:

program convolve_random_arrays
   use iso_fortran_env
   implicit none
   integer(int64), parameter :: a1 = 1103515245
   integer(int64), parameter :: c1 = 12345
   integer(int64), parameter :: m1 = 2147483648
   real, parameter ::    mi = 4.656612873e-10 ! 1/m1
   integer, parameter :: n = 6
   integer :: p, pmax, iters, i, nil(0:1), seed
   !integer, allocatable ::  F(:), S(:), FS(:)
   integer :: F(n), S(n+1), FS(2)

   !n = 6
   !allocate(F(n), S(n+1), FS(2))
   iters = 1000
   nil = 0

   !call init_random_seed()

   S = -1
   pmax = 2**(n+1)
   do p=1,pmax
      do i=1,iters
         F = rand_int_array(n)
         if(all(F==0)) then
            do while(all(F==0))
               F = rand_int_array(n)
            enddo
         endif

         FS = convolve(F,S)

         if(FS(1) == 0) then
            nil(0) = nil(0) + 1
            if(FS(2) == 0) nil(1) = nil(1) + 1
         endif

      enddo
      call permute(S)
   enddo

   print *,"first zero:",nil(0)
   print *," both zero:",nil(1)

 contains
   pure function convolve(x, h) result(y)
!x is the signal array
!h is the noise/impulse array
      integer, dimension(:), intent(in) :: x, h
      integer, dimension(abs(size(x)-size(h))+1) :: y
      integer:: i, j, r
      y(1) = dot_product(x,h(1:n-1))
      y(2) = dot_product(x,h(2:n  ))
   end function convolve

   pure subroutine permute(x)
      integer, intent(inout) :: x(:)
      integer :: i

      do i=1,size(x)
         if(x(i)==-1) then
            x(i) = 1
            return
         endif
         x(i) = -1
      enddo
   end subroutine permute

   function rand_int_array(i) result(x)
     integer, intent(in) :: i
     integer :: x(i), j
     real :: y
     do j=1,i
        y = bsd_rng()
        if(y &lt;= 0.25) then
           x(j) = -1
        else if (y &gt;= 0.75) then
           x(j) = +1
        else
           x(j) = 0
        endif
     enddo
   end function rand_int_array

   function bsd_rng() result(x)
      real :: x
      integer(int64) :: b=3141592653
      b = mod(a1*b + c1, m1)
      x = real(b)*mi
   end function bsd_rng
end program convolve_random_arrays


I suppose the question now is will you stop using slow-as-molasses Python and use fast-as-electrons-can-move Fortran ;).