0
\$\begingroup\$

Recently I noticed that the idiomatic python two-dimensional array initialisation is extremely slow. I am wondering, is there a good, proper way of doing this simple task fast? Also, are those two variants equivalent?

Here are some code snippets using timeit

import timeit

A = 5000
B = 7000

N = 10

def list_comprehension_xrange():
    matrix = [[0 for j in xrange(A)] for i in xrange(B)]
def list_comprehension_range():
    matrix = [[0 for j in range(A)] for i in range(B)]
def multiplication():
    matrix = [[0] * A] * B

print "list_comprehension_xrange:", timeit.timeit(list_comprehension_xrange, number=N)
print "list_comprehension_range:", timeit.timeit(list_comprehension_range, number=N)
print "multiplication:", timeit.timeit(multiplication, number=N)
list_comprehension_xrange: 11.4952278137
list_comprehension_range: 13.5112810135
multiplication: 0.00100612640381
\$\endgroup\$
  • \$\begingroup\$ I'm afraid this question does not match what this site is about. Code Review is about improving existing, working code. The example code that you have posted is not reviewable in this form because it leaves us guessing at the code you intend to do. I think this would fit better on Stack Overflow as a question about Python practices, assuming of course that there isn't a question about this on there already. \$\endgroup\$ – SuperBiasedMan May 4 '16 at 9:52
  • 3
    \$\begingroup\$ Your multiplication case creates an outer list filled with 7000 references to a single list of 5000 items, rather than 7000 lists of 5000 items each, so its unsurprising that it is 3-4 orders of magnitude faster. \$\endgroup\$ – Jaime May 4 '16 at 10:00
  • \$\begingroup\$ @SuperBiasedMan this question was spawned as a follow up on today's codereview.stackexchange.com/questions/127448/…. That is why it is here and not on SO \$\endgroup\$ – vegi May 4 '16 at 14:13
  • 1
    \$\begingroup\$ I have rolled back the last edit. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Vogel612 May 5 '16 at 10:02
3
\$\begingroup\$

First off don't use multiplication. It's creates 2 lists, not 7001.

To better show this, hop into IDLE:

>>> a = [[0] * 3] * 3
>>> a
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
>>> a[0][0] = 1
>>> a
[[1, 0, 0], [1, 0, 0], [1, 0, 0]]

No this is not what you want.


In both your other functions you should use _, this is a convention that says you don't use the result, it's thrown away.

This results in:

def list_comprehension_xrange():
    matrix = [[0 for _ in xrange(A)] for _ in xrange(B)]

If speed is highly important, then you can use a hybrid of multiplication and range or xrange. From the benchmarks I'd lean towards xrange, but I don't think there is too much difference.

I can't say exactly why these are so fast, it may be because the multiplication doesn't build and destroy an intermarry list. Or it's not creating a list in Python code but in C. Or it's not building ~A*B amount of objects only ~B amount. But I don't.

I added the following functions, with timers:

def multiplication_range():
    matrix = [[0] * A for _ in range(B)]
def multiplication_xrange():
    matrix = [[0] * A for _ in xrange(B)]

And got the following results:

list_comprehension_xrange: 23.0122457496
list_comprehension_range: 24.9418833563
multiplication: 0.00104575910762
multiplication_range: 3.35667382897
multiplication_xrange: 3.35528033683
\$\endgroup\$
2
\$\begingroup\$

Now that you are asking about speed from 2+ dimensional arrays you are now out of standard python land and in to lower level array territory. Numpy and Pandas are libraries that you need to become familiar with for this task.

Do not plan on using "for" statements with these libraries. (they work but you will lose speed)

  • Numpy creates an array of some data type

  • Pandas is like having R or a spreadsheet in Python.

Since your numbers are all integers I'll pick Numpy.

import numpy as np
a = 5000
b = 7000

%timeit np.zeroes((a,b))

100000 loops, best of 3: 2.41 µs per loop

and this works with python 2 and 3.

As for matrix multiplication you can multiply 2 arrays or multiply and array * scalars.

a = np.ones((a,b))
b = 5
%timeit a*b

10 loops, best of 3: 148 ms per loop

You had a example of 1's in an axis and that can be done like this with numpy

b = 7000
c = np.zeros((a,b))    
c[:,0] = 1

array([[ 1.,  0.,  0.,  0.,  0.,  0.,...
   [ 1.,  0.,  0.,  0.,  0.,  0., ,,,
   ....
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.