为什么在相同的 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 timeit

def 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 T

T_1 = [0]*1001 

# initial dict T

T_2 = {} 

for i in range(1001):

    T_2[i] = 0

t = 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 中的列表）可能是最佳选择。如果您的数据集具有非整数键，则字典是最佳选择。这就是它的设计目的。如果您有大间隔的整数键，与列表相比，字典将节省大量内存，因为列表必须包含大量浪费的索引。