0

次のように、キーのUNIXエポックタイムスタンプを持つdictがあります。

lookup_dict = {
    1357899: {} #some dict of data
    1357910: {} #some other dict of data
}

何百万、何百万、何百万ものエントリを除いて、あなたは知っています。このdictを何度も何度もサブセット化したいと思います。理想的には、Rでできるようなものを次のように記述できるようにしたいと思います。

lookup_value = 1357900
dict_subset = lookup_dict[key >= lookup_value]
# dict_subset now contains {1357910: {}}

しかし、私は告白します。これが、Pythonがすべての行を反復処理することなく、何らかの方法で実行できることであるという実際の証拠を見つけることはできません。Pythonを正しく理解している場合（そして理解していない場合もあります）、フォームのキールックアップkey in dictはバイナリ検索を使用するため、非常に高速です。dictキーでバイナリ検索を行う方法はありますか？

4

2 に答える 2

2

反復せずにこれを行うには、ソートされた順序でキーが必要になります。>= lookup_value次に、それぞれをチェックするのではなく、最初のバイナリ検索を実行する必要があります>= lookup_value。

サードパーティのライブラリを使用する場合は、そこにたくさんあります。頭に浮かぶ最初の2つはbintrees、（C ++、Javaなどのような赤黒木を使用する）とblist（B +ツリーを使用する）です。たとえば、を使用するとbintrees、次のように簡単になります。

dict_subset = lookup_dict[lookup_value:]

そして、これはあなたが望むのと同じくらい効率的です—基本的に、それはO(log N)そのサブセットを使用するコストに加えて単一の検索を追加します。（もちろん、通常、そのサブセットでやりたいことは、すべてを繰り返すことです。これは、とにかくO（N）になります…しかし、何か別のことをしている場合や、サブセットが1000000のうち10キーしかない場合もあります。）

もちろん、トレードオフがあります。ツリーベースのマッピングへのランダムアクセスは、「通常はO（1）」ではなくO（log N）です。また、キーは明らかにハッシュ可能ではなく完全に順序付けられている必要があります（そして、それを自動的に検出して適切なエラーメッセージを表示するのは非常に困難です）。

これを自分で作成したい場合は、できます。必ずしも木は必要ありません。。と一緒に並べ替えlistられたキーだけdictです。JonClementsが提案したように、stdlib内listのモジュールでを維持できます。bisectまとめてbisectソート済みリストオブジェクトを作成することもできます。または、ActiveStateまたはPyPIのレシピの1つを入手して、それを実行することをお勧めします。次に、ソートされたリストとdict一緒に1つのオブジェクトにラップできるため、一方を誤って更新せずにもう一方を更新することはありません。そして、必要に応じて、インターフェイスを拡張して、と同じくらい素敵にすることができbintreesます。

于 2013-02-15T01:27:40.510 に答える
0

次のコードを使用するとうまくいきます

some_time_to_filter_for = # blah unix time
# Create a new sub-dictionary
sub_dict = {key: val for key, val in lookup_dict.items() 
            if key >= some_time_to_filter_for}

基本的に、辞書内のすべてのキーを繰り返し処理し、フィルターで除外する時間を与えて、その値以上のすべてのキーを取得し、新しい辞書に配置します。

于 2013-02-15T00:54:55.020 に答える