np.searchsorted

 

 

 

Numpy에 있는 함수인 searchsorted에 대해 알아보자.

 

Numpy 기술 문서에 따르면,

'Find indices where elements should be inserted to maintain order.' 즉, 순서를 유지하면서 해당 요소가 삽입될 위치를 찾는 함수이다.

 

이 함수를 쓰게 된 경위는 $e_{i,j} = \frac{K(n_{\mathrm{cal}}+1) I(S_{n+i,j} \ge T_{i}^{+})}{\sum_{l=1}^{n_{\mathrm{cal}}}\sum_{j^{\prime}=1}^{K} I(S_{n_{\mathrm{tr}} + l,j^{\prime}} \ge T_{i}^{-}) + K}$을 구하기 위해서인데 이때 $T_i^{+}$와 $T_i^{-}$는 stopping times로 다음과 같다.

 

$T_i^{+} = \inf \left\{ t \in \mathbb{R} : \widehat{\text{FDP}}_i^+(t) \leq \tilde{\alpha} \right\}, \text{ where }
\widehat{\mathrm{fdp}}_{i}^{+} (t) = \frac{m-1}{n_{\mathrm{cal}}+1} \frac{ \sum_{k=1}^{n_{\mathrm{cal}}} \sum_{j=1}^{K} I(S_{n_{\mathrm{tr}} + k,j} \ge t) + K}{1 \vee \sum_{l \in [m]\setminus \{i\}} \sum_{j=1}^{K} I(S_{n + l,j} \ge t)}$,

 

$T_i^{-} = \inf \left\{t \in \mathbb{R} : \widehat{\text{FDP}}_i^-(t) \leq \tilde{\alpha} \right\}, \text{ where }
\widehat{\mathrm{FDP}}_{i}^{-} (t) = \frac{m-1}{n_{\mathrm{cal}}+1} \frac{ \sum_{k=1}^{n_{\mathrm{cal}}} \sum_{j=1}^{K} I(S_{n_{\mathrm{tr}} + k,j} \ge t)}{1 \vee \sum_{l \in [m]\setminus \{i\}} \sum_{j=1}^{K} I(S_{n + l,j} \ge t)}$

 

여기서 왜 우리가 searchsorted함수를 사용해야하는 이유에 대해 알 수 있다. 위 Stopping times인 $T_i^{+}$와 $T_i^{-}$를 구하기 위해서는 실수 범위 내에서 특정 조건을 만족하는 값을 찾아야 한다. 실제 계산 과정에서는 관측된 수많은 점수(Scores)를 후보군으로 두고 비교 연산을 수행하게 되는데 이때 일반적인 반복문(Loop) 대신 Numpy의 searchsorted 함수를 사용하면 연산 효율을 극대화할 수 있다.

왜냐하면 np.searchsorted는 내부적으로 이진 탐색(Binary Search) 알고리즘을 사용하기 때문에, 이미 정렬된 배열에서 특정 값의 위치를 $O(\log n)$의 시간 복잡도로 매우 빠르게 찾아내기때문이다.

side="left" 옵션과 Infimum의 관계

예를 들어 위 수식에서 $T_i^{+}$는 다음과 같이 인피멈(Infimum, 하한)으로 정의된다.

$$T_i^{+} = \inf \left\{ t \in \mathbb{R} : \widehat{\text{FDP}}_i^+(t) \leq \tilde{\alpha} \right\}$$

이는 조건을 만족하는 $t$ 값들 중 가장 작은 값을 찾겠다는 의미이다. 

• 가장 왼쪽 위치 탐색: side="left" 옵션은 찾고자 하는 값이 삽입될 수 있는 가장 왼쪽 인덱스를 반환한다. 즉, 배열이 오름차순으로 정렬되어 있을 때 FDP 조건을 만족하기 시작하는 '가장 첫 번째' 지점을 즉시 찾아낸다.
• 결과적으로 조건을 만족하는 가장 작은 인덱스를 찾는 것은, 집합의 하한(Infimum)을 찾는 것과 논리적으로 동일하다.
• 기능 응용: a=[1,2,2,3,3,4,5]의 순서를 망치지 않고 b=[3,4]가 들어갈 index를 찾아보자. 아래 코드에서 index는 각각 3,5가 위와 같이 나온다. `len(a)-np.searchsorted(a,b,side="left")`을 사용하면 리스트 a의 원소들 중에 리스트 b에 있는 원소들 보다 크거나 같은 원소들의 갯수가 list형식으로 반환된다.

a=[1,2,2,3,3,4,4,5]
b=[3,4]

np.searchsorted(a,b,side="left")

#array([3, 5])

len(a)-np.searchsorted(a,b,side="left")

#array([5, 3])

 

all_scores = np.sort(np.unique(np.concatenate([s_ref_flat, s_te_flat])))[::-1]
            
# 각 그룹 i별로 '나를 제외한 다른 그룹의 점수'를 빠르게 계산하기 위해
# 전체 s_te에 대한 카운트 테이블을 미리 만듭니다.
count_ref = (len(s_ref_flat) - np.searchsorted(s_ref_flat, all_scores, side='left'))
count_te_total = (len(s_te_flat) - np.searchsorted(np.sort(s_te_flat), all_scores, side='left'))

T_plus = np.full(m, all_scores[0])
T_minus = np.full(m, all_scores[0])

# 각 그룹별로 최적의 t를 찾기 위해 벡터화된 연산 수행
# s_te[i]의 값들이 all_scores의 어디에 위치하는지 인덱스 맵 생성
for i in range(m):
    s_te_i = s_te[i]
    # count_other_te(t) = count_te_total(t) - count_in_group_i(t)
    count_in_i = (len(s_te_i) - np.searchsorted(np.sort(s_te_i), all_scores, side='left'))
    count_other_te = count_te_total - count_in_i
    denom = np.maximum(1, count_other_te)

    # FDP 조건 만족하는 인덱스 찾기
    fdp_plus = ((m - 1) / (n_cal + 1)) * (count_ref + self.K) / denom
    fdp_minus = ((m - 1) / (n_cal + 1)) * count_ref / denom

    plus_idx = np.where(fdp_plus <= self.alpha_tilde)[0]
    minus_idx = np.where(fdp_minus <= self.alpha_tilde)[0]

    if plus_idx.size > 0: T_plus[i] = all_scores[plus_idx[0]]
    if minus_idx.size > 0: T_minus[i] = all_scores[minus_idx[0]]

# e-values 계산 (벡터화)
e_values = np.zeros((m, self.K))
# T_minus에 따른 분모 계산 최적화
denoms = (len(s_ref_flat) - np.searchsorted(s_ref_flat, T_minus, side='left')) + self.K

for i in range(m):
    mask = (s_te[i] >= T_plus[i])
    e_values[i, mask] = (self.K * (n_cal + 1)) / denoms[i]

 

 

Supremum과 side="right"

반대로 만약 슈프리멈(Supremum, 상한)을 찾아야 하는 경우에는 side="right" 옵션을 사용하면 된다.

 

출처 : 넘파이 기술문서 내 searchsorted함수https://numpy.org/doc/2.2/reference/generated/numpy.searchsorted.html,gemini