ソートされたリストのインデックスを一定時間で見つけよう

Question

リストに追加してカスタムコンパレータで並べ替えるカスタムオブジェクトがあります。次に、これらのオブジェクトのいくつかのサブセットの2番目のリストを持っています。最初のリストのインデックスが必要です（私のコンパレータで定義されたものと同じオブジェクトを見つけることができます）。リストがソートされるとき、これらのオブジェクトはこのオブジェクトの直前または直後のオブジェクトでなければなりませんが、どれくらい同じ（おそらく2〜3）になるかは事前にわかりません。

ソートされたオブジェクトのリストがかなり大きいので、一定の時間内にこのルックアップが必要です。私は明らかにlist.index（）を使うことができますが、それはO（N）になります。私はもっとうまくいくと思います。私の最初の考えは、二重にリンクされたリストを使用することでしたが、それを自分で実装する必要があるように見えます。

Pythonで二重リンクされたリストの実装はありますか？または、この問題のより良い代替手段がありますか？また、私は現在Python2.5を使用していますので、私のバージョンを更新することはできませんが、私のバージョンが限られていても、私はまだその解決策について聞いています。追加のO（N）のストレージの価格については

Answer 1

、あなたがソートされたリストのリストインデックスをバックアップする辞書を作成することができます：

index_map = dict((e,i) for (i,e) in enumerate(sorted_list)) 

これはあなたの位置のためのO（1）参照を与えるだろうあなたの2番目のリストの項目。

sorted_listの要素がカスタムオブジェクトである場合、@mseifertが指摘するように、このアプローチは、__eq__が正しく定義され、ハッシュ可能であるオブジェクトに依存します。