5

In Matlab, this type of algorithm ("growing arrays") is advised against

mine = []
for i=1:100,
    mine = [mine,randn(1)]
end

whereas it seems that many examples for Python show this kind of algorithm (this is a really bad example though):

import numpy.random as rand

mine = []
for i in range(100):
    mine.append(rand.random(1)[0])

I wonder why that is -- what is the difference?

hatmatrix
  • 42,883
  • 45
  • 137
  • 231
  • 1
    I don't know the answer to your question, but I would write the second example as `mine = [ rand.random(1)[0] for _ in range(100)] ` – Eric Wilson Oct 13 '11 at 16:55
  • Note that Eric Wilson's example, while much more idiomatic, still does the same thing under the hood (AFAIK, the bytecode is different because there is a special opcode to speed up the "get list object, get object to append, append it, put list back" sequence, but either way it still grows the list by appending to it). –  Oct 13 '11 at 17:08
  • 1
    Of course, I am not implying that this is meant to be the most efficient solution for this particular, silly problem as I think you can just do `rand.random(100).tolist()`, if I'm not mistaken. But I was not aware that internally the list comprehension would be the same. – hatmatrix Oct 13 '11 at 18:58

4 Answers4

7

The difference is that:

  • In MATLAB, every iteration of your loop re-allocates the matrix to increase the size by one and copies the entire contents into the newly allocated space.
  • Python lists don't work like that. More space is allocated than is needed at any given point and this allocated space grows in a manner that guarantees that appends are done in amortized constant time.

That said, I think the difference is largely cultural:

  • It is common to have large numeric matrices in MATLAB, and growing such matrices one element (or one row/column) at a time would indeed be expensive.
  • On the other hand, no one would use a Python list (or a list of lists) to represent a large matrix: that would be very slow and would make very poor use of memory. Numerical Python's ndarray would be used instead, and ndarray would offer exactly the same tradeoffs as a MATLAB matrix.
Glorfindel
  • 21,988
  • 13
  • 81
  • 109
NPE
  • 486,780
  • 108
  • 951
  • 1,012
  • Actually I am growing a list to convert to a NumPy ndarray (the data is not in a regular format amenable for `genfromtxt`)... – hatmatrix Oct 13 '11 at 18:22
  • another thing to note is that the closest equivalent to python lists are cell-arrays in MATLAB. That's because MATLAB matrices require contiguous space in memory with all items of the same type. – Amro Oct 13 '11 at 18:25
  • Right, maybe I should have used that for my example... I've employed them mercilessly, but seems it's not a very widely used data structure in Matlab (as if it only exists for those of us who miss it). – hatmatrix Oct 13 '11 at 19:01
  • @crippledlambda: One useful technique for building `ndarrays` bit by bit is to store chunks (e.g. columns) in a sequence, and then combine them using a single call to `numpy.hstack` or `numpy.vstack`. – NPE Oct 13 '11 at 19:27
  • @crippledlambda: Columns with `hstack`, rows with `vstack`. – NPE Oct 13 '11 at 20:31
4

Appending to arrays in Matlab is apparently very inefficient (it runs in quadratic time), whereas in python the corresponding list operation is much more highly optimized. Appends are O(1) up until the list becomes full - at which point the size of the list is doubled to make more room (which is an O(n) operation). This means appends become increasingly efficient as the list grows longer (the overall efficiency is O(1) amortized). These kinds of optimizations could probably also be achieved in Matlab, but it seems they are not done automatically.

For even better performance, python also has the collections.deque container class which supports efficient appending and removal from either end (it's about O(1) in both directions).

ekhumoro
  • 115,249
  • 20
  • 229
  • 336
3

Your MATLAB code can be better written. Compare the following implementations:

%# preallocation
tic
x = zeros(1,100000); for i=1:100000, x(i) = 99; end
toc

%# appending
tic
x = []; for i=1:100000, x(end+1) = 99; end
toc

%# concatenation
tic
x = []; for i=1:100000, x = [x, 99]; end
toc

I get the following results:

Elapsed time is  0.001844 seconds.    %# preallocated vector/matrix
Elapsed time is  0.109597 seconds.    %# appending using "end+1" syntax
Elapsed time is 35.226361 seconds.    %# appending using concatenation

Note that the above was tested on R2011b, which introduced improvements on growing matrices (without pre-allocation).

You should also check this previous answer for a solution that combines preallocation while still allowing for dynamic growing (idea is to allocate/grow in large block sizes)

On the other side, you should note that Python lists are optimized for appending items at the end. If you insert items at the beginning, you will get very different timings. Example:

>>> from timeit import timeit

>>> timeit('x.insert(0,99)', 'x=[]', number=100000)
5.3840245059078597

>>> timeit('x.append(99)', 'x=[]', number=100000)    # x.insert(len(x),99)
0.039047700196533697
Community
  • 1
  • 1
Amro
  • 123,847
  • 25
  • 243
  • 454
  • Yes, for certain the example was not meant to imply that these are the best ways to do this same operation in both languages -- only an illustration. The difference between insert and append is interesting though. – hatmatrix Oct 13 '11 at 18:20
2

Your two examples are not exactly equivalent. The Matlab example is concatenating two lists into a new list, making a copy each time, whereas the Python is appending items to a list without making a copy of it every time. Now you can in fact write an exact Python equivalent of the Matlab code, e.g.:

mine = mine + [newitem]

But you shouldn't do that, because you're making a copy of an ever-growing list each time. Which is why lists have an .append() method (also .extend()).

For similar reasons, rather than building up a string by concatenation, Pythonistas recommend you append the individual strings to a list then use ``.join() on it.

By the way, Python lists are always allocated with space for extra items, so that they do not always need to be grown when a new item is appended.

kindall
  • 178,883
  • 35
  • 278
  • 309