부동 소수점 인덱스에서 배열로의 빠른 검색

Question

축에 길이가 len 인 n 간격이 있다고 가정합니다. 각각은 ndarray에 값이 지정됩니다. 이제 부동 소수점 숫자로 주어진 query_pos 위치의 값을 조회하고 싶습니다. 현재, 나는 그것을 다음과 같은 방법을 할 계획 :

n = 100 
len = 0.39483 
data = ... # creates ndarray with data of length n = 100 
query_pos = ... # creates an ndarray with positions to query 
values_at_query_pos = data[(query_pos/len).astype(int)] # questionable line 

좋은 방법은 그것을 할 또는 정수 인덱스로 부동 소수점 쿼리 위치를 변환하는보다 효율적인 방법이 있습니다 다음 배열에서 읽을인가요 ? 특히 astype(int)은 값이 비싸거나 값 비싼 작업이며, 예를 들어 부서 또는 메모리 읽기와 비교됩니다.

좀 더 발언 :

• 마지막으로, 2 개 및 3 차원으로 사용됩니다. 현재 불법 색인으로 이어질 수있는 위치를 잡으려고합니다. 전에에 도달하면 으로 이동합니다.

• data 어레이는 충분히 높은 해상도를 가지므로 에는 필터링이나 보간이 필요하지 않습니다. 이전 단계에서 완료됩니다.

Answer 1

대신 그 스칼라 query_pos의 각 요소의 분할, 우리는 스칼라의 역수를 미리 계산하고, 거기에 어떤 고속화 대신 승산을 사용할 수있다. 직감은 분단이 곱셈보다 비용이 많이 드는 일이라는 것입니다. 여기

그것에 빠른 런타임 테스트입니다 -

In [177]: # Setup inputs 
    ...: n = 100 
    ...: len1 = 0.39483 
    ...: data = np.random.rand(100) 
    ...: query_pos = np.random.randint(0,25,(100000)) 
    ...: 

In [178]: %timeit query_pos/len1 
1000 loops, best of 3: 612 µs per loop 

In [179]: %timeit query_pos * (1/len1) 
10000 loops, best of 3: 173 µs per loop 

둘째, 단지 앞에 나온 런타임 테스트에 사용되는 설정처럼, 많은 반복 인덱스가있는 경우, 우리는 몇 가지 더 한계 개선을위한 np.take을 사용할 수 있습니다 으로는 다음과 같습니다 -

In [196]: %timeit data[(query_pos *(1/len1)).astype(int)] 
1000 loops, best of 3: 538 µs per loop 

In [197]: %timeit np.take(data,(query_pos * (1/len1)).astype(int)) 
1000 loops, best of 3: 526 µs per loop 

당신이 일반적인 ndarrays에 사용하려는 경우, 우리는 np.take와 axis PARAM을 사용해야합니다.

원래의 접근 방식과 비교 -

가

In [202]: %timeit data[(query_pos/len1).astype(int)] 
1000 loops, best of 3: 967 µs per loop 

마지막으로, 분할 작업이 int로 전환 대항 스택 방법에 대한 질문에, 그들이 큰 데이터 세트에 비교 보인다. 그러나 색인 생성에 필요한만큼 변환을 피할 수없는 것 같습니다. 이 눈에 띄게 빠른 단지 큰 배열을위한 것입니다

idx = np.empty_like(query_pos, int) 
np.divide(query_pos, len, out=idx, casting='unsafe') 

: 당신은 똑바로 int 배열로 출력 분할의 결과를 수

In [210]: idx = query_pos * (1/len1) 

In [211]: %timeit query_pos * (1/len1) 
10000 loops, best of 3: 165 µs per loop 

In [212]: %timeit idx.astype(int) 
10000 loops, best of 3: 110 µs per loop 

Answer 2

- 여기에 타이밍 테스트입니다. 그러나이 코드는 읽기가 어렵 기 때문에 병목 현상이있는 경우에만 최적화하십시오!