Python __getitem__列表和dict之间的性能

Question

我实现了一种动态编程算法(自下而上(
作为一个快速解决方案，我在DP表中使用了字典而不是固定大小的数组，但考虑到我的输入大小(n高达50k，m敢达100(，我认为将dp_table: Dict[int, Dict[int, float]]重构为dp_table: List[List[float]]会有很大的收获。

我们知道哈希表有O(1(运行时间用于索引，但具有"高"常数值，而列表索引是O(1。

dict.__getitem__和list.__getitem__的性能有何不同
使用numpy数组会获得更多好处吗？

Answer 1

使用timeit进行基准测试非常简单。

>>> timeit.Timer('values[50]', 'values = {i: i for i in range(100)}').timeit(number = 10**7)
0.3076519769999999
>>> timeit.Timer('values[50]', 'values = list(range(100))').timeit(number = 10**7)
0.2913365720000005
>>> timeit.Timer('values[50]', 'import numpy; values = numpy.arange(100)').timeit(number = 10**7)
1.262765399000001

奇怪的是，numpy数组在这里的表现很糟糕。

Answer 2

dict.__getitem__和list.__getitem__之间的性能差异是什么

wiki.python文章TimeComplexity声称以下时间复杂性：

• 对于list获取项目：平均情况O(1(摊余最坏情况O(2(
• 对于dict获取项目：平均情况O(1(摊余的最坏情况O(n(

请记住，这些是CPython的值，其他python实现可能有所不同。