In-placeアルゴリズム
出典: フリー百科事典『ウィキペディア（Wikipedia）』
in-placeアルゴリズムとは、計算機科学においてデータ構造の変換を行うにあたって、追加の記憶領域をほとんど使わずに行うアルゴリズムを意味する。アルゴリズムの実行によって、入力データ構造が出力データ構造で上書きされることが多い。"in-place" とは「その場で」といった意味であり、in-place でないアルゴリズムは not-in-place あるいは out-of-place などと呼ばれることもある。
入力データを出力データで上書きするアルゴリズムを非公式的に in-place であると呼ぶこともある。実際には（クイックソートのように）それだけでは不十分であるか、必要条件ではない。出力がストリームの場合など出力領域が不定であっても in-placeアルゴリズムと呼ばれることがある。一方、より実用的に出力領域の大きさを測定して in-place アルゴリズムかどうかを決定する立場もある（後述の例にある reverse など）が、この考え方では in-placeアルゴリズムかどうかを厳密に定義するのが困難である。対数領域帰着のような問題では、出力空間を無視するのが一般的である（その場合、出力はライトオンリーとするのが基本である）。
目次 |
[編集] 例
n個の要素からなる配列の要素を逆順に入れ替える場合を考える。単純な方法として以下の方式が考えられる:
function reverse(a[0..n])
allocate b[0..n]
for i from 0 to n
b[n - i] = a[i]
return b
この方法では配列 b の領域に O(n) の空間を必要とする。記憶領域の確保は時間がかかることが多い。もし a を今後必要としないなら、以下のような in-placeアルゴリズムで a に逆順の出力結果を書き込むことができる:
function reverse-in-place(a[0..n])
for i from 0 to floor(n/2)
swap(a[i], a[n-i])
他の例として、以下のような整列アルゴリズムは入力配列そのものを操作して整列を施す in-placeアルゴリズムである:
クイックソートは通常 in-placeアルゴリズムと言われているが、実際にはそうではない。分割統治法的再帰を行うために O(log n)の空間を必要とするような実装をしていることが多い。
選択アルゴリズムは多くの場合 in-place だが、結果を得るために入力配列の要素の配置を大幅に変えてしまう。
文字列操作アルゴリズム（トリムや文字列の逆転など）は in-place で行われることが多い。
[編集] 計算複雑性理論
計算複雑性理論では、in-place アルゴリズムは空間複雑性が O(1) であるアルゴリズム（DSPACE(1)クラス）を全て含む。このクラスは非常に限定されており、正規言語と等価である[1]。実際、上述の例にあるアルゴリズムはいずれもこのクラスには含まれない。
このため、一般に in-placeアルゴリズムにはLクラスのアルゴリズム（すなわち、O(log n)の追加領域を必要とする問題のクラス）を含める。これは、定義と矛盾しているように見えるが、抽象世界では非常に巨大な入力を考慮する。実際のコンピュータでは、物理メモリ量が限られているためポインタに要する領域は極めて小さいが、サイズ n のリストのインデックスを表すには一般に O(log n)ビットの領域を必要とする。
それでは、結局クイックソートは in-placeアルゴリズムと言えるのだろうか？ 全く技術的ではないが、クイックソートは O(log2 n) の領域を必要とし、O(log n)個の各スタックフレームには一定個のポインタが格納される（個々のポインタのサイズは O(log n)）。
Lクラスのアルゴリズムを in-placeアルゴリズムであると認めると、興味深い洞察が得られる。例えば、無向グラフでの2ノード間の経路が存在するかどうかを決定する in-placeアルゴリズムが存在することになる[2]。通常、この問題は深さ優先探索などでは O(n) の追加領域を必要とする。同様に、2部グラフかどうかの判定問題や2つのグラフが同数の連結成分を持つかどうかという問題などに関しても in-placeアルゴリズムが存在することになる。
[編集] 無作為性の役割
乱択アルゴリズムを使うことで必要な領域を劇的に減らすことができる場合が多い。例えば、ある2つのノードがグラフ内の1つの連結成分に含まれるかどうかを判定する問題を考える。この問題には既知の単純で決定的な in-placeアルゴリズムは存在しない。しかし、1つのノードを選んで約 20n3回ランダムウォークを行うと、もう1つのノードが同じ連結成分に含まれていることを発見する確率が非常に高い。また、素数判定にも確率的（乱択） in-placeアルゴリズムが存在するし（ミラー-ラビン素数判定法など）、素因数分解にも同様のアルゴリズムが存在する（ポラード・ロー素因数分解法）。
[編集] 関数型プログラミング
関数型言語ではデータを上書きするような明確な in-placeアルゴリズムをサポートしていない（推奨しない）ことが多い。これは、データの上書きが副作用の一種であるためで、関数型言語では新たにデータ構造を作成することだけを許す（推奨する）のが一般的である。しかし、コンパイラが高度なものであれば、新たなデータが既存のデータに似ていて、かつ既存のデータが捨てられるだけであった場合、最適化によってデータ領域を再利用することがある。
ただし、これはデータの更新と以前のデータの参照が前後しないよう注意深く構築された in-placeアルゴリズムでなければならず、実際にはめったにない。
[編集] 参考文献
- ^ Maciej Liśkiewicz and Rüdiger Reischuk. The Complexity World below Logarithmic Space. Structure in Complexity Theory Conference, pp. 64-78. 1994. Online: p. 3, Theorem 2.
- ^ Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94.
