In-placeアルゴリズム
From Wikipedia, the free encyclopedia
in-placeアルゴリズムとは、計算機科学においてデータ構造の変換を行うにあたって、追加の記憶領域をほとんど使わずに行うアルゴリズムを意味する。 in-place とは「その場で」といった意味であり、入力が出力で上書きされることが多いことから来る用語である。 in-place でないアルゴリズムは not-in-place あるいは out-of-place などと呼ばれることもある。
in-placeの定義にはやや揺れがある。最も狭義にはポインタなども含めて一定の空間しか使用しないアルゴリズムを指す。しかし長さnの配列の添字を表すだけでも O(log n) の空間を必要とするため、この意味で in-place であるアルゴリズムはごく限られている。多くの場合、 O(log n) の空間を使うことが許される。より広く O((log n)const.) 程度まで認めることもあり、時には o(n) であればよいとすることもある。
入力を出力で上書きしない場合、出力を追加の記憶領域とみなすかどうかについても揺れがある。出力先が通常の記憶装置である場合は記憶領域に含めて評価するが、書き込み専用メモリやストリームに出力する場合にはその大きさを無視して作業領域だけを評価することがある。特に対数領域帰着のような計算複雑性理論の問題では出力空間を無視するのが一般的である（その場合、出力をライトオンリーとすることが本質的に必要である）。
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アルゴリズムである[注釈 1]:
クイックソートは in-place アルゴリズムと言われることが多いが、素朴な実装ではそうではない。最悪の場合再帰の深さが O(n) に達し O(n log n) の領域を消費するからである[注釈 2]。イントロソートに改めれば、再帰の深さをO(logn)に抑えられるため、広い意味では in-place になる。
選択アルゴリズムは多くの場合 in-place だが、結果を得るために入力配列の要素の配置を大幅に変えてしまう。
計算複雑性理論
計算複雑性理論では、in-place アルゴリズムは空間複雑性が O(1) であるアルゴリズム（DSPACE(1)クラス）を全て含む。このクラスは非常に限定されており、正規言語と等価である[1]。実際、上述の例にあるアルゴリズムはいずれもこのクラスには含まれない。
このため、一般に in-placeアルゴリズムにはLクラスのアルゴリズム（すなわち、O(log n)の追加領域を必要とする問題のクラス）を含める。これは、定義と矛盾しているように見えるが、抽象世界では非常に巨大な入力を考慮する。実際のコンピュータでは、物理メモリ量が限られているためポインタに要する領域は極めて小さいが、サイズ n のリストの添字を表すには一般に O(log n)ビットの領域を必要とする。
この定義によればヒープソートは in-place であるがイントロソートは O((log n)2) の追加領域を必要とするため in-place ではないということになる。
Lクラスのアルゴリズムを in-placeアルゴリズムであると認めると、興味深い洞察が得られる。例えば、無向グラフでの2ノード間の経路が存在するかどうかを決定する in-placeアルゴリズムが存在することになる[2]。通常、この問題は深さ優先探索などでは O(n) の追加領域を必要とする。同様に、2部グラフかどうかの判定問題や2つのグラフが同数の連結成分を持つかどうかという問題などに関しても in-placeアルゴリズムが存在することになる。