假设您正在网格上执行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数组。因此,我确实需要将列表的列表与字典进行比较。