入坑记

25 Nov 2014

程序员们经常用「入坑了」来描述自己选择了某种技术作为未来发展的情景,特别是在面对几种选择摇摆不定多时之后。这种略带诙谐的说法一方面是在自我解嘲,仿佛马上就要过上水深火热的生活,不过更多的还是在表达对对该技术的肯定和自己的决心。就在不久前,我选择了入 Python 的坑,而且此后的每一天都为这个选择由衷高兴。不过今天我要说的不是这个,而是在学习和使用 Python 过程中遇到的一个实实在在的坑,关于二维列表的初始化。

当时需要定义一个函数来计算两个 3x3 矩阵的乘积,实现如下:

def multiplyMatrix(matrix1, matrix2):
	# bad initialization
	resultMatrix = len(matrix1) * [len(matrix2[0]) * [0]]

	for i in range(len(matrix1)):
		for j in range(len(matrix2[0])):
			for k in range(len(matrix2)):
				resultMatrix[i][j] += matrix1[i][k] * matrix2[k][j]

	return resultMatrix

我自以为以上初始化 resultMatrix 列表的方法简洁易读。可是计算结果是错误的:

The multiplication of the matrices is:
  1   2   3       9   8   7     252 207 162 
  4   5   6  *    6   5   4  =  252 207 162 
  7   8   9       3   2   1     252 207 162 

问题不是出在算法上,而是因为这里的二维列表初始化是错误的,对新手来说,这的确是一个坑。正确的初始化方法是这样的(其一):

resultMatrix = [len(matrix2[0]) * [0] for row in range(len(matrix1))]

那么应该怎么来认识这个坑以防止再次掉入进去?

一切皆是对象和引用

对比一下这两种初始化方式,都是先用 [0] * n 的方式初始化了一个一维列表,而后,前者继续用这种方式初始化二维列表;不同的是,后者这时选择用列表推导式的方式初始化二维列表。那么第一种方式为什么不对,而列表推导式又有什么不同?

为简明起见,以下直接用 3 来代替上述的 len(matrix1)len(matrix2[0])。即初始化一个 3x3 的二维列表:

(bad)  resultMatrix = 3 * [3 * [0]]
(good) resultMatrix = [3 * [0] for row in range(3)]

