创建一个非常大的二维数组而不会对 Python 中的代码运行时间产生重大影响

Question

现在我已经做了几个月的竞争性编程（USACO），其中有你不能超过的时间限制。我需要创建一个大矩阵或二维数组，尺寸为 2500x2500，其中每个值为 [0,0]。使用列表理解会花费太多时间，我需要一个替代方案（你不能导入模块，所以 numpy 不是一个选项）。我最初是这样做的：

grid = [[[0,0] for i in range(2500)] for i in range(2500)]

但这花费了太多时间，所以我尝试了：

 grid= [[[0,0]]*2500]*2500

,

最初给出相同的结果，但每当我尝试更改值时，例如：

grid[50][120][0]= 1

，它将整个矩阵中每个 [0,0] 的第 0 个索引位置更改为 False，而不是 [50][120] 位置的特定坐标，而当我使用列表理解时情况并非如此.有人知道这里发生了什么吗？还有任何不涉及疯狂运行时间的解决方案吗？我在竞争性编程前几个月才开始使用 Python，所以我不是很有经验。

Answer 1

grid = [[[0,0] for i in range(2500)] for i in range(2500)]

在我的 PC 上大约需要 2.1 秒，与 PowerShell 的

Measure-Command

同步。现在如果数据规范很严格，没有什么神奇的方法可以让它更快。但是，如果目标是使这种表示更快地生成，则有一个更好的解决方案：使用元组而不是列表作为内部数据 (0, 0)。

grid = [[(0, 0) for i in range(2500)] for i in range(2500)]

此片段在不到四分之一的时间内（0.48 秒）生成相同的信息值。现在你必须考虑的是接下来会发生什么。在网格中更新这些值时，您需要始终创建一个新元组来替换旧元组——这总是比仅更新原始示例代码中的列表值要慢。这是因为元组不支持项目分配操作。替换单个值仍然像

grid[50][120] = (1, grid[50][120][1])

一样简单。

快速生成 - 缓慢替换，如果没有大量的值变化，可能会很方便。希望这会有所帮助。

Answer 2

内置的

memoryview

对象似乎是标准库中唯一类似于nd-array的东西，它的

tolist

方法可以提供一些加速：

In [_]: %timeit [[[0, 0] for i in range(2500)] for i in range(2500)]
477 ms ± 7.91 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [_]: %timeit memoryview(b'\x00' * (2500 * 2500 * 2)).cast('B', (2500, 2500, 2)).tolist()
375 ms ± 11.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

这和NumPy的速度差不多：

In [_]: %timeit np.zeros((2500, 2500, 2), int).tolist()
371 ms ± 11.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

如果

list

不是唯一的选择，那么简单地构建一个

memoryview

应该是最好的解决方案。请注意，需要使用

bytearray

来使其可写：

In [_]: %timeit memoryview(bytearray(b'\x00') * (2500 * 2500 * 2 * 4)).cast('i', (2500, 2500, 2))
9.71 ms ± 488 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

>>> mem = memoryview(bytearray(b'\x00') * (2500 * 2500 * 2 * 4)).cast('i', (2500, 2500, 2))
>>> mem[0, 0, 0]
0
>>> mem[0, 0, 0] = 1
>>> mem[0, 0, 0]
1