python二维列表，为什么内存不连续？

Question

path = [[0, 1, 0, 0], 
       [0, 0, 1, 1], 
       [0, 0, 0, 1], 
       [1, 0, 0, 0]]
print [hex(id(path[0])),hex(id(path[1])), hex(id(path[2]))], id(path[1])-id(path[0]),id(path[2]) -id(path[1])
path[1] = [0,0, 0, 0]
print path
print [hex(id(path[0])),hex(id(path[1])), hex(id(path[2]))], id(path[1])-id(path[0]),id(path[2]) -id(path[1])

这是 python 2.7，CPython。结果示例：

['0x107d05638', '0x107cefb90', '0x107cef7e8'] -88744 -936

[[0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0]]

['0x107d05638', '0x107cef8c0', '0x107cef7e8'] -89464 -216

谢谢。

Answer 1

Python 对象的所有内存都在私有堆中进行管理。 2D 列表是一种数据结构和 Python 对象的示例（因为从原始类型到 class 类型的所有内容都被认为是 Python 中的 'object'）。

管理私有堆的 Python 内存管理器决定如何根据与二维数组类型相关的不同内存管理策略为二维数组对象分配内存。显然，在这种情况下，确保连续分配整个数组的内存是不利的（可能出于性能或开销原因）。

这说明了高级语言不需要指针数学运算的想法。在 C 中，A[x][y] 的简单公式用于检索存储的值，但在 Python 中，我们可以变得更复杂。

Answer 2

首先，一些重要的注意事项。

id(..)不一定指对象的地址。确实 documentation says:

id(object)

Return the "identity" of an object. This is an integer which is guaranteed to be unique and constant for this object during its lifetime. Two objects with non-overlapping lifetimes may have the same id() value.

CPython implementation detail: This is the address of the object in memory.

所以只有在CPython中才能保证是这样

在Python中没有二维列表这样的东西。 Python 只有非常有限的基本数据结构：集合、字典、整数、字符串、列表……但是没有二维列表。二维列表是列表的列表。这可能看起来像一个细节，但您可以例如声明：[[1,0,1],2,'foobar']。所以这只是部分二维列表。 Python 只是看到一个列表，其中一个元素碰巧是一个列表。

这是什么意思？在你的问题中，列表如下所示：

+---------------+
|      list     |
+---+---+---+---+
| o | o | o | o |
+-|-+-|-+-|-+-|-+
  |   |   |   \________________________________________________
  |   |   \________________________________                    \
  |   \______________                      \                    |
  |                  \                      |                   |
+-v-------------+  +--v------------+  +-----v---------+  +------v--------+
|      list     |  |      list     |  |      list     |  |      list     |
+---+---+---+---+  +---+---+---+---+  +---+---+---+---+  +---+---+---+---+
| o | o | o | o |  | o | o | o | o |  | o | o | o | o |  | o | o | o | o |
+-|-+---+---+---+  +-|-+-|-+-|-+-|-+  +-|-+-|-+-|-+-|-+  +-|-+-|-+-|-+-|-+
  v   v   v   v      v   v   v   v      v   v   v   v      v   v   v   v
  0   1   0   0      0   0   1   1      0   0   0   1      1   0   0   0

顺便说一下，0 和 1 也是对象，但它们是对同一对象的引用。

通常解释器使用堆并在堆上分配。现在堆可以被碎片化，因为早期的对象已经在堆上分配和释放。因此，解释器旨在找到一个 hole 可以容纳要分配的对象。

列表可以共享子列表。例如：

a = [1,0] b = [[0,0],a,[0,1],[0,0]] c = [a]

现在 b 和 c 都有一个引用对象 a 的元素。所以不能使 b 和 c 连续。

如果你执行：

path[1] = [0,0, 0, 0]

你基本上首先构建一个新列表[0,0,0,0]。由于旧列表 path[1] 仍在内存中 ，因此无法填补该空缺。因此 Python 解释器将不得不找到另一个地方来定位 [0,0,0,0]。然后它设置从 path[1] 到该列表的引用，最后（通常在更新引用计数之后），它将删除 path[1] 的旧列表（这也可以延迟到内存应该被释放）从而将曾经被占用的地方标记为空置。

这些注释基本上回答了这个问题：没有 2d 列表：所有对象都分配在堆上，因为很多 allocation/deallocation 发生（例如甚至在启动和加载库时）。对象将被分配到哪里是不确定的。由于可以共享一个对象，因此所有列表的内存布局不能同时连续。

最后请注意，Python通常假设程序员方便比效率更重要。 Python 相当低效：它是动态类型的，具有（例如通过使用 MRO）解析动态绑定的低效方式，通常有很多 fallback 机制也花费了计算量。在python-3.x中他们还引入了任意长度的整数等。这些特性都给CPU带来了相当大的负担，但是Python的理念通常是程序员的方便优先于CPU 效率，因为支付额外的程序员费用通常比购买两台新服务器的成本更高。

python二维列表，为什么内存不连续？

python 2D list, why is the memory not contiguous?

python

memory

list

memory-efficient

contiguous