修行の場

知人が言っていました。これは修行だと。

Pythonの基本的なデータ構造を少し真面目に学ぶ

背景

Pythonのメモリ管理において、 Pythonは数値型のメモリ確保が全体的に遅いこと、 とはいえ、オーダーの議論は進めても問題なさそうなことがイメージできました。

今回はPythonの基本的なデータ型について学びます。 参考とするページは以下のとおりです。

list

リストは配列として実装されています。 この中でも、実コストが高いものとして挙げられているのが、 行 * メモリへの割り当てを超えて要素数が増えた場合 * 配列の先頭付近の要素を削除したり(pop, remove)、先頭付近に要素を追加したりした(insert)場合

で、全てコピーが発生します。 また、sortやcopyも大量のコピーが発生します。

appendのaverage running timeはO(1)ですが、毎回メモリが割り当てられるわけではなく、取りたい長さに応じて多めにメモリを確保するらしいです。リストが長くなる場合、reallocがうまく行かない場合は、appendの速度はO(n)になるらしいです。reallocはメモリ領域を拡張できない場合、新たなメモリ領域を確保してコピーするので、確保領域が大きければ大きいほど、realloc時にメモリ領域拡張ではなく、コピーが生じるからでしょう。 できる限り一度にappendしてしまったほうが良さそうです。 予め確保する方法はなさそう?です。

insert, a[n1:n2] = another_list, remove, pop, del[n1:n2]などはデータ量と相談して考えたほうがいいかもしれません。sortも。

delステートメントも便利です。

Stackの実装

listはstackとして使えます。

collections.deque

doubly linked listとして実装されています。 listと異なる点は、末尾だけでなく、先頭の追加削除も高速であることです。 任意の場所の削除はO(n)。ただしメモリ読み込みがcomputational expensiveです。 また、単体でrotate(シフト操作)がO(k)でできます。

Queueの実装

dequeはqueueとして使えます。

setとdict

所属チェックとキーによる探索が速いです。 dictはstrがキーの場合は特別に早くなる処理が入っているようです。 平均計算量はハッシュ関数が良い感じで、辞書内にあるデータへのアクセスの平均計算量なようで、その使い方から外れると速度が低下する可能性があります。

setもdictもデータ構造について記載なしですが、どちらも同じ構造でsetのソースを見てみたところ、普通のhashテーブル+open addressingを使っているようです。forzensetとsetで構造とアルゴリズムはほぼ同じものを使っているようです。

ductもソースコードによると、 chainingではなく、open addressingを使っているようです。 実際のデータ構造もソースコード参照です。 基本的なハッシュテーブルだと思えばいいと思いますが、 高速になるようにかなりの工夫がされているようです。

dictはordered, setはunorderedなようです。 setは多分ハッシュ表の要素が存在する箇所をたどるだけでしょう。O(n)だと思います。 dictでは順序が保証されているので、どうなっているかiteratorの実装を見てみましょう。

ちょっと詳細は次回見るとして、順序が保存してあって、そこからざっくりした位置を探すようです。おそらく、O(n)?

シーケンスの比較

シーケンス型は比較ができるようです。

まとめ

基本的なデータ型についてさらっと実装とオーダーを確認しました。 次は他のシーケンス型について学びます。