GitHubじゃ!Pythonじゃ!

GitHubからPython関係の優良リポジトリを探したかったのじゃー、でも英語は出来ないから日本語で読むのじゃー、英語社会世知辛いのじゃー

grantjenks

python-sortedcontainers – Pythonソート済みコンテナのタイプ:ソート済みリスト、ソート済Dict、およびソート済みセット //w..

投稿日:

Pythonソート済みコンテナのタイプ:ソート済みリスト、ソート済Dict、およびソート済みセット http: //www.grantjenks.com/docs/sorted…

Pythonソート済みコンテナ

Sorted Containersはpure2-Pythonで書かれた、Apache2でライセンスされたソート済みコレクションライブラリで 、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ギガバイトのメモリが必要です。 ソートされたリストに1000万を乗算すると、 “a”から “e”までのそれぞれに1,000,000の参照が格納されます。 各参照には、ソートされたコンテナ内に8バイトが必要です。 それは各オブジェクトへのポインタのコストであるので、かなり苦労します。 また、すべてのノードが子ノードへの2つのポインタを格納しなければならない典型的なバイナリツリー実装(例えば、Red-Black Tree、AVL-Tree、AA-Tree、Splay-Tree、Treapなど)よりもオーバーヘッドが66%少なくなります。

ソートされたコンテナは、Pythonソートされたコレクションからすべての作業を取り除き、Pythonのデプロイメントと使用を容易にします。 Cコンパイラをインストールする必要はなく、カスタム拡張を事前にビルドして配布する必要もありません。 パフォーマンスは機能であり、テストはユニットテストと数時間のストレスで100%カバーします。

お客様の声

Alex MartelliPython Software Foundationのフェロー

「良いものよ… O(N)の挿入コストを避けるために、ソートされたコンテナをより小さな「フラグメント」に分割する簡単で効果的な実装のアイディアが好きです。

Jeff KnuppWriting Idiomatic PythonとPython Trainerの著者

「最後の部分は、「C-拡張機能」としては信じがたいものでしたが、これは真実であると確信するためには何らかのパフォーマンス比較が必要です。著者にはこれがドキュメントに含まれています。

Kevin SamuelPython、Django Trainer

私は非常に驚くばかりです。コードの品質だけでなく、コードよりも多くのコメントを持っています。実際の作業量はコードではなく 、ドキュメント、ベンチマーク、実装の説明です。 gitログもきれいで、ユニットテストはPython 2と3の箱の外で実行されます。

マークサマーフィールドPythonソートコレクションの短い嘆願

Pythonの “batteries included”標準ライブラリにはバッテリーがないと思われます。 そして、「私たちはこれまでになかった」という議論は薄かった。 Pythonはソートされたコレクションクラスを含め、すぐにすぐにコレクションクラスを提供することができました。

Sorted Containersは以下のような一般的なオープンソースプロジェクトで使用されています:Zipline、Quantopianのアルゴリズム取引ライブラリ。 Angr 、UC Santa Barbaraのバイナリ解析プラットフォーム。 Trio 、非同期I / Oライブラリ。 Continuum Analyticsでサポートされている分散計算ライブラリDask Distributedが含まれています。

特徴

  • 純粋なPython
  • 完全に文書化されている
  • ベンチマーク比較(代替、ランタイム、負荷要因)
  • 100%テストカバレッジ
  • ストレステストの時間
  • パフォーマンスの問題(C実装よりも高速な場合が多い)
  • 互換性のあるAPI(古いblistおよびbintreesモジュールとほぼ同じ)
  • 豊富な機能(ソートされたdictの5つの最大キーを取得するなど):d.keys()[ – 5:])
  • 実用的な設計(例えば、SortedSetはSortedListインデックスを持つPythonセットです)
  • Python 3.6で開発
  • CPython 2.7,3.2,3.3,3.4,3.5,3.6およびPyPy、PyPy3でテスト済み

クイックスタート

並べ替えられたコンテナのインストールはpipで簡単です:

$ pip install sortedcontainers

Pythonの組み込みヘルプ機能を使用してインタプリタのドキュメントにアクセスすることができます。 ヘルプは、 ソートされたコンテナのモジュール、クラス、およびメソッドで機能します。

.. code-block:: python
>>> import sortedcontainers
>>> help(sortedcontainers)
>>> from sortedcontainers import SortedDict
>>> help(SortedDict)
>>> help(SortedDict.popitem)

ドキュメンテーション

パフォーマンスの比較を含む完全なドキュメントは、 http: //www.grantjenks.com/docs/sortedcontainers/で入手できます

ユーザーガイド

詳細については、導入、実装、パフォーマンス、および開発について説明しています。

APIドキュメント

特定の関数、クラス、またはメソッドに関する情報を探している場合は、この部分のドキュメントを参照してください。

会談

役に立つリンク

ソート済みコンテナライセンス

著作権2014-2018 Grant Jenks

Apache License、Version 2.0(以下「ライセンス」)の下でライセンスされています。 ライセンスに従わない限り、このファイルを使用することはできません。 あなたはライセンスのコピーを

http://www.apache.org/licenses/LICENSE-2.0

適用法または書面による合意が必要な場合を除き、本ライセンスに基づいて配布されるソフトウェアは、明示的または黙示的にいかなる種類の保証または条件もなく「現状有姿」で配布されます。 ライセンスに基づいて許可および制限を規定する特定の言語については、ライセンスを参照してください。







-grantjenks
-, , , , ,

執筆者: