8

私が辞書を持っているとしましょう

{1:5, 2:5, 4:5}

キーと値のペアを追加した場合に3:5、キーがソートされた順序になるように辞書に入力するようなデータ構造はありますか？すなわち

{1:5, 2:5, 3:5, 4:5}

私はを知ってcollections.OrderedDict()いますが、これはキーが追加された順序でのみ保持されます（これは現在私には十分ではありません）。

通常の辞書を使用する必要はなく、最小のキーを取得するdic = {}ために使用する必要があります。sorted(dic)[0]むしろsorted_dict[0]タイプ機能が欲しいです。
これは、通常のディクショナリを使用する場合、ディクショナリにペアを継続的に追加しているため、ソートを複数回呼び出す必要があるためです。

編集：私が気にするのは最小と最大のキーだけでなく、この辞書も定期的に印刷する必要があることを述べておかなければなりません...

4

3 に答える 3

5

ディクショナリにキーを継続的に追加および削除する場合は、問題に適切なデータ構造を使用するものが本当に必要です。ハッシュテーブル（またはSortedOrderedDict-typeレシピの場合のように、ハッシュテーブルとリスト）ではなく、バランスの取れたツリー（またはスキップリストのような同等のもの）。

PyPIを見回すと、いくつかのオプションが見つかります。私の推薦はですblist。そのデータ構造は他のいくつかほど最適ではないかもしれませんが（B +ツリーはバイナリツリーよりもはるかに広いため）、遭遇するほとんどすべてのユースケースにはおそらく十分です。また、十分にテストされたパフォーマンス保証を含む、完全で十分にテストされたインターフェースを備えています。そして、それは他の深刻なプロジェクトによってかなり使用されています。

ツリーのパフォーマンスが本当に重要であるまれなケースの1つを扱っている場合は、さまざまな赤黒木、スプレーツリー、スキップリストなどの実装を確認する必要があります。私はbintrees以前に使用しましたが、これは優れたインターフェイスを備えています（たとえば、インデックスでキーと値にアクセスでき、ツリーをスライスしたり、ツリーをのように扱ったりすることもできます。作成dict者は、考えられるすべてのあいまいさを熟考して回避しました。 ）、しかし私はそれを真剣にパフォーマンステストしていません。

または、キーと値が実際にはすべて小さい整数である場合は、Cythonを使用してC++map<int, int>をPythonicインターフェイスでラップすることを検討することをお勧めします。（ C ++の上に完全なインターフェイスを提供することは完全にmapは不可能ですが、とにかくそれを必要としないことがよくあります。）または、代わりに、保存して比較するように実装の1つを変更しbintrees.FastRBTreeます。longPyObject*

一方、辞書を一度に作成して使用する場合は、はるかに簡単な答えがあります。並べ替えて、に貼り付けOrderedDictます。そうすれば、stdlibの外には何も必要ありません。

sorted_dict = collections.OrderedDict(sorted(d.iteritems()))

別の回答へのコメントから、「新しいモジュールをインストールする権限がありません...」と言います。

まず、それが本当に真実であることを確認してください。おそらく、ユーザーのsite-packagesディレクトリにモジュールをインストールする権限があります。または、virtualenvがインストールされているか、組み込みの3.3を使用している場合はvenv、さらに良いことに、venvを作成してそれにモジュールをインストールする権限があります。

blistただし、その場合は、ファイルを// bintreeswhateverからプロジェクトにコピーする必要があります。

遭遇する可能性のある問題は、これらのパッケージのほとんどにC拡張モジュールが含まれていることです。つまり、それらをビルドできる必要があります（まあ、build_ext -iそれら）。システムにPython開発ファイルとコンパイラツールチェーンがインストールされていない場合、それを行うことはできません。その場合、あなたは最高の純粋なPythonソリューションを探しています。bintrees遅いことを除いて、通常のC-extension実装と同じ純粋なPython実装が付属しています。もちろん、それでもO（log N）ですが、定数係数の方がはるかに高くなります。Nが十分に大きい場合でも、それは大きな勝利です。そうでない場合は、そうではない可能性があります。

これのいずれかの部分が合理的に聞こえるが、ユーザーごとのサイトパッケージまたは仮想環境のセットアップ、プロジェクトへのモジュールのインプレースでのコピー、拡張機能のインプレースでの構築などの支援が必要な場合は、おそらく検索する必要があります既存の質問については、新しい質問が見つからない場合は質問してください（インストールの問題の専門家である種類の人々が必ずしもデータ構造の専門家であるとは限らず、これを読んでいない可能性があるためです。質問）。

于 2013-03-19T05:29:59.227 に答える
3

このレシピを試してください— http://code.activestate.com/recipes/576998-sorted-dictionary/

stdlibbisectモジュールを使用してキーをソートし続けます。

于 2013-03-19T05:23:35.880 に答える
1

パーティーに1年以上遅れましたが、sortedcontainersモジュールを提案したいと思いました。blistやbintreesと同様に、ソートされた順序でキーを維持するSortedDictデータ型を提供します。それらのモジュールとは異なり、純粋なPythonで記述されており、実際には高速です。SortedDictはインデックス作成もサポートしています。最小/最大の検索は、実際にはO（1）時間で行われます。

純粋なPythonなので、pipを使用したインストールは簡単です。

pip install sortedcontainers

次に、SortedDictをインポートするだけです。

In [1]: from sortedcontainers import SortedDict

In [2]: d = SortedDict({1:5, 2:5, 4:5})

In [3]: d
Out[3]: SortedDict({1: 5, 2: 5, 4: 5})

In [4]: d[3] = 5

In [5]: d
Out[5]: SortedDict({1: 5, 2: 5, 3: 5, 4: 5})

pipを使用してインストールするのが難しい場合、またはコンパイルが必要なファイルをコピーできない場合は、sortedlist.pyファイルとsorteddict.pyファイルをデポからプルするだけです。すべてのコードはgithubのオープンソースです。

sortedcontainersモジュールは、相互にベンチマークされた最も一般的な提案とのパフォーマンス比較も提供します。

于 2014-09-23T06:36:45.323 に答える