python-3.x - python 3.x : which is more efficient: list of lists vs. 字典？

Question

假设您正在网格上执行 BFS(例如，两个单元格之间的最短距离)。可以使用两种数据结构来承载已访问信息:

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

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

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

在编码方面，似乎 dict 方法可以节省更多字符/行。内存方面，dict 方法可能会为未触及的单元格节省一些空间，但也会为哈希表的额外空间浪费一些空间。

编辑

@Peteris 提到了 numpy 数组。列表列表的优势是显而易见的:numpy 数组在连续的内存块上运行，这允许更快的寻址和更多的缓存命中。但是我不确定它们与哈希表(即 dict)相比如何。如果算法涉及相对较少的元素，哈希表可能会提供更多的缓存命中，因为它可能占用更小的内存。

此外，事实是我无法使用 numpy 数组。所以我真的需要将列表列表与字典进行比较。

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