搜索字典与搜索排序的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)的调用，而基于阵列的实现最终将调用两种方法，即.searchsorted和__getitem__两次。 Python是一种动态语言，函数调用，特别是方法调用（由于方法解析）非常昂贵。

但基本上，您的基于dict的实现应该更好地扩展。 Python dict对象通常是具有恒定时间搜索的高度优化的哈希映射。你的基于数组的实现是二分搜索，所以它是O（log（n））。您将看到一个测试用例，您可以选择最差的情况，即搜索不在数组中的元素。假设searchsorted以对数形式进行扩展，则在看到明显的运行时效果之前，可能需要大幅增加数组的大小（例如，100x，1000x）。

绝对没有机会实现比Python中内置的dict更快的查找。