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

Question

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

在存储和访问这样的 table 方面，是否有任何对象比标准 python 字典更快？例如，pandas.DataFrame?

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

Answer 1

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

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

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

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

Enter string in the table of “interned” strings and return the interned string – which is string itself or a copy. Interning strings is useful to gain a little performance on dictionary lookup...

还有...

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

这是一个例子：

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

Answer 2

你可以考虑将它们存储在像 Trie 这样的数据结构中，因为你的键是字符串。即使要从 Trie 中存储和检索，您也需要 O(N)，其中 N 是密钥的最大长度。计算键的哈希值的哈希计算也是如此。 Hash用于在HashTable中查找和存储。我们通常不考虑散列时间或计算。

你可以试一试 Trie，它的性能应该几乎相同，可能会快一点（如果哈希值的计算方式不同

HASH[i] = (HASH[i-1] + key[i-1]*256^i % BUCKET_SIZE ) % BUCKET_SIZE

或类似的由于碰撞我们需要使用 256^i.

你可以尝试将它们存储在Trie中，看看它的表现如何。

Answer 3

不，我认为没有比 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

Answer 4

一个numpy.array[]和简单的dict={}比较：

import numpy
from timeit import default_timer as timer

my_array = numpy.ones([400,400])

def read_out_array_values():
    cumsum = 0
    for i in range(400):
        for j in range(400):
            cumsum += my_array[i,j]


start = timer()
read_out_array_values()
end = timer()
print("Time for array calculations:" + str(end - start))


my_dict = {}
for i in range(400):
    for j in range(400):
        my_dict[i,j] = 1

def read_out_dict_values():
    cumsum = 0
    for i in range(400):
        for j in range(400):
            cumsum += my_dict[i,j]
    
start = timer()
read_out_dict_values()
end = timer()
print("Time for dict calculations:" + str(end - start))

打印：

Time for dict calculations:0.046898419999999996
Time for array calculations:0.07558204099999999
============= RESTART: C:/Users/user/Desktop/dict-vs-numpyarray.py =============
Time for array calculations:0.07849989000000002
Time for dict calculations:0.047769446000000104

Answer 5

人们会认为数组索引比散列查找更快。

因此，如果我们可以将此数据存储在一个 numpy 数组中，并假设键不是字符串，而是数字，那会比 python 字典更快吗？

不幸的是，NumPy 针对向量运算进行了优化，而不是针对值的单独查找进行了优化。 Pandas票价更差。在此处查看实验：https://nbviewer.jupyter.org/github/annotation/text-fabric/blob/master/test/pandas/pandas.ipynb

另一个候选者可能是数组模块中的 Python 数组。但这不适用于可变大小的值。为了使这项工作有效，您可能需要将其包装到一些纯 python 代码中，这将阻碍数组提供的所有时间性能增益。

因此，即使放宽了OP的要求，似乎仍然没有比字典更快的选择。

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

Is there anything faster than dict()?

python

python-3.x

numpy

dictionary

python-internals