番兵と時間計測と関数ポインタ

#include <time.h>
#include <sys/time.h>
#include <stdio.h>

//関数ポインタの型(SEARCH_ARRAYは返り値intで引数(int*,int,int)の関数型という定義)
typedef int (*SEARCH_ARRAY)(int*,int,int);

//時間計測用関数
//http://kzk9.net/column/time.htmlより
double gettimeofday_sec()
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec + (double)tv.tv_usec*1e-6;
}

int search_array1(int* array,int length,int n){
    int i;
    for(i=0;i<length;++i)
        if(n==array[i])
            return i;
    return -1;
}

int search_array2(int* array,int length,int n){
    int i;
    array[length+1] = n;        //配列最後尾に番兵をセット
    for(i=0;n!=array[i];++i);       //終了条件が必要なくなる
    return (i>length)? - 1 : i ; //番兵かどうかチェック
}

void time_logging(SEARCH_ARRAY search_array,int* array,int length,int n){
    int i;
    double t1,t2;
    t1 = gettimeofday_sec();
    i = search_array(array,length,n);
    t2 = gettimeofday_sec();
    printf("time = %10.30f\n", t2 - t1);
    printf("return i == %d\n", i );
}

int main(void)
{
    int i, length = 2000000;
    int array[length];
    for(i=0;i<length-1;++i)
        array[i] = i;
    time_logging(search_array1,array,length-1,length);
    time_logging(search_array2,array,length-1,length);
}

実行結果:(gccコンパイラオプション-O2の最適化)
time = 0.005414009094238281250000000000 //番兵なし
return i == -1
time = 0.004438161849975585937500000000 //番兵あり
return i == -1

• 本当は動的に配列を増やせる言語を使った方がよい
• 番兵を使うと配列について回すループで条件文が減るので少しだけ高速化できる
• 関数ポインタは、関数の返り値と引数が同じ型のものをまとめて同じものとみなす
• どちらかというとJavaのインターフェースっぽい