Python 3.x：哪个更高效：列表嵌套列表还是字典？

Question

假设您正在网格上执行BFS（例如两个单元格之间的最短距离）。两种数据结构可用于存储visited信息：

1）列表的列表，即data = [[False for _ in range(cols)] for _ in range(rows)]。稍后，我们可以通过data[r][c]访问某个单元格中的数据。

2）字典，即data = dict()。稍后，我们可以通过data[(r, c)]访问某个单元格中的数据。

我的问题是：在这种BFS场景中，哪种计算效率更高？

从编码角度来看，字典方法似乎可以节省更多的字符/行数。从内存方面来看，字典方法可能可以为未使用的单元格节省一些空间，但也可能浪费一些哈希表的额外空间。

编辑

@Peteris提到了numpy数组。与列表的列表相比，其优势显而易见：numpy数组操作连续内存块，从而实现更快的寻址和更多的缓存命中。但是我不确定它们与哈希表（即dict）相比如何。如果算法涉及的元素数量相对较小，则哈希表可能提供更多缓存命中率，因为它具有潜在的较小内存占用。

此外，事实是对我来说不可用numpy数组。因此，我确实需要将列表的列表与字典进行比较。

- Roy

---

您的数据大小是否会在任何时候增加/缩小，还是数据大小将保持不变？ - Onyambu

Answer 1

一个二维数组

存储二维数据的高效方法是将二维数组/矩阵分配到连续的内存区域中（而不是像列表一样）。这避免了需要多次内存查找，以及在每次查找时需要计算哈希值的字典。

在Python中标准的方法是使用numpy库，以下是一个简单的示例：

import numpy as np
data = np.zeros( (100, 200) ) # create a 100x200 array and initialize it with zeroes
data[10,20] = 1  # set element at coordinates 10,20 to 1

- Peteris

---

谢谢Peteris。我知道numpy数组。但它不是我可用的选项之一，因此我只询问本地数据结构。我想我欠大家这个背景，我会把它加入到我的问题中。 - Roy

此外，我并不清楚numpy数组是否总是比哈希表更快，因为哈希表的占用空间可能会更小，具体取决于BFS过程中所涉及元素的数量，这可能会导致更多的缓存命中。 - Roy