사전 검색 Vs 정렬 된 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__이라는 두 가지 메소드를 두 번 호출합니다. 파이썬은 동적 언어이고, 함수 호출과, 특히 메소드 호출 때문에 (메소드 해석 때문에) 비싸다.

근본적으로 dict 기반 구현의 확장 성이 좋아야합니다. Python dict 개체는 일반적으로 상수 시간 검색이 가능한 고도로 최적화 된 해시 맵입니다. 배열 기반 구현은 바이너리 검색이므로 O (log (n))입니다. 최악의 경우, 즉 배열에없는 요소를 검색하는 테스트 케이스가 표시됩니다. searchsorted 스케일을 대수적으로 감안할 때 주목할만한 런타임 효과를보기 전에 배열 크기를 극적으로 증가시켜야 할 수도 있습니다 (예 : 100 배, 1000 배).

파이썬에서 내장 된 dict보다 빠른 검색을 구현할 가능성은 절대적으로 없습니다.