This is a follow up to How slow is Python really? (Or how fast is your language?).
It turns out it was a bit too easy to get a x100 speedup for my last question. For those who have enjoyed the challenge but want something harder where they can really use their low level skills, here is part II. The challenge is to get a x100 speedup for the following python code as tested on my computer.
To make it more difficult I am using pypy this time. The current timing for me is 1 minute and 7 seconds using pypy 2.2.1.
- The first person to submit code which I can run, is correct and is x100 times faster on my machine will be awarded a bounty of 50 points.
- I will award the win to the fastest code after a week.
import itertools import operator import random n = 8 m = 8 iters = 1000 # creates an array of 0s with length m # [0, 0, 0, 0, 0, 0, 0, 0] leadingzerocounts = *m # itertools.product creates an array of all possible combinations of the # args passed to it. # # Ex: # itertools.product("ABCD", "xy") --> Ax Ay Bx By Cx Cy Dx Dy # itertools.product("AB", repeat=5) --> [ # ('A', 'A', 'A', 'A', 'A'), # ('A', 'A', 'A', 'A', 'B'), # ('A', 'A', 'A', 'B', 'A'), # ('A', 'A', 'A', 'B', 'B'), # etc. # ] for S in itertools.product([-1,1], repeat = n+m-1): for i in xrange(iters): F = [random.choice([-1,0,0,1]) for j in xrange(n)] # if the array is made up of only zeros keep recreating it until # there is at least one nonzero value. while not any(F): F = [random.choice([-1,0,0,1]) for j in xrange(n)] j = 0 while (j < m and sum(map(operator.mul, F, S[j:j+n])) == 0): leadingzerocounts[j] +=1 j += 1 print leadingzerocounts
The output should be similar to
[6335185, 2526840, 1041967, 439735, 193391, 87083, 40635, 19694]
You must use a random seed in your code and any random number generator that is good enough to give answers close to the above will be accepted.
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.
Explanation of code
This code iterates over all arrays S of length n+m-1 that are made up for -1s and 1s. For each array S it samples 1000 non-zero random arrays F of length n made up of -1,0 or 1 with probability of 1/4, 1/2,/14 of taking each values. It then computes the inner products between F and each window of S of length n until it finds a non-zero inner product. It adds 1 to
leadingzerocounts at each position it found a zero inner product.
Perl. 2.7 times slowdown by @tobyink. (Compared to pypy not cpython.)
J. 39 times speedup by @Eelvex.
- C. 59 times speed up by @ace.
- Julia. 197 times faster not including start up time by @one-more-minute. 8.5 times speed up including start up time (it's faster using 4 processors in this case than 8).
- Fortran. 438 times speed up by @semi-extrinsic.
- Rpython. 258 times speed up by @primo.
- C++. 508 times speed up by @ilmale.
(I stopped timing the new improvements because they are too fast and iters was too small.)
It was pointed out that timings below a second are unreliable and also some languages have a start-up cost. The argument is that if you are to include that you should also include the compilation time of C/C++ etc. Here are the timings for the fastest code with the number of iterations increased to 100,000.
- Julia. 42 seconds by @one-more-minute.
- C++. 14 seconds by @GuySirton.
- Fortran. 14s by @semi-extrinsic.
- C++. 12s by @ilmale.
- Rpython. 18s by @primo.
- C++. 5s by @Stefan.
The winner is.. Stefan!
Follow-up challenge posted. How high can you go? (A coding+algorithms challenge) . This one is harder.