Github: https://github.com/grantjenks/sorted_containers
Python SortedContainers
SortedContainersは、純粋なPythonで書かれた、Apache2でライセンスされたソート済みコレクションライブラリであり 、C拡張として高速です。
Pythonの標準ライブラリは、ソートされたコレクション型が必要になるまで素晴らしいものです。 多くの人があなたが本当になくてはならないことを証明しますが、ソートされたリスト、辞書、またはセットが本当に必要な瞬間には 、十分な文書化とベンチマークなしでC-拡張を使用しています。
Pythonでは、もっとうまくいくことができます。 純粋なPythonでそれを行うことができます！
>>> sl = sortedcontainers.SortedList(xrange(10000000))
>>> 1234567 in sl
True
>>> sl[7654321]
7654321
>>> sl.add(1234567)
>>> sl.count(1234567)
2
>>> sl *= 3
>>> len(sl)
30000003
注：少なくとも半分のメモリがなければこれを試してはいけません。 Pythonでは、整数は約24バイト必要です。 SortedListは、コンテナに格納されているオブジェクトあたり約8バイトを追加します。 それは各オブジェクトへのポインタのコストであるので、かなり苦労します。 また、すべてのノードが子ノードへの2つのポインタを格納しなければならない典型的なバイナリツリー実装（例えば、red-blackツリー、avlツリー、aaツリー、スプレイツリー、トレップなど）よりもオーバーヘッドが66％少なくなります。
SortedContainersは、Pythonのソート済みコレクションからすべての作業を取り除き 、Pythonのデプロイメントと使用を容易にします。 Cコンパイラをインストールする必要はなく、カスタム拡張を事前にビルドして配布する必要もありません。 パフォーマンスは機能であり、テストはユニットテストと数時間のストレスで100％カバーします。
お客様の声
Alex Martelli 、 ウィキペディア
いい物！ …私は、O（N）の挿入コストを避けるために、ソートされたコンテナをより小さな「フラグメント」に分割する簡単で効果的な実装のアイデアが好きです。
Jeff Knupp 、 SortedContainersのレビュー
最後の部分である「C-extensionsとしての速さ」は信じがたいものでした。 私はこれが本当であることを確信させるためにある種のパフォーマンス比較が必要です。 作者はこれをドキュメントに含めます。 そうです。
Kevin Samuel 、 Formations Python
私は非常に驚いています。コードの品質だけでなく、コードよりも多くのコメントを持っています。実際の作業量は、コードではなく 、ドキュメント、ベンチマーク、実装の説明です。 gitログもきれいで、ユニットテストはPython 2と3の箱の外で実行されます。
マークサマーフィールド 、 Pythonソートコレクションの短い嘆願
Pythonの “batteries included”標準ライブラリにはバッテリーがないと思われます。 そして、「私たちはこれまでになかった」という議論は薄かった。 Pythonはソートされたコレクションクラスを含め、すぐにすぐにコレクションクラスを提供することができました。
特徴
- 純粋なPython
- 完全に文書化されている
- ベンチマーク比較（代替、ランタイム、負荷要因）
- 100％テストカバレッジ
- ストレステストの時間
- パフォーマンスの問題（C実装よりも高速な場合が多い）
- 互換性のあるAPI（一般的なblistおよびrbtreeモジュールとほぼ同じ）
- 豊富な機能（ソートされたdict：d.iloc [-5：]の5つの最大キーを取得するなど）
- 実用的な設計（例えば、SortedSetはSortedListインデックスを持つPythonセットです）
- Python 2.7で開発
- CPython 2.7,3.2,3.3,3.4,3.5,3.6およびPyPy、PyPy3でテスト済み
クイックスタート
SortedContainersのインストールはpipで簡単です：
$ pip install sortedcontainers
Pythonの組み込みヘルプ関数を使用してインタプリタのドキュメントにアクセスすることができます：
>>> from sortedcontainers import SortedList, SortedSet, SortedDict
>>> help(SortedList)
ドキュメンテーション
パフォーマンスの比較を含む完全なドキュメントは、 http： //www.grantjenks.com/docs/sortedcontainers/で入手できます 。
ユーザーガイド
詳細については、導入、実装、パフォーマンス、および開発について説明しています。
APIドキュメント
特定の関数、クラス、またはメソッドに関する情報を探している場合は、この部分のドキュメントを参照してください。
会談
寄稿
コラボレーターは大歓迎です！
- 開いている問題を確認するか、新しい問題を開いてバグに関する議論を開始してください。 まだコードベースに精通していない人が使用すべき問題についてはContributor Friendlyタグがあります。
- GitHubでSortedContainersリポジトリをフォークし、新しいブランチへの変更を開始します。
- バグが修正されたことを示すテストを作成します。
- プルリクエストを送信し、マージンが発行されて公開されるまでメンテナをバグしてください。
役に立つリンク
SortedContainersライセンス
著作権2014-2016 Grant Jenks
Apache License、Version 2.0（以下「ライセンス」）の下でライセンスされています。 ライセンスに従わない限り、このファイルを使用することはできません。 あなたはライセンスのコピーを
適用法または書面による合意が必要な場合を除き、本ライセンスに基づいて配布されるソフトウェアは、明示的または黙示的にいかなる種類の保証または条件もなく「現状有姿」で配布されます。 ライセンスに基づいて許可および制限を規定する特定の言語については、ライセンスを参照してください。