How can I speed up this two-lines code?

Question

I need to speed up the following code:

for i in range(0, 2**N):

    output[i] = f(np.array(map(int, bin(i)[2:].zfill(N))))

N is around 30, so the code is very slow (it takes about 33 hours on my laptop). The argument of the function f() is the binary representation of the index i, and f() can be an arbitrary vectorizable function. I'm not an expert, but in order to speed up the code, I was thinking to get rid of the for loop, which means that I need to vectorize the argument of f(). In other words, I have to create a matrix with the binary representations of the numbers from 0 to 2**N. This can be achieved through the following code:

list(itertools.product([0, 1], repeat=N))

that I have found at this link. However, it seems to me that itertools is very slow, and clearly it takes a lot of memory since 2**30 is about one billion.

Do you have any suggestion for making this code faster? Thanks in advance.

Answer 1

Always profile:

>>> timeit.timeit("for i in range(0, 2**N): numpy.array(map(int, bin(i)[2:].zfill(N)))", "import numpy; N=5", number=100000)
26.472519159317017
>>> timeit.timeit("for t in itertools.product((0, 1), repeat=N): numpy.array(t)", "import numpy, itertools; N=5", number=100000)
6.129688024520874

You can see that the itertools.product method is considerably faster, since it doesn't has to fiddle around with strings.

The problem could be that most of the time is spent in the f function though.

Another solution could be to make f accept an integer, and use it as a binary field.