map :: lower_bound（）はPythonのdictクラスに相当しますか？

Question

私はキーの下限をフェッチする必要があるコードを書いています（簡単にするために、コレクションの最小のキーの下にあるキーを無視してください）。

C++では、std :: map（最も類似したデータ型として）を使用して、単純にlower_bound（）を使用してイテレータを返します。

は何私のPythonfooは、その素晴らしいではありませんが、私は（場合には、Pythonはすでにこれを行う方法を持っていない）、これはラムダ関数をうまく利用することであろうと推測しています...

指定されたインデックスの下限キーを取得するPythonの方法？

質問があまりにも抽象的である場合には、これは私が実際にやろうとしていますものです：

私は日付によってインデックスさ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-treeだと思います。

Answer 2

Pythonの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 []