Python の組み込みシーケンス型の時間と空間の複雑さはどこで確認できますか?

Question

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

Answer 1

チェックアウトしてください 時間の複雑さ py dot org wiki のページ。少なくとも時間の複雑さに関しては、set/dicts/listsなどをカバーしています。

Answer 2

レイモンド D.ヘッティンガーはそうする 素晴らしい話 (スライド) 「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 表記であり、メモリはそれほど多くありません。