Ｃでの行列式計算（再帰無し）

さて、動的メモリ確保がＣではかなり負荷が高く、Javaではそれ程でもない、ただしJavaはその分メモリ管理の厳密性を犠牲にしているようだということは分かった。
では、もう一つ2004.04.02付でのソースコードで速度劣化の原因になりそうということで挙げられていた、再帰呼び出しの方はどうだろうか。
ということで、次は再帰呼び出しになっている部分を展開してみて、結果が変わるかどうかを見てみよう。
問題となっている関数は、以下の部分である。

long expand(long array[], int dim) {
  int i, j, k, l;
  long value = 0;
  long *subarray;
  if(dim < 2)return array[0];
  subarray = (long *)malloc( (dim - 1) * (dim - 1) * sizeof(long));
  for(i = 0; i < dim; ++i) {
    l = 0;
    for(j = 0; j < dim; ++j){
      if(j != i){
        for(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)));
    }
  }
  free(subarray);
  return value;
}

上記を、dimの値ごとに別途の関数としてやれば、これを展開することが出来る。例えば、dim = 11の場合には以下のようになるだろう。

long expand11(long array[]) {
  int i, j, k, l;
  long value = 0;
  long *subarray;
  subarray = (long *)malloc(10 * 10 * sizeof(long));
  for(i = 0; i < 11; ++i) {
    l = 0;
    for(j = 0; j < 11; ++j){
      if(j != i){
        for(k = 1; k < 11; ++k)subarray[(l * 10) + k - 1] = array[(j * 11) + k];
        ++l;
      }
    }
    if(i % 2 == 0){
      value += (array[i * 11] * expand10(subarray));
    }else{
      value -= (array[i * 11] * expand10(subarray));
    }
  }
  free(subarray);
  return value;
}

今まではexpand関数の中から更にexpand関数自身を呼んでいたのだが、これがexpand11関数の中ではexpand10関数を、expand10関数の中ではexpand09関数を呼ぶというように展開することが出来る。
最後のexpand01関数は以下のようになる。

long expand01(long array[]) {
  return array[0];
}

こういう書き方をしても、論理的には全く同じことになる。関数の中から関数を呼び出していることに変わりは無いから、積まれるスタックの数も同じ。もしもスタックの節約をしたければ、１つの関数の中に多重ループでもって押し込むことになるだろう。（もしくは計算するデータをユーザスタックの形で保持し、ループを回すか、かな）
今回のような処理では、再帰でスタックに積まれる関数の数も少ないわけで、これで実行速度がどれだけ変わるのかは正直疑問だが、結論を出すのは測ってみてからで良いだろう。