我们先来看看 3 * [0] 做了什么,很简单,它生成了 [0, 0, 0] 。那么紧接着,3 * [[0, 0, 0]] 呢,不就是生成了 [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 吗?多么完美的初始化,能有什么错呢?是的,虽然看似完美,不过如果深究下去,却大有文章。

那么说到这里,就必须先明确一个概念,在 Python 中,一切数据(data)都是对象(object),一个整数是一个对象,一个字符串也是一个对象,你可以把这些对象想象成在内存中实打实的存在的物件,它们持有数据。而变量,只是指向这些物件的引用(reference)。更进一步,不只是变量,我们可以在程序中直接使用的比如数字,叫做字面表示(literal)的东西,也只是指向某种类型的对象的标识。举例来说,[0], [0, 0, 0]3 都是相对应类型对象的字面表示。这里简单总结一下,Python 里一切数据都是对象,我们可以用变量或者字面表示来引用这些对象。

复制引用

我们再来看 3 * [0],表面上看它是生成了 [0, 0, 0],而本质上,它是将 0 这个引用复制了三份放在列表里,也就是说,列表里的这三个 0 指向同一个整型对象。同样地,3* [[0, 0, 0]],看似是生成了[[0, 0, 0], [0, 0, 0], [0, 0, 0]],而本质是,它将[0, 0, 0] 这个引用复制了三份放在了二维列表里,因此,二维列表里的三个一维列表指向的是同一个列表对象。

而前面给出的正确的初始化方法,也是先用3 * [0]初始化了一个一维列表,不过在第二维的初始化时使用了列表推导式的方式。它有什么不同呢?

列表推导式

我们必须要知道列表推导式做了什么。根据定义,列表推导式会最终生成一个列表,每次 for 循环中计算前面的表达式所得来的结果就会生成一个元素。那么这里,

resultMatrix = [3 * [0] for row in range(3)]

会循环三次,表达式是 3 * [0],每次循环都会计算一次该表达式,并将其计算结果作为一个元素放置在最终列表里。需要谨记的是,这里生成的三个元素看似相同,都是 [0, 0, 0],不过它们各自指向相互独立的列表对象,互不关联,因为每次计算这里的表达式都就会生成一个新的对象。

问题所在

在此,还是先总结一下两种初始化本质上的不同。首先,一维列表的初始化没什么不同;不同的是初始化二维列表时,前者生成的的三个一维列表引用的是同一个列表对象,而后者生成的三个一维列表引用的是互不关联的三个列表对象。

如果二维列表里的一维列表指向的是同一个列表对象,那么当你改动其中一个列表的时候,另外两个也同时跟着改动。或者毋宁说,你输出它们的时候,其实输出的是同一个列表。举例来说:

>>> a = [1, 2]
>>> b = 3 * [a] # 复制引用
>>> b
>>> [[1, 2], [1, 2], [1, 2]]
>>> a.append(3)
>>> a
>>> [1, 2, 3]
>>> b
>>> [[1, 2, 3], [1, 2, 3], [1, 2, 3]]
>>> b[0].append(4)
>>> b
>>> [[1, 2, 3, 4], [1, 2, 3, 4], [1, 2, 3, 4]]
>>> a
>>> [1, 2, 3, 4]

这时候你会发现,上面错误的计算输出,

The multiplication of the matrices is:
  1   2   3       9   8   7     252 207 162 
  4   5   6  *    6   5   4  =  252 207 162 
  7   8   9       3   2   1     252 207 162 

存放计算结果的二维列表 resultMatrix 的输出结果,每一行有着相同的内容,就是因为三个一维列表引用的其实是同一个列表对象,输出内容当然会相同了。

而我们用列表推导式初始化的二维列表,其中的一维列表互不干扰,因此就能得到正却的结果:

The multiplication of the matrices is:
  1   2   3       9   8   7      30  24  18 
  4   5   6  *    6   5   4  =   84  69  54 
  7   8   9       3   2   1     138 114  90 

列表推导式是万能的?

初始化二维列表时,只要用列表推导式就没问题吗?这可不一定。

考虑这种方式来初始化 resultMatrix

lst = 3 * [0]
resultMatrix = [lst for row in range(3)]

我们这里将列表推导式内的表达式由 3 * [0] 换成了 lst,结果如何?不好意思,这样是错误的。不需再多作解释。

因此不仅仅要看是不是列表推导式,更重要的是能分辨二维列表中的一维列表是不是各自引用着互不关联的对象。如果是,没有问题;如果不是,那么初始化可能就不是你想要的。

再深入,可变对象与不可变对象

如果到这里你还没看晕,那么再来解决最后一个问题,也需你也已经注意到了:为什么一维列表的初始化可以用 [0] * n 的方式?

这就涉及到了 Python 中的另一个重要概念,可变对象(mutable object)与不可变对象(immutable object)。如前所述,Python 中的一切数据都是对象,但是有些对象一旦建立,它的内容就不可更改,比如整型对象,字符串对象等;还有一些对象,在建立以后它的内容是可以更改的,比如列表,还有你自己定义的对象等。

还是来看 3 * [0] 或者 [0, 0, 0]。虽然列表中三个元素引用同一个整型对象 0,但是当你更改此处列表中某个元素的值的时候,其它元素不会跟着改变,比如:

>>> a = 3 * [0] # 复制引用
>>> a[0] = 1
>>> a
[1, 0, 0]

这是因为该一维列表中元素所引用的整型对象是不可变对象,当你改变其中一个元素的值,比如操作 a[0] = 1 时,a[0] 所指向的整型对象并不能改变,那么这个时候只能新建一个整型对象 1,并另 a[0]离开指向原来的整型对象 0 并指向这个新的整型对象。因此此处列表元素间值的更改是互不干扰的。

而二维列表里,如果一维列表指向的是同一个列表对象,因为列表对象是可变对象,它可以就地发生内容的更改,那么一旦其中一个一维列表发生了更改,其它的一维列表仍然引用着这个更改了的列表对象,自然也都跟着改变了。

另外,理解 Python 中的可变对象与不可变对象的概念,对于理解函数的传参问题上也是大有帮助。

作为一种语法糖,[0] * n 的初始化方式只能用于一维列表(且元素为不可变对象),而不适合二维列表,这真是一个不小的坑。因此,不论是初始化一维列表还是二维列表,这里都推荐使用列表推导式的方式:

resultMatrix = [[0 for col in range(3)] for row in range(3)]