python - 搜索字典与搜索排序的 numpy 结构化数组

Question

假设我们有一个唯一整数数组。给定该列表的整数 (N)，我希望能够尽快获取其在数组中的索引 (I)。

我的想法是生成一个给定 N 返回 I 的对象。我想使用数据类型 (N,I) 并按 N 排序的结构化数组，或者只是使用键 N 的字典。

这两种方法的搜索速度似乎与对象的大小无关，这使我相信它们是由开销控制的。然而，我有点惊讶地发现搜索字典比搜索结构化数组快了几乎 10 倍。所以我的问题是:

1. 为什么字典比我的数组实现快得多？
2. 是否有比这两种方法更快的替代方法？

<小时/>

MWE:

from __future__ import division
import numpy as np
import timeit

#Time a function
def Timeme(funct,var,NN=10,NNN=10):
    for i in xrange(NN):
        start =timeit.default_timer()
        for t in xrange(NNN):
            funct(*var)
        end =timeit.default_timer()
        print str(i)+': '+str((end - start)/NNN*1000)  

#Function to build a dictionary        
def mydict(Flist):
    Mydict=dict()
    for n,i in Flist:
        Mydict[n]=i
    return Mydict

#Functions to access the data
def myfd(Mydict,vtest):
    return Mydict[vtest]

def myfs(Flist,vtest):
    n=Flist['N'].searchsorted(vtest)
    return Flist['I'][n] #Flist[n]['I'] is slower

#N=100000  
N=100

# "Allocate empty structured array"
Flist=np.empty(N,dtype=[('N','i4'),('I','i4')])

# "Fill N with randoms and I with sequence"
Flist['N'] = np.random.randint(N*1000,size=N)
Flist['I'] = np.arange(N)

# "Create test value"
ntest=np.random.randint(N)
vtest=Flist['N'][ntest]

# "Sort array on N"
Flist.sort(order='N')

# "Make dictionary"
Mydict=dict(Flist)

# "Get values"    
nrd=myfd(Mydict,vtest)
nrs=myfs(Flist,vtest)

print "Tests OK: " + str(ntest == nrd and ntest == nrs) 

print "\nSearch with Dictionary:"
Timeme(myfd,[Mydict,vtest],NN=5,NNN=100)
print "\nSearch directly in Array:"
Timeme(myfs,[Flist,vtest],NN=5,NNN=100)

结果:

Tests OK: True

Search with Dictionary:
0: 0.000404204885682
1: 0.000409016848607
2: 0.000418640774457
3: 0.000404204885682
4: 0.000394580959833

Search directly in Array:
0: 0.00455211692685
1: 0.00465798011119
2: 0.00458580066732
3: 0.00464354422242
4: 0.00476384329554

Answer 1

这可以部分地通过方法调用/函数调用开销来解释。您的字典搜索函数仅执行单个操作(索引)，该操作会转换为对 my_dict.__getitem__(key) 的调用，而基于数组的实现最终会调用 3 个方法，.searchsorted 和 __getitem__ 两次。 Python 是一种动态语言，函数调用，尤其是方法调用(由于方法解析)的成本很高。

但从根本上来说，基于 dict 的实现应该可以更好地扩展。 Python dict 对象通常是高度优化的 HashMap ，具有恒定时间搜索。基于数组的实现是二分搜索，因此它是 O(log(n))。您将在测试用例中看到这一点，其中您选择最坏的情况，即搜索不在数组中的元素。鉴于 searchsorted 按对数缩放，您可能必须大幅增加数组的大小(例如 100 倍、1000 倍)才能看到显着的运行时效果。

绝对不可能实现比 Python 中内置 dict 更快的查找速度。