ja In-place%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

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 で行われることが多い。

計算複雑性理論

計算複雑性理論では、in-place アルゴリズムは空間複雑性が O(1) であるアルゴリズム（DSPACE(1)クラス）を全て含む。このクラスは非常に限定されており、正規言語と等価である^[1]。実際、上述の例にあるアルゴリズムはいずれもこのクラスには含まれない。

このため、一般に in-placeアルゴリズムにはLクラスのアルゴリズム（すなわち、O(log n)の追加領域を必要とする問題のクラス）を含める。これは、定義と矛盾しているように見えるが、抽象世界では非常に巨大な入力を考慮する。実際のコンピュータでは、物理メモリ量が限られているためポインタに要する領域は極めて小さいが、サイズ n のリストの添字を表すには一般に O(log n)ビットの領域を必要とする。

この定義によればヒープソートは in-place であるがイントロソートは O((log n)²) の追加領域を必要とするため in-place ではないということになる。

Lクラスのアルゴリズムを in-placeアルゴリズムであると認めると、興味深い洞察が得られる。例えば、無向グラフでの2ノード間の経路が存在するかどうかを決定する in-placeアルゴリズムが存在することになる^[2]。通常、この問題は深さ優先探索などでは O(n) の追加領域を必要とする。同様に、2部グラフかどうかの判定問題や2つのグラフが同数の連結成分を持つかどうかという問題などに関しても in-placeアルゴリズムが存在することになる。

無作為性の役割

乱択アルゴリズムを使うことで必要な領域を劇的に減らすことができる場合が多い。例えば、ある2つのノードがグラフ内の1つの連結成分に含まれるかどうかを判定する問題を考える。この問題には既知の単純で決定的な in-placeアルゴリズムは存在しない。しかし、1つのノードを選んで約 20n³回ランダムウォークを行うと、もう1つのノードが同じ連結成分に含まれていることを発見する確率が非常に高い。また、素数判定にも確率的（乱択） in-placeアルゴリズムが存在するし（ミラー-ラビン素数判定法など）、素因数分解にも同様のアルゴリズムが存在する（ポラード・ロー素因数分解法）。

関数型プログラミング

関数型言語ではデータを上書きするような明確な in-placeアルゴリズムをサポートしていない（推奨しない）ことが多い。これは、データの上書きが副作用の一種であるためで、関数型言語では新たにデータ構造を作成することだけを許す（推奨する）のが一般的である。しかし、コンパイラが高度なものであれば、新たなデータが既存のデータに似ていて、かつ既存のデータが捨てられるだけであった場合、最適化によってデータ領域を再利用することがある。

ただし、これはデータの更新と以前のデータの参照が前後しないよう注意深く構築された in-placeアルゴリズムでなければならず、実際にはめったにない。

脚注

[脚注の使い方]

注釈

^ なお、各ソートの記事ではこれらをO(1)追加領域と表記しているが、本記事ではO(logn)追加領域と扱う。
^ 「素朴でない」実装によって、最悪でもO(n log n)ではなく、イントロソートと同様のO((log n)²)に追加領域を抑えられる。当該記事を参照

出典

^ 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.

[1] なお、各ソートの記事ではこれらをO(1)追加領域と表記しているが、本記事ではO(logn)追加領域と扱う。

[2] 「素朴でない」実装によって、最悪でもO(n log n)ではなく、イントロソートと同様のO((log n)²)に追加領域を抑えられる。当該記事を参照

[3] 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.

[4] Omer Reingold. Undirected ST-connectivity in Log-Space. Electronic Colloquium on Computational Complexity. No. 94.

[注釈 1]

[注釈 2]

[1]

[2]

In-placeアルゴリズム

例

計算複雑性理論

無作為性の役割

関数型プログラミング

脚注

注釈

出典