雨谷の日和

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

Cでの行列式計算(ループ、事前、alloca)

次に、事前メモリ確保のallocaでの実装を実測してみよう。
ソースコードは以下のようになる。

#include
#include

long** array_buf;

long expand(long arraybase[ ], int dim){
  int j, k, l, index, d, flg;
  long **array;
  long *return_value;
  int *i;
  long result;

  array = (long **)alloca(dim * sizeof(long *));
  return_value = (long *)alloca(dim * sizeof(long));
  i = (int *)alloca(dim * sizeof(int));
  d = dim;
  flg = 0;

  array[dim - 1] = arraybase;
  for(index = 0; index < dim; index++)return_value[index] = 0;
  for(index = 0; index < dim; index++)i[index] = 0;

  do {
    if(d < 2){
      return_value[d - 1] = array[d - 1][0];
      d++;
      flg = 1;
    }else{
      if(flg == 0){
        if(i[d - 1] == 0){
          array[d - 2] = array_buf[d - 2];
          return_value[d - 1] = 0;
        }
        if(i[d - 1] < d){
          l = 0;
          for(j = 0; j < d; ++j){
            if(j != i[d - 1]){
            for(k = 1; k < d; ++k)array[d - 2][(l * (d - 1)) + k - 1] = array[d - 1][(j * d) + k];
              ++l;
            }
          }
          d--;
          i[d - 1] = 0;
        }
      }else{
        if(i[d - 1] < d){
          if(i[d - 1] % 2 == 0){
            return_value[d - 1] += (array[d - 1][i[d - 1] * d] * return_value[d - 2]);
          }else{
            return_value[d - 1] -= (array[d - 1][i[d - 1] * d] * return_value[d - 2]);
          }
          i[d - 1]++;
          flg = 0;
        }
        if(i[d - 1] == d){
          d++;
          flg = 1;
        }
      }
    }
  }while(d <= dim);
  result = return_value[dim - 1];
  return result;
}

int main() {
  int i;
  long value;
  long array[11 * 11] = {
    1, 2, 3, 4, 6, 1, 7, 1, 9, 0, 0, 
    5, 1, 5, 7, 7, 3, 5, 3, 6, 1, 6, 
    7, 6, 4, 8, 4, 6, 1, 7, 1, 4, 8, 
    6, 5, 1, 0, 1, 5, 9, 1, 7, 5, 1, 
    2, 3, 1, 1, 5, 8, 4, 6, 3, 1, 5, 
    3, 1, 0, 3, 2, 9, 4, 8, 0, 3, 1, 
    3, 2, 8, 5, 0, 6, 3, 4, 4, 8, 5, 
    4, 9, 9, 4, 6, 1, 0, 1, 2, 1, 6, 
    9, 7, 6, 1, 6, 4, 5, 2, 9, 4, 4, 
    1, 2, 2, 2, 8, 3, 4, 9, 1, 2, 4, 
    6, 1, 6, 4, 4, 8, 6, 3, 4, 1, 4, 
  };

  array_buf = (long **)alloca(10 * sizeof(long *));
  for(i = 0; i < 10; ++i)array_buf[i] = (long *)alloca(11 * 11 * sizeof(long)); 

  value = expand(array, 11);
  printf("result: %d\n", value);
  return 0;
}

結果は以下のようになった。

20:38:29
result: 489261678
20:38:36
result: 489261678
20:38:40

最適化無しで約7秒、最適化有り(-O3)で約4秒という結果となった。
malloc/freeでの実装の実測と同じ結果となった。