雨谷の日和

過去12年で1,600を超えるアニメの第1話だけは見続けた僕のお勧めアニメがハズレなはずがない

再帰のループ展開その1

ということで、再帰呼び出しを今度はループに展開してみようと思う。
結構ややこしいので、順を追ってちまちまと開いていくことにする。
展開対象となるのは、以下のexpand関数である。
作業はまずJavaの方で行い、後にCの方も類似の記述に改めることにする。

private static long expand(long array, int dim) {
  if(dim < 2)return array[0];
  long subarray = new long[(dim - 1) * (dim - 1)];
  long value = 0;
  for(int i = 0; i < dim; ++i) {
    int l = 0;
    for(int j = 0; j < dim; ++j){
      if(j != i){
        for(int k = 1; k < dim; ++k)subarray[(l * (dim - 1)) + k - 1] = array[(j * dim) + k];
        ++l;
      }
    }
    if(i % 2 == 0){
      value += (array[i * dim] * expand(subarray, (dim - 1)));
    }else{
      value -= (array[i * dim] * expand(subarray, (dim - 1)));
    }
  }
  return value;
}

まずは、再帰呼び出しの部分を基準に、関数の中を区分する。
そのために、以下のような書き換えを行い、呼び出し部分を切り出す。

private static long expand(long array, int dim) {
  if(dim < 2)return array[0];
  long subarray = new long[(dim - 1) * (dim - 1)];
  long value = 0;
  for(int i = 0; i < dim; ++i) {
    int l = 0;
    for(int j = 0; j < dim; ++j){
      if(j != i){
        for(int k = 1; k < dim; ++k)subarray[(l * (dim - 1)) + k - 1] = array[(j * dim) + k];
        ++l;
      }
    }
    long result = expand(subarray, (dim - 1));
    if(i % 2 == 0){
      value += (array[i * dim] * result);
    }else{
      value -= (array[i * dim] * result);
    }
  }
  return value;
}

次に、このロジックは多重ループになるので呼び出しとループの関係から処理を分けてみる。

(A)

return array[0];
(B)

long[] subarray = new long[(dim - 1) * (dim - 1)]; long value = 0;
(C)

int l = 0; for(int j = 0; j < dim; ++j){ if(j != i){ for(int k = 1; k < dim; ++k)subarray[(l * (dim - 1)) + k - 1] = array[(j * dim) + k]; ++l; } }
(D)

long result = expand(subarray, (dim - 1));
(E)

if(i % 2 == 0){ value += (array[i * dim] * result); }else{ value -= (array[i * dim] * result); }

上記の(A)〜(E)までに分けると、元の関数は以下のようになる。

private static long expand(long[] array, int dim) {
  if(dim < 2){
    (A)
  }else{
    (B)
    for(int i = 0; i < dim; ++i) {
      (C)
      (D)
      (E)
    }
    return value;
  }
}

まずはここまで。