Two-dimensional arrays

[Michael Chermside]

Peter Slizik writes:
> I'm really thankful for this solution:
>  > You might use:
>  >
>  >   array = [[0]*dim for row in range(dim)]
> which is the one I really wouldn't think about;
> and I'm also thankful for directing my attention to the Python FAQ, 
> which is, I think, the only website on Python I didn't read. ;-)
> 
> But I want to ask: When does Python merge two same objects into one and 
> when does it treat as two different objects? Is there any general rule?

An excellent question. Yes, there IS a general rule, but you're also
operating under a bit of a misconception. The general rule is that
Python *never* merges two same objects into one. But now that I've
said that, I need to go back to what you originally wrote and explain
it to you more clearly.

You wrote this:
  >>> array = [[0]*dim]*dim
A really good way to think about this is to break it up into two lines.
The two-line version would read something like this:
  >>> aList = [0]*dim
  >>> array = [aList]*dim

In the second line there, you say that the list 'array' should be made
up of dim copies of the list 'aList'. What you originally thought was
a case of Python merging same objects into one, turns out to be you
explicitly instructing Python to use many copies of the same list.

But if you're paying attention very carefully, you'll notice something
odd going on here. After all, the only thing that you did was to
duplicate the same idiom "[x]*dim" that had worked for the one-dimentional
array. Why would it re-use the same object when used to make the ONE
dimentional array TWO dimentional, but not do the same when you made the
ONE dimentional array in the first place?

The answer is subtle and tricky. Let's experiment here.
  >>> aList = [0]*3
  >>> id(aList[0])
  7627524
  >>> id(aList[1])
  7627524
  >>> id(aList[2])
  7627524

The id() function is one which tests object identity -- a given object
will always return the same value for id(), and it's unique across all
live objects. (Your value for id() may differ from mine, but it'll still
be the same for all 3 slots.)

It appears that when you write "[0]*dim", you get dim copies of *THE
SAME OBJECT*.

In C, this would be a disaster... as soon as you changed one object
all of the values in the array would change. But in Python, some
objects (like numbers) are immutable. That means that they can't be
changed. If you now do this:

  >>> aList[1] = 3
  >>> print aList
  [0, 3, 0]

you DIDN'T "change the object in slot 1 of the array" (if that were
true, you'd have changed the number 0 itself!). Instead, you have
"changed which object is in slot 1".

If you were to do this instead:
  >>> aList[1].setValueOfThisNumberToThree()
Then you WOULD see all of the numbers in the list change at once...
but you can't call that method because it doesn't exist. In fact,
the designers of Python have carefully made sure that there are NO
methods of number objects that change the object. Any object like
this which is impossible to change is said to be an "immutable"
object. Because 0 is an immutable object, you could write this:
  >>> aList = [0]*dim
and not really care that you got the same object appearing
everywhere.

But list objects are *not* immutable... there are lots of ways to
change a list object (and you _want_ to be able to make these changes
anyhow). So writing
  >>> array = [aList]*dim
won't do, because it re-uses the same list, and that list isn't
immutable. The REAL problem here is that the idiom "[x]*dim" re-uses
the SAME object, which is not what you wanted.

That's where the list comprehension comes in. Saying "[x]*dim" is
a very simple idiom, that says to repeat the same exact object
multiple times. But the list comprehension idiom gives an expression
and it *evaluates* the expression multiple times. That means that if
the expression gives us a new thing (new number, new list, whatever)
then we'll have different objects in the list. When you write this:
  >>> array = [[0]*dim for x in range(dim)]
it's equivalent to the following two-line code:

  >>> def makeAList():
  ...     return [0]*dim
  ...
  >>> array = [makeAList() for x in range(3)]

which makes a DIFFERENT list for each row of array. If you wanted
to initialize a whole array to DIFFERENT number objects, you could
do something like this:

  >>> array = [[100+3 for x in range(3)] for x in range(3)]

The only trick here is that I initialized them to 103 instead of
initializing them to 0. That's because Python *DOES* get clever with
us when we use numbers. Since it knows that numbers are immutable
it sometimes re-uses an existing number even when we don't tell it
to... just Python's way of saving some memory.

Hope this more detailed explanation helps some.

-- Michael Chermside