python - numpy.median.reduceat에 대한 빠른 대안




performance numpy-ufunc (3)

네이티브 numpy로는 할 수없는 계산 속도를 높이려면 비 아이디 오틱 numpy 코드를 작성해야하는 경우가 있습니다.

numba 는 파이썬 코드를 저수준 C로 컴파일합니다. 많은 numpy 자체는 일반적으로 C만큼 빠르기 때문에 문제가 numpy를 사용한 네이티브 벡터화에 적합하지 않은 경우에 유용합니다. 이것은 하나의 예입니다 (인덱스가 연속적이고 정렬되어 있다고 가정하고 예제 데이터에도 반영됨).

import numpy as np
import numba

# use the inflated example of roganjosh https://stackoverflow.com/a/58788534
data =  [1.00, 1.05, 1.30, 1.20, 1.06, 1.54, 1.33, 1.87, 1.67]
index = [0,    0,    1,    1,    1,    1,    2,    3,    3] 

data = np.array(data * 500) # using arrays is important for numba!
index = np.sort(np.random.randint(0, 30, 4500))               

# jit-decorate; original is available as .py_func attribute
@numba.njit('f8[:](f8[:], i8[:])') # explicit signature implies ahead-of-time compile
def diffmedian_jit(data, index): 
    res = np.empty_like(data) 
    i_start = 0 
    for i in range(1, index.size): 
        if index[i] == index[i_start]: 
            continue 

        # here: i is the first _next_ index 
        inds = slice(i_start, i)  # i_start:i slice 
        res[inds] = data[inds] - np.median(data[inds]) 

        i_start = i 

    # also fix last label 
    res[i_start:] = data[i_start:] - np.median(data[i_start:])

    return res

그리고 다음은 IPython의 %timeit 마술을 사용하는 타이밍입니다.

>>> %timeit diffmedian_jit.py_func(data, index)  # non-jitted function
... %timeit diffmedian_jit(data, index)  # jitted function
...
4.27 ms ± 109 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
65.2 µs ± 1.01 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

문제의 업데이트 된 예제 데이터를 사용하면 이러한 숫자 (예 : Python 함수의 런타임 대 JIT 가속 함수의 런타임)는 다음과 같습니다.

>>> %timeit diffmedian_jit.py_func(data, groups) 
... %timeit diffmedian_jit(data, groups)
2.45 s ± 34.4 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
93.6 ms ± 518 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

이것은 가속 코드를 사용하여 작은 경우에는 65 배, 큰 경우에는 26 배의 속도 향상 (물론 느린 루프 코드와 비교)에 해당합니다. 또 다른 단점은 (기본 numpy를 사용한 일반적인 벡터화와 달리)이 속도를 달성하기 위해 추가 메모리가 필요하지 않다는 것입니다. 이것은 모두 실행되고 결국 최적화되고 컴파일 된 저수준 코드에 관한 것입니다.

위의 함수는 numpy int 배열이 기본적으로 int64 라고 가정하지만 실제로 Windows에서는 그렇지 않습니다. 따라서 대안은 적절한 적시 컴파일을 트리거하여 numba.njit 호출에서 서명을 제거하는 것입니다. 그러나 이것은 첫 번째 실행 중에 함수가 컴파일되어 타이밍 결과와 충돌 할 수 있음을 의미합니다 (대표 데이터 유형을 사용하여 수동으로 한 번 함수를 한 번 실행하거나 첫 번째 타이밍 실행이 훨씬 느리다는 것을 받아 들일 수 있음) 무시하십시오). 이것은 미리 컴파일을 트리거하는 서명을 지정하여 방지하려고했던 것입니다.

어쨌든, 적절한 JIT 케이스에서 우리가 필요로하는 데코레이터는

@numba.njit
def diffmedian_jit(...):

jit 컴파일 된 함수에 대해 위에서 보여준 타이밍은 함수가 컴파일 된 후에 만 ​​적용됩니다. 이는 정의시 (열심히 컴파일하거나 명시 적 서명이 numba.njit 전달 될 numba.njit ) 또는 첫 번째 함수 호출 (지연 컴파일이 numba.njit 서명이 numba.njit 으로 전달되지 않을 때)에서 발생합니다. 함수가 한 번만 실행될 예정이라면이 방법의 속도에 대해 컴파일 시간도 고려해야합니다. 컴파일 + 실행의 총 시간이 컴파일되지 않은 런타임 (기본 파이썬 함수가 매우 느린 위의 경우에 해당)보다 적은 경우 일반적으로 함수를 컴파일하는 것이 좋습니다. 컴파일 된 함수를 여러 번 호출 할 때 주로 발생합니다.

max9111 이 주석에서 언급했듯이 max9111 중요한 기능 중 하나는 jit cache 키워드 입니다. cache=Truenumba.jit 전달하면 컴파일 된 함수가 디스크에 저장되므로 주어진 파이썬 모듈을 다음에 실행하는 동안 함수가 다시 컴파일되지 않고로드되어 장기적으로 런타임을 절약 할 수 있습니다.

