How to allocate array size in Python

Question

Python newbie here. I've searched quite a bit for a solution to this but nothing quite fits what I need. I would like to allocate an empty array at the start of my program that has a rows and b columns. I came up with a solution but encountered an interesting problem that I didn't expect. Here's what I had:

a = 7
b = 5
array_ab = [['?'] * b] * a

which produces

[['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?']]

However, if I try to change a single element, it treats every row as the same object and effectively changes the entire column to that element. So for example

array_ab[4][2] = '1'

produces

[['?', '?', '1', '?', '?'],
 ['?', '?', '1', '?', '?'],
 ['?', '?', '1', '?', '?'],
 ['?', '?', '1', '?', '?'],
 ['?', '?', '1', '?', '?'],
 ['?', '?', '1', '?', '?'],
 ['?', '?', '1', '?', '?']]

Clearly I need a better way to create the blank array than by multiplication. Is there a solution to this in python? (It was so simple in FORTRAN!)

You might want to check out `numpy`. It's a module that deals a lot with arrays. — kylieCatt, Feb 05 '14 at 15:20
It doesn't *treat* every row as the same object, every row *is* the same object; multiplication has just created many references to that object. You don't usually need to allocate a list in Python in advance, they grow as you append items to them. So your approach to the underlying problem may not be ideal - what exactly are you planning to do? — Tim Pietzcker, Feb 05 '14 at 15:25
Tim, thanks for the clarification! I am writing a text adventure and wanted to create a little "minimap" grid that starts blank but fills in as you move, changing the '?' to '1'. — JohannesKepler, Feb 05 '14 at 15:35
@JohannesKepler: OK, in that case Shurane's answer is indeed the best way to go about this. — Tim Pietzcker, Feb 06 '14 at 06:19

score 7 · Accepted Answer · answered Feb 05 '14 at 15:19

Something along the lines of

In [12]: a = 5

In [13]: b = 7

In [14]: array_ab = [ [ '?' for i in xrange(a) ] for j in xrange(b) ]

In [15]: array_ab
Out[15]:
[['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?']]

In [16]: array_ab[4][2] = '1'

In [17]: array_ab
Out[17]:
[['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '1', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?']]

In particular, you're using list comprehensions and xrange.

zhangxaochen · Answer 2 · 2014-02-05T15:57:49.033

Use list comprehension [['?'] * b for _ in range(a)]:

In [1405]: a = 7
      ...: b = 5
      ...: array_ab = [['?'] * b for _ in range(a)]

In [1406]: array_ab
Out[1406]: 
[['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?']]

In [1407]: array_ab[4][2] = '1'

In [1408]: array_ab
Out[1408]: 
[['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '1', '?', '?'],
 ['?', '?', '?', '?', '?'],
 ['?', '?', '?', '?', '?']]

['?']*b is safe, because '?' is an immutable string, changing elements of a list of string does not affect the others:

In [1419]: a=['a']*5

In [1420]: a[2]=123

In [1421]: a
Out[1421]: ['a', 'a', 123, 'a', 'a']

while [[1,2]]*3 is dangerous, because list is mutable, this equals:

In [1427]: b=[1,2]
      ...: a=[b,b,b] #a is just a list of b's references
      ...: print a
[[1, 2], [1, 2], [1, 2]]

changing elements of the inner list b does not affect the contents of a.

Shouldn't you still get mirroring with the array multiplication? — Ehtesh Choudhury, Feb 05 '14 at 15:22
@Shurane, no, because ['?']*b makes a list of immutable strings — zhangxaochen, Feb 05 '14 at 15:25

score 4 · Answer 3 · answered Feb 05 '14 at 15:24

4

If you are going to use your array for numerical computations, and can live with importing an external library, then I would suggest looking at numpy. It provides an array class and lots of useful array operations.

Creating an MxN array is simply

import numpy as np

A = np.empty((M,N)) # Empty array
B = np.zeros((M,N)) # Array filled with zeros

Indexing is then done like

x = A[i,j]
A[4,2] = 1

row1 = A[0, :] # or simply A[0]

answered Feb 05 '14 at 15:24

Hannes Ovrén

21,229
9
65
75

2

+1 on `numpy` for anything computationally expensive. – Ehtesh Choudhury Feb 05 '14 at 15:25
1

If you know the type of the array you can do even np.empty((M,N),dtype='int') and so on... – ntg Dec 14 '14 at 21:04
He is using string arrays: how do non numeric data types play with numpy? What about arbitrary data types? – WestCoastProjects Oct 29 '21 at 00:46

James Sapam · Answer 4 · 2014-02-05T15:45:48.027

The problem is here:

array_ab = [['?'] * 4] * 3

The problem is caused by the fact that python chooses to pass lists around by object reference. Because list is mutable object.

But since lists might get pretty large, rather than shifting the whole list around memory, Python chooses to just use a reference ('pointer' in C terms). If you assign one to another variable, you assign just the reference to it. This means that you can have two variables pointing to the same list in memory:

>>> a = [1]
>>> b = a
>>> a[0] = 2
>>> print b
[2]

So, in your first line of code you have ['?'] * 4.

Now ['?'] is a pointer to the value ? in memory, and when you multiply it, you get 4 pointers to the same place in memory.

BUT when you change one of the values then Python knows that the pointer needs to change to point to the new value:

>>> a = 4 * ['?']
>>> a
['?', '?', '?', '?']]

You can verify the id of the element inside the list:

>>> [id(v) for v in a]
[33302480, 33302480, 33302480, 33302480]
>>> a[0] = 1
>>> a
[1, '?', '?', '?']

The problem comes when you multiply this list - you get four copies of the list pointer. Now when you change one of the values in one list, all four change together.

The suggested approach is to create a list of the desired length first and then fill in each element with a newly created list:

>>> A = [None] * 3
>>> for i in range(3):
...     A[i] = [None] * 4
...
>>> A
[[None, None, None, None], [None, None, None, None], [None, None, None, None]]
>>>

This generates a list containing 3 different lists of length 4.

Or You can use list comprehension :

w, h = 4, 3
A = [[None] * w for i in range(h)]
[[None, None, None, None], [None, None, None, None], [None, None, None, None]]

Edit 2

Base on your header, you can't allocate a exact memory for list in advanced. Python list is using some kind of algorithm to over allocate the list size for future additional growth.

from the source code:

 /* This over-allocates proportional to the list size, making room
 * for additional growth.  The over-allocation is mild, but is
 * enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
 * system realloc().
 * The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
 */

Very informative, thank you! List comprehension definitely solves my problem best. — JohannesKepler, Feb 05 '14 at 15:47
+1 for mentioning `id()`, that's useful to look at the references of objects. — Ehtesh Choudhury, Feb 06 '14 at 19:19

score 0 · Answer 5 · answered Feb 05 '14 at 16:14

Try this:

a = 7
b = 5
array_ab = []
for i in range(a):
    array_ab.append([])
    for j in range(b):
        array_ab[i].append('?')

This code:

array_ab[4][2] = '1'

Will change array_ab to:

[['?', '?', '?', '?', '?'], 
['?', '?', '?', '?', '?'], 
['?', '?', '?', '?', '?'], 
['?', '?', '?', '?', '?'], 
['?', '?', '1', '?', '?'], 
['?', '?', '?', '?', '?'], 
['?', '?', '?', '?', '?']]

How to allocate array size in Python

5 Answers5