Rotate Image - LeetCodeを解いていたところ，in-place という馴染みのない単語が出てきたため調査してみた．
in-place とは？
この問題は，
入力：n×nの二次元行列
出力：入力の行列を時計回りに90度回転したもの
というもの．
問題文にある in-place の説明は以下通りである：
you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
つまり，追加のメモリを（ほとんど）使用せずに，入力を置換や入れ替えによって直接上書きすることで所望の結果を得るアルゴリズムのことであるといえる．
逆に， in-place でないアルゴリズムは not-in-place や out-of-place と呼ばれる．
in-place と not-in-place アルゴリズムの比較
今回は，次の問題を例に in-place アルゴリズムと not-in-place アルゴリズムを比較する．
問題
n個の要素を持つ配列の要素を逆順にした配列を返せ．
ex) input : [1,2,3,4,5] → output : [5,4,3,2,1]
not-in-place
def reverse(array):
n = len(array)
res = [0] * n # 戻り値用に領域を追加
for i in range(n):
res[i] = array[(n-1) - i]
return res
in-place
def reverse(array):
n = len(array)
for i in range(n//2):
# swap（入力に直接上書き）
array[i], array[n-1-i] = array[n-1-i], array[i]
考察
上記二つのアルゴリズムを見比べると，not-in-place は$O(n)$の配列resを新たに割り当てているのに対して，in-place は新たに配列を割り当てていないことが分かる．
このことから，入力の情報を保持したい場合は入力を直接操作する in-place ではなく， not-in-place アルゴリズムを採用するべきであることが分かる．
また，in-place であることはメモリの制限が厳しかった時代において重要な性質であったが，近年では計算機の性能が上がっているため in-place 性の重要度は比較的低くなっていると推測される．
参考
※こちらの記事は私のブログ記事の複製となっております。
※補足や間違いなどがありましたらコメント等でご指摘お願いいたします．