Rotate Image - LeetCodeを解いていたところ，in-place という馴染みのない単語が出てきたため調査してみた．

問題の概要

この問題は，

というもの．

問題文の 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 性の重要度は比較的低くなっていると考えられる．