Numpy: 첫 번째 값 인덱스를 빠르게 찾습니다.

Numpy: 첫 번째 값 인덱스를 빠르게 찾습니다.

Numpy 배열에서 숫자가 처음 나타나는 인덱스를 어떻게 찾을 수 있습니까?속도는 저에게 중요합니다.다음 답변은 전체 배열을 검색하고 첫 번째 항목을 찾을 때 멈추지 않기 때문에 관심이 없습니다.

itemindex = numpy.where(array==item)[0][0]
nonzero(array == item)[0][0]

참고 1: 해당 질문의 답변 중 관련이 없는 것 같습니다. 배열에 있는 어떤 것의 첫 번째 인덱스를 반환하는 Numpy 함수가 있습니까?

참고 2: C 컴파일된 방법을 사용하는 것이 파이썬 루프보다 선호됩니다.

Numpy 2.0.0에 대해 예약된 이 기능 요청이 있습니다. https://github.com/numpy/numpy/issues/2269

너무 늦었지만 나중에 참고하시기 바랍니다.numba (1)을 사용하는 것이 numpy가 구현할 때까지 가장 쉬운 방법입니다.아나콘다 파이썬 배포를 사용하는 경우 이미 설치되어 있어야 합니다.코드가 컴파일되어 빨라질 것입니다.

@jit(nopython=True)
def find_first(item, vec):
    """return the index of the first occurence of item in vec"""
    for i in xrange(len(vec)):
        if item == vec[i]:
            return i
    return -1

다음과 같은 경우:

>>> a = array([1,7,8,32])
>>> find_first(8,a)
2

몇 가지 방법에 대한 벤치마크를 만들었습니다.

• argwhere
• nonzero과
• .tostring()@ Reilink에서 처럼
• 파이썬 루프
• 포트란 루프

Python 및 Fortran 코드를 사용할 수 있습니다.저는 목록으로 변환하는 것과 같은 가능성이 없는 것들을 건너뛰었습니다.

로그 척도의 결과입니다. X축은 바늘의 위치입니다(배열 아래쪽에 있는지 확인하는 데 더 오래 걸립니다). 마지막 값은 배열에 없는 바늘입니다.Y축은 그것을 찾는 시간입니다.

어레이에는 100만 개의 요소가 있으며 테스트는 100번 실행되었습니다.결과는 여전히 약간 변동하지만 질적 추세는 분명합니다.Python과 f2py는 첫 번째 요소에서 중단되어 서로 다르게 확장됩니다.바늘이 처음 1%에 있지 않으면 파이썬은 너무 느려집니다. 반면에f2py빠르지만 컴파일해야 합니다.

요약하자면, f2py는 특히 바늘이 꽤 일찍 나타나는 경우 가장 빠른 해결책입니다.

귀찮을 정도로 내장된 것은 아니지만, 실제로는 2분 정도의 작업입니다.다음 파일에 추가합니다.search.f90:

subroutine find_first(needle, haystack, haystack_length, index)
    implicit none
    integer, intent(in) :: needle
    integer, intent(in) :: haystack_length
    integer, intent(in), dimension(haystack_length) :: haystack
!f2py intent(inplace) haystack
    integer, intent(out) :: index
    integer :: k
    index = -1
    do k = 1, haystack_length
        if (haystack(k)==needle) then
            index = k - 1
            exit
        endif
    enddo
end

만약 당신이 다른 것을 찾고 있다면.integer그냥 유형을 변경합니다.그런 다음 다음을 사용하여 컴파일합니다.

f2py -c -m search search.f90

다음 작업을 수행할 수 있습니다(Python에서).

import search
print(search.find_first.__doc__)
a = search.find_first(your_int_needle, your_int_array)

0이 아닌 첫 번째 요소를 찾는다면 다음과 같은 해킹을 사용할 수 있습니다.

idx = x.view(bool).argmax() // x.itemsize
idx = idx if x[idx] else -1

매우 빠른 "넘피 퓨어" 솔루션이지만 아래에서 설명하는 경우에 따라 실패합니다.

이 솔루션은 숫자 유형에 대한 0의 거의 모든 표현이 다음과 같이 구성된다는 사실을 활용합니다.0바트입다니에 합니다. 그것은 numpy의 것에 적용됩니다.bool뿐만 아니라.최근 버전의 numpy에서는argmax()은 함는처수단사논용을 할 때 합니다.bool 입타의 . 이는즈사는▁of이즈▁type.bool1바이트입니다.

따라서 다음을 수행해야 합니다.

