python - Pythonの組み込みシーケンスタイプの時間と空間の複雑さはどこにありますか

Question

Pythonソースコードを自分で調べてオブジェクトがどのように機能するかを判断する以外に、この情報のソースを見つけることができませんでした。私がこれをオンラインで見つけることができる場所を誰かが知っていますか？

Answer 1

py dot org wiki のTimeComplexityページをチェックしてください。少なくとも時間の複雑さに関する限り、set/dicts/lists/etc をカバーします。

Answer 2

Raymond D. Hettinger は、 'Core Python Containers - Under the Hood' と呼ばれる Python の組み込みコレクションについて優れた講演(スライド) を行っています。私が見たバージョンは、主にsetとdictに焦点を当てていましたlistが、カバーも含まれていました。

ブログには、 EuroPython の関連するスライドの写真もいくつかあります。

に関する私のメモの要約は次のとおりですlist。

• 項目をポインターの配列として格納します。添字のコストは O(1) 時間です。追加コストは償却 O(1) 時間です。挿入コストは O(n) 時間です。
• memcpyオーバーアロケーションによる成長時に回避しようとします。多くの小さなリストは多くのスペースを浪費しますが、大きなリストは約 12.5% 以上を無駄にして割り当て超過することはありません。
• 一部の操作は事前にサイズ調整されています。与えられた例はrange(n)、、、、、map()およびスライスでしたlist()。[None] * n
• 縮小する場合、配列はreallocスペースの 50% を浪費している場合にのみ編集されます。pop安いです。

Answer 3

私があなたの質問だと思うものをあなたが尋ねるなら、あなたはそれらをここで見つけることができます...476ページ以降。

Pythonの最適化手法を中心に書かれています。これは主に、時間効率のBig-O表記であり、メモリはそれほど多くありません。