Pythonソートコンテナ
v2.1.0 JOSS
Sorted Containers は、Apache2 ライセンスのソート コレクション ライブラリであり、純粋な Python で書かれており、C 拡張機能と同じくらい高速です。
Python の標準ライブラリは、ソートされたコレクション型が必要になるまでは優れています。多くの人は、これらを使わなくてもかなりの作業ができることを証明しますが、並べ替えられたリスト、並べ替えられた辞書、または並べ替えられたセットが本当に必要になった瞬間に、十数種類の異なる実装に直面することになります。そのほとんどは、優れたドキュメントやベンチマークなしで C 拡張機能を使用しています。
Python では、さらに改善できるはずです。そして、それを純粋な Python で行うことができます。
> >> from sortedcontainers import SortedList
> >> sl = SortedList ([ 'e' , 'a' , 'c' , 'd' , 'b' ])
> >> sl
SortedList ([ 'a' , 'b' , 'c' , 'd' , 'e' ])
> >> sl *= 10_000_000
> >> sl . count ( 'c' )
10000000
> >> sl [ - 3 :]
[ 'e' , 'e' , 'e' ]
> >> from sortedcontainers import SortedDict
> >> sd = SortedDict ({ 'c' : - 3 , 'a' : 1 , 'b' : 2 })
> >> sd
SortedDict ({ 'a' : 1 , 'b' : 2 , 'c' : - 3 })
> >> sd . popitem ( index = - 1 )
( 'c' , - 3 )
> >> from sortedcontainers import SortedSet
> >> ss = SortedSet ( 'abracadabra' )
> >> ss
SortedSet ([ 'a' , 'b' , 'c' , 'd' , 'r' ])
> >> ss . bisect_left ( 'c' )
2上記の操作はすべて、直線時間よりも高速に実行されます。上記のデモの実行には、ギガバイト近くのメモリも必要です。ソートされたリストを 1,000 万倍すると、「a」から「e」までのそれぞれへの 1,000 万件の参照が格納されます。各参照には、ソートされたコンテナー内に 8 バイトが必要です。各オブジェクトへのポインターのコストがかかるため、これを克服するのはかなり困難です。また、すべてのノードが子ノードへの 2 つのポインタも格納する必要がある一般的なバイナリ ツリー実装 (例: Red-Black Tree、AVL-Tree、AA-Tree、Splay-Tree、Treap など) よりもオーバーヘッドが 66% 少なくなります。
Sorted Containers は、Python のソートされたコレクションからすべての作業を取り除き、Python のデプロイと使用を簡単にします。 C コンパイラーをインストールしたり、カスタム拡張機能を事前にビルドして配布したりする必要はありません。パフォーマンスが特徴であり、テストは単体テストと数時間のストレスで 100% カバーされます。
Alex Martelli氏、Python Software Foundation フェロー
「良いですね! ... O(N) の挿入コストを回避するために、ソートされたコンテナをより小さな「フラグメント」に分割するという、シンプルで効果的な実装アイデアが気に入っています。」
Jeff Knupp 、『Writing Idiomatic Python』および『Python Trainer』の著者
「最後の部分、『C 拡張機能と同じくらい高速』というのは信じがたいことでした。これが真実であると確信するには、ある種のパフォーマンス比較が必要でしょう。著者はこれをドキュメントに記載しています。そのとおりです。」
Kevin Samuel 、Python および Django トレーナー
コードの品質 (信じられないほど読みやすく、コードよりもコメントが多い、すごい) だけでなく、ドキュメント、ベンチマーク、実装の説明など、コード以外の部分に費やした実際の作業量にも、私は非常に驚いています。 git ログもクリーンで、単体テストは Python 2 と 3 でそのまま実行できます。
Mark Summerfield 、Python のソートされたコレクションに対する短い嘆願
Python の「電池付き」標準ライブラリには電池が無いようです。そして、「これまでそんなことはなかった」という議論は薄れてきました。 Python が、ソートされたクラスを含む、あらゆる種類のコレクション クラスをすぐに提供できる時代が来ました。
Sorted Containers は、次のような人気のあるオープン ソース プロジェクトで使用されています。Zipline、Quantopian のアルゴリズム取引ライブラリ。 Angr、カリフォルニア大学サンタバーバラ校のバイナリ分析プラットフォーム。 Trio、非同期 I/O ライブラリ。 Dask Distributed は、Continuum Analytics によってサポートされる分散計算ライブラリです。
Sorted Containers のインストールは pip を使用すると簡単です。
$ pip installsortedcontainers
Python の組み込みヘルプ機能を使用して、インタープリターのドキュメントにアクセスできます。このヘルプは、Sorted Containers のモジュール、クラス、メソッドに対して機能します。
> >> import sortedcontainers
> >> help ( sortedcontainers )
> >> from sortedcontainers import SortedDict
> >> help ( SortedDict )
> >> help ( SortedDict . popitem )ソートされたコンテナーの完全なドキュメントは、http://www.grantjenks.com/docs/sortedcontainers/ で入手できます。
ユーザー ガイドでは、Sorted Containers の概要と広範なパフォーマンスの比較と分析が提供されます。
コミュニティ ガイドでは、Sorted Containers の開発に関する情報と、サポート、実装、歴史の詳細が提供されます。
API ドキュメントでは、Sorted Containers パッケージの特定の関数、クラス、およびモジュールに関する情報が提供されます。
著作権 2014-2024 グラント・ジェンクス
Apache License バージョン 2.0 (「ライセンス」) に基づいてライセンスされています。ライセンスに準拠する場合を除き、このファイルを使用することはできません。ライセンスのコピーは次の場所で入手できます。
http://www.apache.org/licenses/LICENSE-2.0
適用される法律で義務付けられている場合または書面による同意がない限り、ライセンスに基づいて配布されるソフトウェアは、明示または黙示を問わず、いかなる種類の保証や条件もなく、「現状のまま」で配布されます。ライセンスに基づく許可と制限を規定する特定の言語については、ライセンスを参照してください。