이 답변 과 관련하여 요소 수가 다른 그룹을 갖는 배열에서 중간 값을 계산하는 빠른 방법이 있습니까?

예 :

data =  [1.00, 1.05, 1.30, 1.20, 1.06, 1.54, 1.33, 1.87, 1.67, ... ]
index = [0,    0,    1,    1,    1,    1,    2,    3,    3,    ... ]

그리고 그룹당 중앙값과 숫자의 차이를 계산하고 싶습니다 (예 : 그룹 0 중앙값은 1.025 이므로 첫 번째 결과는 1.00 - 1.025 = -0.025 ). 따라서 위 배열의 결과는 다음과 같습니다.

result = [-0.025, 0.025, 0.05, -0.05, -0.19, 0.29, 0.00, 0.10, -0.10, ...]

np.median.reduceat 가 존재하지 않기 때문에 (아직)이를 달성하는 또 다른 빠른 방법이 있습니까? 내 배열에는 수백만 행이 포함되므로 속도가 중요합니다!

인덱스는 연속적이고 정렬 된 것으로 가정 할 수 있습니다 (만약 그렇지 않으면 변환하기 쉽습니다).

성능 비교를위한 데이터 예 :

import numpy as np

np.random.seed(0)
rows = 10000
cols = 500
ngroup = 100

# Create random data and groups (unique per column)
data = np.random.rand(rows,cols)
groups = np.random.randint(ngroup, size=(rows,cols)) + 10*np.tile(np.arange(cols),(rows,1))

# Flatten
data = data.ravel()
groups = groups.ravel()

# Sort by group
idx_sort = groups.argsort()
data = data[idx_sort]
groups = groups[idx_sort]

양수 bin / 인덱스 값에 대해 binned-median을 얻는 NumPy 기반 접근법은 다음과 같습니다.

def bin_median(a, i):
    sidx = np.lexsort((a,i))

    a = a[sidx]
    i = i[sidx]

    c = np.bincount(i)
    c = c[c!=0]

    s1 = c//2

    e = c.cumsum()
    s1[1:] += e[:-1]

    firstval = a[s1-1]
    secondval = a[s1]
    out = np.where(c%2,secondval,(firstval+secondval)/2.0)
    return out

빼기의 특정 사례를 해결하려면-

def bin_median_subtract(a, i):
    sidx = np.lexsort((a,i))

    c = np.bincount(i)

    valid_mask = c!=0
    c = c[valid_mask]    

    e = c.cumsum()
    s1 = c//2
    s1[1:] += e[:-1]
    ssidx = sidx.argsort()
    starts = c%2+s1-1
    ends = s1

    starts_orgindx = sidx[np.searchsorted(sidx,starts,sorter=ssidx)]
    ends_orgindx  = sidx[np.searchsorted(sidx,ends,sorter=ssidx)]
    val = (a[starts_orgindx] + a[ends_orgindx])/2.
    out = a-np.repeat(val,c)
    return out

한 가지 방법은 여기에서 Pandas 를 순수하게 사용하여 groupby 사용하는 것입니다. DF를 만드는 데 오버 헤드가 있기 때문에 타이밍을 더 잘 이해하기 위해 입력 크기를 약간 늘 렸습니다.

import numpy as np
import pandas as pd

data =  [1.00, 1.05, 1.30, 1.20, 1.06, 1.54, 1.33, 1.87, 1.67]
index = [0,    0,    1,    1,    1,    1,    2,    3,    3]

data = data * 500
index = np.sort(np.random.randint(0, 30, 4500))

def df_approach(data, index):
    df = pd.DataFrame({'data': data, 'label': index})
    df['median'] = df.groupby('label')['data'].transform('median')
    df['result'] = df['data'] - df['median']

다음과 같은 timeit .

%timeit df_approach(data, index)
5.38 ms ± 50.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

동일한 표본 크기 에 대해 Aryerez 의 dict 접근 방식은 다음 과 같습니다.

%timeit dict_approach(data, index)
8.12 ms ± 3.47 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

그러나 입력을 10 배 더 늘리면 타이밍이 다음과 같이됩니다.

%timeit df_approach(data, index)
7.72 ms ± 85 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%timeit dict_approach(data, index)
30.2 ms ± 10.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

그러나 일부 안정성을 희생하면서 Divakar 는 순수한 Divakar 사용하여 대답합니다.

%timeit bin_median_subtract(data, index)
573 µs ± 7.48 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

새로운 데이터 세트에 비추어 볼 때 (실제 시작시 설정해야 함) :

%timeit df_approach(data, groups)
472 ms ± 2.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit bin_median_subtract(data, groups) #https://.com/a/58788623/4799172
3.02 s ± 31.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit dict_approach(data, groups) #https://.com/a/58788199/4799172
<I gave up after 1 minute>

# jitted (using @numba.njit('f8[:](f8[:], i4[:]') on Windows) from  https://.com/a/58788635/4799172
%timeit diffmedian_jit(data, groups)
132 ms ± 3.12 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)




numpy-ufunc