Pythonユーザーなら知っておきたいのリストの仕組み
Pythonでプログラムを書くとき、ほぼ必須となるデータ構造であるリスト (list) の仕組みを紹介します。僕自身Pythonをよく使うのですが、これまで実装を意識してこなかったので、内部の仕組みについてまとめてみました。Pythonのリストは要素の追加 (list.append) /削除 (list.pop) により、サイズが動的に変更されますが、これらはO(1)で高速に行う (list.popは末尾要素のみ) ことができます。この記事ではその理由について解説していきます。
Pythonのリストのような特徴を持ったデータ構造は動的配列 (dynamic array) と呼ばれます。通常の配列は静的配列 (static array)として区別されます。 この記事では、動的配列の概要、要素の追加/削除について、MITの講義 (Table Doubling, Karp-Rabin) を元に以下の順でまとめます。
- 動的配列とは？
- 動的配列における追加/削除の方法
- 追加/削除のバランス調整
1. 動的配列とは？
動的配列では、要素の追加/削除に応じてサイズが変更されます。ただしサイズの拡大、縮小は毎回行われる訳ではありません。動的配列は追加と拡大、削除と縮小のバランスを調整することによって、効率的なサイズ変更を行っています。
動的配列は要素数に応じて、新しい静的配列を生成し、既存の要素をすべてコピーすることでサイズ変更を行っています。下図に配列のサイズが拡大される例を示しました。静的配列への要素追加もコピーも処理的には同じことですが、わかりやすさのために分けて示しました。
拡大において、配列のサイズは、少ししか増やさなくても、たくさん増やしても効率が悪くなります。上図のようにサイズを1しか増やさないと 、最初に作成した配列のサイズ以上の要素を追加するたびに、要素数分コピーの処理が発生し、無駄な処理が多くなります。 一方で大きくしすぎると、要素が格納されない無駄な領域が多くなります。
動的配列では、下記のような状態から要素を削除するとき、同時に配列のサイズを縮小します。
図を見て分かる通り、使われていない領域は無駄になるからです。サイズの縮小においても、サイズを少ししか減らさなくても、減らしすぎても効率は悪くなります。少ししか減らさないと無駄な領域は多いままになり、減らしすぎると要素を追加するときに配列を拡大しなければなりません。
2. 動的配列における追加/削除の方法
2.1 動的配列の要素追加
動的配列の要素追加とサイズの拡大のみについて考えます。配列のサイズ拡大は、要素追加時にサイズが足りないと実行されます。拡大するサイズは通常、既存の配列のサイズの何倍にするか (growth factor) によって決まり、growth factorはプログラミング言語によって異なります。Wikipediaによると、C言語やGo言語では2、Pythonでは1.125となっているようです。この記事ではわかりやすさのために、growth factorは2とします。
growth factorを2としたとき、動的配列にn個の要素を追加する計算量を考えます。1個の要素追加の計算量は、後述します。初期の配列のサイズを2とすると、要素を追加する毎に配列のサイズは以下のように変化します。配列の左側に、追加とコピーの回数を示しました。
n個の要素追加の計算量は次のようになります。
前半部分は配列への要素追加、後半部分は配列への要素コピーの計算量になります。要素のコピーは配列拡大のコストとなります。静的配列への要素の追加やコピー (追加と同じ) はO(1)で実行できるので、計算量は単にそれらの処理行った回数の合計になります。
等比数列の和の公式を用いて変形すると、計算量は以下のようなります。式変形の途中で定数項は無視しています。
動的配列にn個の要素を追加する処理の計算量はO(n)となります。動的配列では、要素の追加と同時に配列の拡大も行われていますが、n個の要素追加は線形時間で実行できるということになります。
n個の要素を動的配列に追加する計算量はO(n)なので、1個の要素追加の計算量は平均的にO(1)と考えることができます。このような操作1回あたりの平均の計算量のことを償却計算量やならし計算量 (amortized complexity time) と呼びます。また個々の操作ではなく、全体的な操作に着目して、計算量を解析することを償却解析やならし解析 (amortized analysis) と呼びます。償却解析により、Pythonのlist.appendが平均的にO(1)で実現されていることがわかります。
実際のシステムでは、個々の処理にかかる時間よりも、目的の処理を達成するのにかかる時間に興味があることが多いので、償却解析が用いられます。例えば、CSVファイルの各行を配列に格納する処理では、1行より全行を格納し終える時間のほうが重要です。
2.2 動的配列の要素削除
動的配列は要素を削除していくと同時に、静的配列のサイズを1/(growth factor)に縮小します。配列サイズに対して要素が少ないと、無駄な領域が多くなるからです。この処理は、Pythonのlist.popに対応します。要素追加を参考に、要素を削除する際には、要素数が配列サイズの1/2になったらサイズの縮小をします。初期の配列のサイズを16として、要素の削除を行った様子は下図のようになります。growth factorは2なので、サイズは1/2になります。
動的配列の要素追加と同様に考えると、n個の要素を削除する計算量は、O(n)となります。よって償却計算量はO(1)となり、要素削除も配列サイズを縮小しつつ、高速に実行可能であることが確認できます。
3. 追加/削除のバランス調整
2では動的配列の追加/削除の動作を別々に解説しましたが、両方を行う場合は効率を考慮する必要があります。下図のような追加/削除の繰り返しは無駄な処理や領域が多くなります。
この問題は、拡大と縮小のタイミングをずらすことによって、解決することができます。例えば、次のように要素数が配列サイズの1/4になったら、配列のサイズを1/2にするなどです。
配列サイズの拡大と縮小のタイミングが違うので、追加と削除が繰り返されても、無駄な処理が少なくなります。
解説は以上になります。Pythonのリストが採用している動的配列の仕組みを解説しました。償却解析により要素の追加/削除、Pythonでのlist.appendとlist.pop、がO(1)で実行可能なことを確認しました。追加/削除以外のメソッドや、他のデータ構造の計算量は、Python WikiのTimeComplexityにまとまっているので、興味のある方は御覧ください。
