map :: lower_bound()는 파이썬의 dict 클래스와 동일합니까?

Question

간단히하기 위해 키의 하한을 가져와야하는 코드를 작성 중입니다. 컬렉션의 가장 작은 키 아래에있는 키를 무시하십시오.

C++에서 std :: map (가장 유사한 데이터 유형)을 사용하면 lowererbound()를 사용하여 반복기를 반환합니다.

내 Pythonfoo는 잘되지 않습니다,하지만 난이

은 무엇인가 ... 람다 기능을 잘 사용하는 것 (경우에 파이썬은 이미이 일을하는 방법이 없음) 추측하고있다 주어진 인덱스에 대한 하위 바운드 키를 검색하는 Python 방식?

나는 날짜에 의해 색인 파이썬 딕셔너리 있습니다

이 경우 문제는 이것이 내가 실제로 할 노력하고 무엇을, 너무 추상적이다. 내가 날짜를 사용하여 사전을 조회하고 지정된 키의 하한과 연관된 값을 리턴 할 수 있기를 원합니다.

발췌문은 다음과 같습니다

이

mymap = { datetime.date(2007, 1, 5): 'foo', 
      datetime.date(2007, 1, 10): 'foofoo', 
      datetime.date(2007, 2, 2): 'foobar', 
      datetime.date(2007, 2, 7): 'foobarbar' } 

mydate = datetime.date(2007, 1, 7) 

# fetch lbound key for mydate from mymap 
def mymap_lbound_key(orig): 
    pass # return the lbound for the key 

난 정말 더 나은 대안이없는 경우를 제외하고, 키를 제공 = 첫 번째 키 <을 찾고, 키를 통해 루프 싶지 않아 ... 아직

Answer 1

"하한선"이 무엇인지 모릅니다 : 쿼리 날짜 전후의 최신 날짜?

어쨌든 사전에 키의 고유 한 순서가 지정되어 있지 않으므로 다른 구조가 필요합니다. 키를 정렬 된 상태로 유지하고 빠른 검색을 허용하는 구조에 키를 저장하십시오.

가장 간단한 해결책은 (날짜, 값) 목록에을 정렬하여 저장하고 이진 검색을 통해 원하는 지역을 확대하는 것입니다. 더 나은 성능이 필요하거나 필요하다면 b- 트리가 필요하다고 생각합니다.

Answer 2

파이썬의 dict 클래스에는이 기능이 없습니다. 직접 작성해야합니다. 키가 이미 정렬되어 있다면 편리 할 것입니다. 따라서 바이너리 검색을 수행하고 모든 항목을 반복하지 않아도됩니까? 이 글에서는 blist 패키지의 sorteddict 클래스에 대해 살펴 보겠습니다. http://pypi.python.org/pypi/blist/

Answer 3

날짜가 있다면 어떻게 든 오버로드하여 bisect module을 볼 수 있습니다.

최소한의 정수 코딩 예 :

from bisect import bisect_left 

data = { 
    200 : -100, 
    -50 : 0, 
    51 : 100, 
    250 : 200 
} 

keys = list(data.keys()) 

print data[ keys[ bisect_left(keys, -79) ] ] 

Answer 4

나는 C++지도를 닮은 무언가를 할 때, 나는 SortedDict를 사용합니다. irange을 사용하면 지정된 키가 하한 인 키에 반복자를 얻을 수 있습니다. 이는 내가 생각하기에 std::lower_bound이 어떻게 작동하는지입니다.

번호 :

from sortedcontainers import SortedDict 
sd = SortedDict() 
sd[105] = 'a' 
sd[102] = 'b' 
sd[101] = 'c' 

#SortedDict is sorted on insert, like std::map 
print(sd) 

# sd.irange(minimum=<key>) returns an iterator beginning with the first key not less than <key> 
print("min = 100", list(sd.irange(minimum=100))) 
print("min = 102", list(sd.irange(minimum=102))) 
print("min = 103", list(sd.irange(minimum=103))) 
print("min = 106", list(sd.irange(minimum=106))) 

출력 :

SortedDict(None, 1000, {101: 'c', 102: 'b', 105: 'a'}) 
min = 100 [101, 102, 105] 
min = 102 [102, 105] 
min = 103 [105] 
min = 106 []