정렬 된 목록에서 다음 하위 항목 찾기

Question

내가 분류 된 플로트 목록을 가지고 있다고 가정 해 봅시다. 이제 주어진 값의 다음 하위 항목의 인덱스를 얻고 싶습니다. 일반적인 for-loop aprroach는 O (n)의 복잡성을 가지고 있습니다. 목록이 정렬되기 때문에 O (log n)로 색인을 가져올 수있는 방법이 있어야합니다.

내 O (n)의 접근 방식 :

index=0 
for i,value in enumerate(mylist): 
    if value>compareValue: 
     index=i-1 

는 O (N 로그)에서 그 문제를 해결하기위한 데이터 형식이 있습니까?

이 이

Answer 1

는 당신은 당신이 찾고있는 객체의 인덱스를 얻을 하부 항목을 얻을 아래에있는 인덱스를 얻을 수 배열/목록 이진 검색을 수행 할 수 있습니다 (주어진

안부 세바스찬이 실제로 낮은 항목입니다!).

은 참조 : Binary search (bisection) in Python

이 어떤지 때 comparing floating point numbers주의!

Answer 2

데이터 유형에 관한 질문의 일부에 답하려면 : 일반적으로 O (log n) 시간에 물건을 찾는 데 가장 적합한 데이터 유형은 (삽입 및 삭제시 O (1) 성능을 유지하면서) 바이너리 트리입니다 . 일련의 좌우 결정을하면 선형 목록에서 이진 탐색을 수행하는 것과 매우 유사하지만 개념 상 직관적으로 (IMO)보다 쉽습니다.

그렇긴하지만, 파이썬에 대해 내가 아는 것에서부터, 바이너리 트리는 언어의 표준 라이브러리에없는 것 같습니다. 응용 프로그램의 경우이 목적을위한 구현 만 포함하면 아무런 이점이 없습니다.

마지막으로 정렬 된 목록에서 이진 트리와 이진 검색을 사용하면 검색을 한 단계 단축 할 수 있습니다. 키 항목을 검색 한 다음 이전 항목으로 다시 이동할 필요가 없습니다. 대신, 모든 비교 단계에서 키 값을 만나면 너무 큰 것처럼 행동하십시오. 그러면 다음 작은 값으로 검색이 끝납니다. 주의 깊게 살펴보면 바트가 언급 한 "거의 동일한 부동 소수점 값"문제에도 도움이 될 수 있습니다.

Answer 3

어때 대략 bisect?

>>> import bisect 
>>> float_list = [1.0, 1.3, 2.3, 4.5] 
>>> i = bisect.bisect_left(float_list, 2.5) 
>>> index = i - 1 
>>> index 
2 

당신은보다 작거나 별도로 목록 (이 경우 index == -1)에서 가장 낮은/왼쪽 값과 동일한 검색 값의 경우를 처리해야 할 수도 있습니다.

평등의 경우에 원하는 색인에 따라 bisect_right을 대신 사용해야 할 수도 있습니다.

Answer 4

bisect 모듈을 사용하십시오. 함수

bisect.bisect_left(mylist, compareValue) 

은 정렬 된 순서를 유지하기 위해 목록의 항목에 적절한 삽입 지점을 반환합니다.

Answer 5

import bisect 

def next_lower_value(values_list, input_value): 
    index= bisect.bisect_left(values_list, input_value) 
    if index == 0: # there's not a "next lower value" 
     raise NotImplementedError # you must decide what to do here 
    else: 
     return values_list[index - 1] 

>>> l= [11, 15, 23, 28, 45, 63, 94] 
>>> next_lower_value(l, 64) 
63 
>>> next_lower_value(l, 63) 
45 
>>> next_lower_value(l, 1000) 
94 
>>> next_lower_value(l, 1) 
Traceback (most recent call last): 
    File "<pyshell#29>", line 1, in <module> 
    next_lower_value(l, 1) 
    File "<pyshell#26>", line 4, in next_lower_value 
    raise NotImplementedError # you must decide what to do here 
NotImplementedError 

당신이 인덱스이 아닌 다음으로 낮은 값을 요구하기 때문에, index - 1 대신 values_list[index - 1] 반환하는 기능 next_lower_value을 변경합니다.

Answer 6

내가이 권리를 읽는다면 다음 하위 항목은 목록의 x보다 작거나 같은 첫 번째 항목입니다.

def find_le(a, x): 
    'Find rightmost value less than or equal to x' 
    i = bisect_right(a, x) 
    if i: 
     return a[i-1] 
    raise ValueError