• 보만듭다니기를로 보기를 .bool복사본이 생성되지 않습니다.
• 사용하다argmax() 을 사용하여 첫 .
• 첫 이 합니다.// ( )x.itemsize)
• 확인해 보다x[idx]는 실제로 0이 이 아닌 경우입니다. 0이 아닌 경우는 0이 아닙니다.

Numba 솔루션에 대한 벤치마크를 만들어 구축했습니다.np.nonzero.

import numpy as np
from numba import jit
from timeit import timeit

def find_first(x):
    idx = x.view(bool).argmax() // x.itemsize
    return idx if x[idx] else -1

@jit(nopython=True)
def find_first_numba(vec):
    """return the index of the first occurence of item in vec"""
    for i in range(len(vec)):
        if vec[i]:
            return i
    return -1


SIZE = 10_000_000
# First only
x = np.empty(SIZE)

find_first_numba(x[:10])

print('---- FIRST ----')
x[:] = 0
x[0] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=1000), 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=1000), 'ms')

print('---- LAST ----')
x[:] = 0
x[-1] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- NONE ----')
x[:] = 0
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- ALL ----')
x[:] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

내 기계의 결과는 다음과 같습니다.

---- FIRST ----
ndarray.nonzero 57.63976670001284 ms
find_first 0.0010841979965334758 ms
find_first_numba 0.0002308919938514009 ms
---- LAST ----
ndarray.nonzero 58.96685277999495 ms
find_first 5.923203580023255 ms
find_first_numba 8.762269750004634 ms
---- NONE ----
ndarray.nonzero 25.13398071998381 ms
find_first 5.924289370013867 ms
find_first_numba 8.810063839919167 ms
---- ALL ----
ndarray.nonzero 55.181210660084616 ms
find_first 0.001246920000994578 ms
find_first_numba 0.00028766007744707167 ms

이 솔루션은 numba보다 33% 빠르고 "numpy-pure"입니다.

단점:

• 는 다과같은허용유형작는않에동습니다지하음과 같은 는 작동하지 않습니다.object
• 가 나타 에는마이스 0 해합실다에 가끔 합니다.float또는double

정렬된 배열의 경우np.searchsorted작동하다.

용 하 배 변 수 니 다 할array.tostring()그런 다음 find() 방법을 사용합니다.

(array==item).tostring().find('\x01')

그러나 Python 문자열은 불변해야 하므로 데이터를 복사해야 합니다.를 들어 상승 할 수 있다는 것입니다.\x00\x01

다른 방법과 어레이에 대한 사전 지식이 도움이 되는 문제를 해결했다고 생각합니다.데이터의 첫 번째 Y%에서 답을 찾을 확률이 X인 것과 같은 것입니다.행운을 바라며 문제를 분할하고 파이썬에서 중첩된 목록 이해 같은 것을 수행하는 것.

이 무차별적인 힘을 수행하기 위해 C 함수를 작성하는 것도 C타입을 사용하는 것은 그리 어렵지 않습니다.

함께 해킹한 C코드(index.c):

long index(long val, long *data, long length){
    long ans, i;
    for(i=0;i<length;i++){
        if (data[i] == val)
            return(i);
    }
    return(-999);
}

그리고 비단뱀:

# to compile (mac)
# gcc -shared index.c -o index.dylib
import ctypes
lib = ctypes.CDLL('index.dylib')
lib.index.restype = ctypes.c_long
lib.index.argtypes = (ctypes.c_long, ctypes.POINTER(ctypes.c_long), ctypes.c_long)

import numpy as np
np.random.seed(8675309)
a = np.random.random_integers(0, 100, 10000)
print lib.index(57, a.ctypes.data_as(ctypes.POINTER(ctypes.c_long)), len(a))

92점을 받았습니다.

파이썬을 적절한 기능으로 포장하면 됩니다.

이 시드에 대해 C 버전이 훨씬 더 빠릅니다(시간이 부족하다는 경고).

import timeit
t = timeit.Timer('np.where(a==57)[0][0]', 'import numpy as np; np.random.seed(1); a = np.random.random_integers(0, 1000000, 10000000)')
t.timeit(100)/100
# 0.09761879920959472
t2 = timeit.Timer('lib.index(57, a.ctypes.data_as(ctypes.POINTER(ctypes.c_long)), len(a))', 'import numpy as np; np.random.seed(1); a = np.random.random_integers(0, 1000000, 10000000); import ctypes; lib = ctypes.CDLL("index.dylib"); lib.index.restype = ctypes.c_long; lib.index.argtypes = (ctypes.c_long, ctypes.POINTER(ctypes.c_long), ctypes.c_long) ')
t2.timeit(100)/100
# 0.005288000106811523

