有什么比 dict() 更快的吗？

Question

我需要一种更快的方法来存储和访问大约 3GB 的 k:v 对。其中 k 是一个字符串或整数， v 是一个 np.array() 可以是不同的形状。

在存储和访问这样的表时，是否有任何对象比标准 python dict 更快？例如，一个 pandas.DataFrame ？

据我所知，python dict 是哈希表的一个相当快速的实现。对于我的具体情况，还有什么比这更好的吗？

原文由 alec_djinn 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

不，对于这个任务没有比字典更快的了，那是因为它的索引（获取和设置项目）甚至成员检查的复杂性平均为 O(1)。 （在 Python 文档 https://wiki.python.org/moin/TimeComplexity 上检查其余功能的复杂性）

一旦将项目保存在字典中，您就可以在恒定时间内访问它们，这意味着您的性能问题不太可能与字典索引有任何关系。话虽这么说，您仍然可以通过对对象及其类型进行一些更改来稍微加快此过程，这些更改可能会在后台操作中进行一些优化。

例如，如果您的字符串（键）不是很大，您可以使用查找键和字典键。实习是将对象缓存在内存中——或者在 Python 中，“实习”字符串表——而不是将它们创建为单独的对象。

Python 在 sys 模块中提供了一个 intern() 函数，您可以使用它。

在“interned”字符串表中输入字符串并返回 interned 字符串——它是字符串本身或一个副本。实习字符串对于在 字典查找 中获得一点性能很有用……

还 …

如果字典中的键被驻留并且查找键被驻留，则可以通过指针比较来完成键比较（散列后），而不是比较字符串值本身，从而减少了对对象的访问时间。

这是一个例子：

 In [49]: d = {'mystr{}'.format(i): i for i in range(30)}

In [50]: %timeit d['mystr25']
10000000 loops, best of 3: 46.9 ns per loop

In [51]: d = {sys.intern('mystr{}'.format(i)): i for i in range(30)}

In [52]: %timeit d['mystr25']
10000000 loops, best of 3: 38.8 ns per loop

原文由 Mazdak 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

不，我认为没有比 dict 更快的了。其索引检查的时间复杂度为 O(1) 。

 -------------------------------------------------------
Operation    |  Average Case  | Amortized Worst Case  |
-------------------------------------------------------
Copy[2]      |    O(n)        |       O(n)            |
Get Item     |    O(1)        |       O(n)            |
Set Item[1]  |    O(1)        |       O(n)            |
Delete Item  |    O(1)        |       O(n)            |
Iteration[2] |    O(n)        |       O(n)            |
-------------------------------------------------------

PS https://wiki.python.org/moin/TimeComplexity

原文由 akash karothiya 发布，翻译遵循 CC BY-SA 3.0 许可协议