列表的列表 vs 字典

Question

在Python中，使用列表的列表和字典来进行数字操作时，有哪些优缺点呢？我正在编写一系列函数的类来解决线性代数课程中的简单矩阵运算。我一开始使用字典，但后来发现 numpy 使用列表的列表，所以我想这种方式肯定有一些优点。

示例：[[1,2,3],[4,5,6],[7,8,9]] 相对于 {0:[1,2,3],1:[4,5,6],2:[7,8,9]}。

- Alex

---

这取决于情况。阅读一本数据结构教材以了解哈希表的工作原理。存在很多差异使得某些用例中它更快，但对于其他用例则更慢。 - millimoose

在矩阵相关运算中，列表（lists）可以维护顺序，而字典（dicts）则是无序的。我认为对于矩阵相关的操作，使用列表会更合适。 - Ashwini Chaudhary

NumPy 不使用列表嵌套列表的形式：它可以将二维数组呈现为列表嵌套列表的形式，但实际上它使用一种专门的数组类型，比列表嵌套列表更加高效和灵活。 - Mark Dickinson

然而，这取决于您的矩阵是否非常稀疏。如果是这样，那么与其使用充满“None”的列表，使用字典可能更有意义。 - Gareth Latty

@Lattyware 直观地看，即使是一个中等稀疏的列表，在中间进行多次删除/插入操作（这将需要在列表中进行大量复制），使用字典可能会更好。（当然，这可能也不是因为复杂性理论与实际性能并不直接相关。） - millimoose

Answer 1

我认为这在很大程度上取决于您计划如何使用这个结构。

Python中的字典（像大多数字典一样）默认是无序的。如果您计划像这样迭代您的数据，则不应使用字典：

for list in dict.keys():
    for elem in list:
        # Logic

同样，如果只是作为索引使用的话，使用键为1、2、3等等的字典就没有太多意义了。由于哈希处理，字典在内存中占用更多的空间。

如果您计划通过元素访问项目(听起来似乎是这样)，仍然需要使用列表。列表的索引查找是O (1)，与字典相同。唯一的区别是当您查找某个关键值而不是索引时(在字典中比在列表中慢)。

仅在存在某种关键值关系映射的情况下考虑使用字典，在这种情况下需要搜索有意义的键以检索相关值。这似乎不是这种情况。坚持使用列表。

并不是说字典是一个糟糕的数据结构。Ruby和Python向我介绍了它们，并且对于那些前面提到的映射问题非常有用(我发现我经常遇到这种问题)。它们只是对特定类别的问题有用，而这不是其中之一。

- KChaloux

Answer 2

如果字典的键是 0, 1, ..., n 这样的序列，使用 list 会更快，因为不需要进行哈希。但一旦键不再是这样的序列，你就需要使用 dict。

- Elmar Peise

---

我曾认为list是双向链表，而在list中查找时间复杂度为O(n)，而在dict中为O(1)，因此在list中查找速度较慢。 - Akavall

@Akavall Python的列表不是双向链表。 - Gareth Latty

@Akavall 列表是通过动态数组实现的。列表是如何实现的？ - Ashwini Chaudhary