今度は事前にメモリを確保してその領域を使い回す方法を、ループ展開の場合にも試してみよう。
まずはCのmalloc/freeについて書き下すと以下のようになる。
#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 **)malloc(dim * sizeof(long *)); return_value = (long *)malloc(dim * sizeof(long)); i = (int *)malloc(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]; free(i); free(return_value); free(array); 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 **)malloc(10 * sizeof(long *)); for(i = 0; i < 10; ++i)array_buf[i] = (long *)malloc(11 * 11 * sizeof(long)); value = expand(array, 11); printf("result: %d\n", value); for(i = 0; i < 10; ++i)free(array_buf[i]); free(array_buf); return 0; }
実行結果は以下である。
20:38:18 result: 489261678 20:38:25 result: 489261678 20:38:29
最適化無しで約7秒、最適化有りで約4秒という結果となった。
やはり、少し遅くなっている印象である。