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: 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.
- 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)?