|
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) allocate b for i from 0 to n b- i = a return b この方法では配列 ''b'' の領域に O(''n'') の空間を必要とする。記憶領域の確保は時間がかかることが多い。もし ''a'' を今後必要としないなら、以下のような in-placeアルゴリズムで ''a'' に逆順の出力結果を書き込むことができる: function reverse-in-place(a) for i from 0 to floor(n/2) swap(a, a) 他の例として、以下のような整列アルゴリズムは入力配列そのものを操作して整列を施す in-placeアルゴリズムである: * バブルソート * コムソート * 選択ソート * 挿入ソート * ヒープソート * シェルソート クイックソートは通常 in-placeアルゴリズムと言われているが、実際にはそうではない。分割統治法的再帰を行うために O(log ''n'')の空間を必要とするような実装をしていることが多い。 選択アルゴリズムは多くの場合 in-place だが、結果を得るために入力配列の要素の配置を大幅に変えてしまう。 文字列操作アルゴリズム（トリムや文字列の逆転など）は in-place で行われることが多い。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「In-placeアルゴリズム」の詳細全文を読む スポンサード リンク
|