@tal 를미a 제습니다했시를 했습니다.numba첫 번째 인덱스를 찾는 기능이지만 1D 어레이에서만 작동합니다.를 사용하여 임의의 차원 배열에서 첫 번째 인덱스를 찾을 수도 있습니다.

from numba import njit
import numpy as np

@njit
def index(array, item):
    for idx, val in np.ndenumerate(array):
        if val == item:
            return idx
    return None

샘플 사례:

>>> arr = np.arange(9).reshape(3,3)
>>> index(arr, 3)
(1, 0)

Timings에 따르면 Totals 솔루션과 성능이 유사합니다.

arr = np.arange(100000)
%timeit index(arr, 5)           # 1000000 loops, best of 3: 1.88 µs per loop
%timeit find_first(5, arr)      # 1000000 loops, best of 3: 1.7 µs per loop

%timeit index(arr, 99999)       # 10000 loops, best of 3: 118 µs per loop
%timeit find_first(99999, arr)  # 10000 loops, best of 3: 96 µs per loop

이 문제는 배열을 청크로 처리함으로써 순수한 numpy로 효과적으로 해결할 수 있습니다.

def find_first(x):
    idx, step = 0, 32
    while idx < x.size:
        nz, = x[idx: idx + step].nonzero()
        if len(nz): # found non-zero, return it
            return nz[0] + idx
        # move to the next chunk, increase step
        idx += step
        step = min(9600, step + step // 2)
    return -1

가 어이가청크처리다니됩기의 처리됩니다.step.step단계가 길수록 제로 어레이 처리 속도가 빨라집니다(대략적인 경우.크기가 작을수록 시작 시 0이 아닌 배열을 더 빠르게 처리할 수 있습니다. 작은것시작것요이로 하는 것입니다.step그리고 그것을 기하급수적으로 증가시킵니다.게다가, 제한된 혜택 때문에 일부 임계값 이상으로 증가시킬 필요가 없습니다.

저는 이 솔루션을 순수 ndarary.nonzero 및 numba 솔루션과 1000만 개의 플로트 어레이와 비교했습니다.

import numpy as np
from numba import jit
from timeit import timeit

def find_first(x):
    idx, step = 0, 32
    while idx < x.size:
        nz, = x[idx: idx + step].nonzero()
        if len(nz):
            return nz[0] + idx
        idx += step
        step = min(9600, step + step // 2)
    return -1

@jit(nopython=True)
def find_first_numba(vec):
    """return the index of the first occurence of item in vec"""
    for i in range(len(vec)):
        if vec[i]:
            return i
    return -1


SIZE = 10_000_000
# First only
x = np.empty(SIZE)

find_first_numba(x[:10])

print('---- FIRST ----')
x[:] = 0
x[0] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=1000), 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=1000), 'ms')

print('---- LAST ----')
x[:] = 0
x[-1] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- NONE ----')
x[:] = 0
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

print('---- ALL ----')
x[:] = 1
print('ndarray.nonzero', timeit(lambda: x.nonzero()[0][0], number=100)*10, 'ms')
print('find_first', timeit(lambda: find_first(x), number=100)*10, 'ms')
print('find_first_numba', timeit(lambda: find_first_numba(x), number=100)*10, 'ms')

그리고 내 기계에 대한 결과는:

---- FIRST ----
ndarray.nonzero 54.733994480002366 ms
find_first 0.0013148509997336078 ms
find_first_numba 0.0002839310000126716 ms
---- LAST ----
ndarray.nonzero 54.56336712999928 ms
find_first 25.38929685000312 ms
find_first_numba 8.022820680002951 ms
---- NONE ----
ndarray.nonzero 24.13432420999925 ms
find_first 25.345200140000088 ms
find_first_numba 8.154927100003988 ms
---- ALL ----
ndarray.nonzero 55.753537260002304 ms
find_first 0.0014760300018679118 ms
find_first_numba 0.0004358099977253005 ms

순수하다ndarray.nonzero확실히 느슨합니다.Numba 용액은 최상의 경우에 5배 더 빨리 순환됩니다.그것은 최악의 경우에 3배 더 빨리 순환됩니다.

