파이썬에서는 정렬 된 목록에서 첫 번째 값의 인덱스가 임계 값보다 큰 것을 어떻게 알 수 있습니까?

Question

파이썬에서 정렬 된 목록에서 첫 번째 값의 인덱스가 임계 값보다 큰 것을 어떻게 알 수 있습니까?

이 작업을 수행하는 여러 가지 방법 (선형 검색, 손으로 직접 작성한 이분법 등)을 생각할 수 있지만이를 수행하는 데있어 효율적인 방법을 찾고 있습니다. 아마 꽤 일반적인 문제이기 때문에, 나는 경험있는 SOers가 도울 수 있다고 확신합니다!

감사합니다.

Answer 1

bisect을 살펴보십시오.

import bisect 

l = [1, 4, 9, 16, 25, 36, 49, 64, 81, 100] 

bisect.bisect(l, 55) # returns 7 

선형 검색과 비교 :

timeit bisect.bisect(l, 55) 
# 375ns 


timeit next((i for i,n in enumerate(l) if n > 55), len(l)) 
# 2.24us 


timeit next((l.index(n) for n in l if n > 55), len(l)) 
# 1.93us 

Answer 2

당신 수도 itertools를 사용하여 열거/발전기 접근 방식보다 더 나은 시간을 얻을; 나는 itertools가 우리 모두의 성능에 대해 기본 알고리즘의보다 빠른 구현을 제공한다고 생각한다. 그러나 bisect는 여전히 빠를 수 있습니다.

from itertools import islice, dropwhile 

threshold = 5 
seq = [1,4,6,9,11] 
first_val = islice(dropwhile(lambda x: x<=threshold, seq),0,1) 
result = seq.index(first_val) 

나는 지금까지 관용구/속도로, 여기에 표시된 양분 접근 방식과 문서의 예에 질문에 대해 나열된 하나의 차이에 대해 궁금합니다. 그들은 값을 찾는 접근법을 보여 주지만 첫 줄까지 잘린 경우 인덱스를 반환합니다. 나는 그것이 "bisect_right"대신에 "bisect_right"라고 불리는 이래로 아마도 한 방향에서만 보일 것이라고 생각합니다. 귀하의 목록이 정렬되어 있고 귀하가보다 큼을 원한다면, 이것은 최고의 검색 경제 일 수 있습니다.

from bisect import bisect_right 

def find_gt(a, x): 
    'Find leftmost value(switching this to index) greater than x' 
    return bisect_right(a, x) 

흥미로운 질문입니다.