インプレースアルゴリズム

コンピュータサイエンスにおいて、インプレースアルゴリズムとは、入力データ構造に直接作用し、入力サイズに比例した追加スペースを必要としないアルゴリズムのことです。言い換えれば、データ構造の別個のコピーを作成することなく、入力データをその場で変更します。インプレースではないアルゴリズムは、非インプレースまたはアウトオブプレースと呼ばれることもあります。

インプレースには、若干異なる意味があります。最も厳密な形では、アルゴリズムは関数呼び出しやポインタを含むすべてを数えて、一定量の追加スペースしか持つことができません。しかし、この形式は非常に限定的で、長さn の配列へのインデックスを持つだけでもO (log n )ビットが必要になります。より広義には、インプレースとは、アルゴリズムが入力の操作に余分なスペースを使用しないものの、操作のために少量の非定数の追加スペースを必要とする可能性があることを意味します。通常、このスペースはO (log n )ですが、場合によってはo ( n )の範囲内であれば何でも許容されます。スペース複雑度には、インデックスの長さをスペースの一部としてカウントするかどうかというさまざまな選択肢があることに注意してください。多くの場合、スペース複雑度は、必要なインデックスまたはポインタの数で表され、それらの長さは無視されます。この記事では、ポインタの長さをカウントする総スペース複雑度 ( DSPACE ) を参照します。したがって、ここでのスペース要件は、インデックスとポインタの長さを無視する分析と比較して、 log n の係数が追加されます。

アルゴリズムによっては、出力をメモリ使用量の一部としてカウントする場合としない場合があります。インプレースアルゴリズムは通常、入力を出力で上書きするため、追加のメモリは必要ありません。出力を書き込み専用メモリまたはストリームに書き込む場合は、アルゴリズムの作業領域のみを考慮する方が適切な場合があります。対数空間削減などの理論的な応用では、出力領域を常に無視するのが一般的です（このような場合、出力が書き込み専用であることがより重要になります）。

n個の要素を持つ配列 が与えられたとき、同じ要素を逆順に保持する配列を作成し、元の配列を破棄したいとします。これを行う一見簡単な方法の 1 つは、同じサイズの新しい配列を作成し、適切な順序でコピーを格納してから、を削除することです。aaa

function reverse(a[0..n - 1]) b[0..n - 1]を割り当てる i を0からn - 1まで繰り返す b[n − 1 − i] := a[i] bを返す

残念ながら、これには配列とを同時に使用できるようにするためのO ( n )の追加スペースが必要です。また、割り当てと解放は多くの場合、遅い操作です。はもはや必要ないので、代わりにこのインプレースアルゴリズムを使用して、自身の反転で上書きすることができます。このアルゴリズムでは、配列のサイズに関係なく、補助変数とに必要な整数は定数 (2) だけです。abaitmp

function reverse_in_place(a[0..n-1]) for i from 0 to floor((n-2)/2) tmp := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp

別の例として、バブルソート、コームソート、選択ソート、挿入ソート、ヒープソート、シェルソートなど、多くのソートアルゴリズムは配列をその場でソートされた順序に並べ替えます。これらのアルゴリズムは少数のポインタしか必要としないため、空間計算量はO (log n )です。^{[ 1 ]}

クイックソートは、ソート対象のデータに対してインプレースで処理を行います。ただし、クイックソートは分割統治戦略において部分配列を追跡するために、O (log n )個のスタック領域ポインタを必要とします。したがって、クイックソートにはO (log ² n )個の追加領域が必要となります。この非定数領域のため、技術的にはクイックソートはインプレースの範疇から外れますが、クイックソートや、O (log n )個の追加ポインタしか必要としない他のアルゴリズムは、通常インプレースアルゴリズムとみなされます。

ほとんどの選択アルゴリズムはインプレース方式ですが、最終的な一定サイズの結果を見つける過程で、入力配列を大幅に再配置するものもあります。

トリミングや反転などのテキスト操作アルゴリズムの中には、その場で実行できるものもあります。

計算複雑性理論では、インプレースアルゴリズムの厳密な定義には、空間計算量がO (1)のすべてのアルゴリズム、クラスDSPACE (1) が含まれます。このクラスは非常に限定的で、正規言語に相当します。^{[ 2 ]}実際、上記の例はどれも含まれていません。

アルゴリズムは通常、インプレース処理のためにO (log n )の追加スペースを必要とする問題のクラスであるLクラスに分類されます。このクラスは、ポインタまたはインデックスとしてサイズnの数値を扱うことができるため、実用的な定義により近いと言えます。ただし、再帰呼び出しを含むクイックソートは、この拡張された定義では除外されます。

インプレースアルゴリズムをLで識別すると、いくつかの興味深い意味合いがあります。たとえば、無向グラフの2つのノード間にパスが存在するかどうかを判定する（かなり複雑な）インプレースアルゴリズムが存在することを意味します^{[ 3 ]。}これは、深さ優先探索（各ノードに訪問済みビット）などの一般的なアルゴリズムを使用するとO ( n )の追加スペースを必要とする問題です。これにより、グラフが二部グラフであるかどうかを判定したり、2つのグラフが同じ数の連結成分を持っているかどうかをテストしたりするなどの問題に対するインプレースアルゴリズムが得られます。

多くの場合、ランダム化アルゴリズムを使用することで、アルゴリズムのメモリ使用量を大幅に削減できます。たとえば、 n個の頂点を持つグラフで 2 つの頂点が同じ連結成分にあるかどうかを知りたい場合、これを判定する単純で決定論的なインプレース アルゴリズムは知られていません。しかし、1 つの頂点から始めて約20 n ³ステップのランダム ウォークを実行すると、もう 1 つの頂点が同じ連結成分にある限り、その頂点に偶然たどり着く確率は非常に高くなります。同様に、ミラー・ラビン素数判定法のような単純なランダム化インプレース アルゴリズムがあり、ポラードのロー アルゴリズムのような単純なインプレース ランダム化因数分解アルゴリズムもあります。

関数型プログラミング言語では、データの上書きを伴う明示的なインプレースアルゴリズムは、副作用の一種であるため、推奨されないか、サポートされないことが多い。その代わりに、新しいデータの構築のみが許可される。しかし、優れた関数型言語コンパイラは、既存のオブジェクトと非常によく似たオブジェクトが作成され、古いオブジェクトが破棄された場合、それを認識して、内部的に単純な変更に最適化することが多い。

原理的には、データを変更しない（データがもはや使用されなくなった場合を除き）インプレースアルゴリズムを慎重に構築することは可能であるが、実際にはほとんど行われていないことに注意されたい。

• インプレースソートアルゴリズムと非インプレースソートアルゴリズムの表