목록이 정렬되면 '이등분' 패키지로 인덱스를 매우 빠르게 검색할 수 있습니다.O(n)가 아니라 O(log(n)입니다.

bisect.bisect(a, x)

배열 a에서 x를 찾습니다. 정렬된 경우 모든 첫 번째 요소를 통과하는 C-루틴보다 훨씬 빠릅니다(충분히 긴 목록).

가끔 알게 되어 좋습니다.

제가 알기로는 부울 배열의 np.any 및 np.all만 단락됩니다.

이 경우 numpy는 전체 배열을 두 번, 한 번은 부울 조건을 만들고 두 번째는 인덱스를 찾아야 합니다.

이 경우 제가 추천하는 것은 싸이톤을 사용하는 것입니다.특히 다양한 d타입과 모양에 대한 많은 유연성이 필요하지 않다면 이 경우에 대한 예제를 쉽게 조정할 수 있어야 한다고 생각합니다.

저는 이것이 제 일에 필요했기 때문에 파이썬과 Numpy의 C 인터페이스를 독학하고 저만의 것을 썼습니다.http://pastebin.com/GtcXuLyd 1-D 어레이에만 해당되지만 대부분의 데이터 유형(int, float 또는 string)에서 작동하며 테스트 결과 순수 Python-numpy에서 예상되는 접근 방식보다 약 20배 더 빠릅니다.

오랫동안 matlab 사용자로서 Ia는 이 문제에 대한 효율적인 해결책을 찾고 있었습니다.마지막으로, 이 스레드의 제안에 대한 논의에 동기를 부여하여, 저는 여기서 제안된 것과 유사한 API를 구현하는 솔루션을 생각해 내려고 노력했고, 현재는 1D 어레이만 지원합니다.

이렇게 사용하시면 됩니다.

import numpy as np
import utils_find_1st as utf1st
array = np.arange(100000)
item = 1000
ind = utf1st.find_1st(array, item, utf1st.cmp_larger_eq)

지원되는 조건 연산자는 cmp_equal, cmp_not_equal, cmp_larger, cmp_smaller, cmp_larger_eq, cmp_smaller_eq입니다.효율성을 위해 확장자는 c로 작성됩니다.

출처, 벤치마크 및 기타 세부 정보는 다음과 같습니다.

https://pypi.python.org/pypi?name=py_find_1st&:action=display

우리 팀에서 사용하기 위해 (리눅스 및 macrows의 아나콘다) 설치를 단순화하는 아나콘다 설치 프로그램을 만들었습니다. 여기 설명된 대로 사용할 수 있습니다.

https://anaconda.org/roebel/py_find_1st

일련의 검색을 수행하는 경우 문자열로 변환하는 것과 같은 영리한 작업을 수행함으로써 얻는 성능은 검색 차원이 충분히 크지 않으면 외부 루프에서 손실될 수 있습니다.위에서 제안한 문자열 변환 트릭을 사용하는 find1과 내부 축을 따라 argmax를 사용하는 find2를 반복하는 성능을 확인하십시오(및 불일치가 -1로 반환되도록 조정).

import numpy,time
def find1(arr,value):
    return (arr==value).tostring().find('\x01')

def find2(arr,value): #find value over inner most axis, and return array of indices to the match
    b = arr==value
    return b.argmax(axis=-1) - ~(b.any())


for size in [(1,100000000),(10000,10000),(1000000,100),(10000000,10)]:
    print(size)
    values = numpy.random.choice([0,0,0,0,0,0,0,1],size=size)
    v = values>0

    t=time.time()
    numpy.apply_along_axis(find1,-1,v,1)
    print('find1',time.time()-t)

    t=time.time()
    find2(v,1)
    print('find2',time.time()-t)

산출물

(1, 100000000)
('find1', 0.25300002098083496)
('find2', 0.2780001163482666)
(10000, 10000)
('find1', 0.46200013160705566)
('find2', 0.27300000190734863)
(1000000, 100)
('find1', 20.98099994659424)
('find2', 0.3040001392364502)
(10000000, 10)
('find1', 206.7590000629425)
('find2', 0.4830000400543213)

그렇긴 하지만, C로 작성된 발견은 적어도 이러한 접근법 중 하나보다 조금 더 빠를 것입니다.

이것은 어떻습니까?

import numpy as np
np.amin(np.where(array==item))

당신은 당신의 배열을 비밀로 할 수 있습니다.list그리고 그것을 사용합니다.index()방법:

i = list(array).index(item)

제가 알기로는 이것은 C 컴파일 방식입니다.

언급URL : https://stackoverflow.com/questions/7632963/numpy-find-first-index-of-value-fast