有没有比dict()更快的东西？

Question

我需要一种更快的方式来存储和访问大约3GB的k:v对.其中k是string或integer并且v是一个np.array(),可以是不同的形状.有没有任何对象,比标准python dict在存储和访问这样的表时更快？例如,a pandas.DataFrame？

到目前为止,我已经了解python dict是一个相当快速的哈希表实现,有什么比我的具体案例更好的？

Answer 1

没有什么比这个任务的字典更快,这是因为它的索引甚至成员资格检查的复杂性大约为O(1).

将项目保存在字典中后,您可以在固定的时间内访问它们.也就是说,问题不在于索引过程.但是,通过对对象及其类型进行一些更改,您可以稍微加快进程.这可能会在引擎盖的操作中引起一些优化.例如,如果你的字符串(键)不是很大,你可以实习它们,以便在内存中兑现,而不是作为一个对象创建.如果字典中的键被中断,并且查找键被中断,则可以通过指针比较而不是字符串比较来进行键比较(在散列之后).这使得访问对象的速度更快.Python intern()在sys模块中提供了一个函数,您可以将其用于此目的.

在"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

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

Answer 3

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