为什么在相同的 Python 代码中 List 比 Dict 快？

Question

我写了一个关于动态规划的函数。递归公式为T(n) = T(0) * T(n-1) + T(1) * T(n-2) + … + T(n-1) * T(0)如您所见， 的值T(n)取决于 的值T(0) … T(n-1)。在这个问题中，我需要存储T(0) … T(n-1)来计算T(n)。但哪种数据结构最好？假设我们已经完成了计算T(0) … T(5)。我们需要计算T(6)我们可以将 T 存储在以下结构中：T = [1,1,2,5,14,42,0]T = {0:1,1:1,2:2,3:5,4:14,5:42,6:0}我的答案是dict首先，因为获取的时间复杂度T(k)是O(1)。但是经过测试list和dict。测试结果表明list比 快dict。 为什么？？？我n = 1000用来测试程序。import timeitdef test(n, T):    T[0] = 1    # calculate T[i]    # we need to calculate T[0]-> T[n-1] at first.    for i in range(1,n+1):         for j in range(i):            T[i] += T[j]*T[i-1-j]    return T[n]# initial list TT_1 = [0]*1001 # initial dict TT_2 = {} for i in range(1001):    T_2[i] = 0t = timeit.timeit(stmt="test(1000,T_1)",setup="from __main__ import test,T_1;",number=10)print("store T with list, total time is:",t)t = timeit.timeit(stmt="test(1000,T_2)",setup="from __main__ import test,T_2;",number=10)print("store T with dict, total time is:",t)运行结果如下：用list存储T，总时间为：6.454328614287078用dict存储T，总时间为：6.761199993081391谢谢你的帮助。

Answer 1

字典使用散列来查找增加了一些开销的值。还存在冲突的可能性，这需要更多的性能来解决。

长答案：

Hashing：
Dictionary 被实现为一个 hashtable，它是一种内部将值存储在数组中的数据结构。它通过将键传递给散列函数来确定要使用的索引。散列函数将产生一个内部数组范围内的值。这是一种通过键而不是索引来查找项目的相对快速的方法。但是由于每次都需要运行这个散列函数，它仍然比直接通过索引查找要慢。

碰撞：
字典在大多数情况下不能完全避免碰撞。内部数组既可以实现为链表数组，也可以使用其他技术来解决冲突。如果数据集变化缓慢，或者从不变化，则可以避免冲突；为给定的数据集创建一个完美的哈希函数。没有适用于所有数据集的通用完美哈希函数，这是不可能的。因此，诸如 Python 中提供的通用字典必须实现冲突解决。

哪种数据结构更好？这取决于您的数据是如何映射的。

如果您可以将它映射到具有很少间隙的连续整数键（例如 0、1、2、3、4、5 等...），那么数组（python 中的列表）可能是最佳选择。

如果您的数据集具有非整数键，则字典是最佳选择。这就是它的设计目的。

如果您有大间隔的整数键，与列表相比，字典将节省大量内存，因为列表必须包含大量浪费的索引。