どのように異なるアルゴリズムの効率をテストする

Question

どのように異なるアルゴリズム、例えばソートアルゴリズムの効率をテストするには？私はclock_gettimeで試してみます。それは正確ですか？この問題を解決する方法はありますか？

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

/* compute interval: end - start */ 
struct timespec diff(struct timespec start, struct timespec end); 

/* tested algorithm, just an example. Print 10000 lines "hello" */ 
void testFunc(void); 

int main(void) 
{ 
    struct timespec start; 
    struct timespec end; 

    struct timespec interval ; 

    clock_gettime(CLOCK_REALTIME, &start); 

    /* call the tested algorithm */ 
    testFunc(); 

    clock_gettime(CLOCK_REALTIME, &end); 

    interval = diff(start, end); 
    printf("%lld.%.9ld(seconds)\n", (long long)interval.tv_sec, interval.tv_nsec); 

    return 0; 
} 

/* compute interval: end - start */ 
struct timespec diff(struct timespec start, struct timespec end) 
{ 
    struct timespec temp; 

    if ((end.tv_nsec - start.tv_nsec) < 0) { 
     temp.tv_sec = end.tv_sec - start.tv_sec - 1; 
     temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec; 
    } 
    else { 
     temp.tv_sec = end.tv_sec - start.tv_sec; 
     temp.tv_nsec = end.tv_nsec - start.tv_nsec; 
    } 

    return temp; 
} 

/* tested algorithm, just an example. Print 10000 lines "hello" */ 
void testFunc(void) 
{ 
    int i; 

    for (i = 0; i < 10000; i++) { 
     printf("hello\n"); 
    } 
} 

Answer 1

アルゴリズムをテストするときは、問題の正確なアルゴリズムを除いて、不要なコードをすべて削除することをお勧めします（たとえば、プログラムの起動、ファイルの読み込み、データの初期化からアルゴリズム自体を切り離します。アルゴリズム自体がテストされている）。それはコマンドラインから行うことができないtimeを使用して1つの制限です。

clock_gettimeは、ナノ秒の粒度が可能なため、機能が優れています。しかし、clock()機能は、タイミングアルゴリズムでも使用できます。 clock()のための一般的な使用である：

#include <time.h> 
... 
int main() { 
    double t1 = 0.0, t2 = 0.0; 
    srand (time (NULL)); 
    ... 
    t1 = clock();     /* get start time (as double) */ 
    quicksort (a, 0, TESTLIM - 1); /* test whatever you need  */ 
    t2 = clock();     /* get end time (as double) */ 
    printf ("\n quick1 (%lf sec)\n", (t2-t1)/CLOCKS_PER_SEC); 

返される時間の差はコード実行のために粗い壁時間です。正確な壁面時間ではありません。CLOCKS_PER_SECは、実行中のマシンに関係なく一定の値として指定されています。 clock_gettimeまたはclockのいずれかを使用して

が動作します（POSIXはCLOCKS_PER_SECが1000000に等しいことを要求する）が、他の回答で述べたように、もっぱら2つの実行に基づいて良好な近似値を得ることを期待し、繰り返しの多くを使用しないでください。

ここで、clock_gettimeは、より柔軟性を提供します。これは、使用するクロックの選択を許可することです。 CLOCK_MONOTONIC_RAW、CLOCK_PROCESS_CPUTIME_IDなど、必要に応じてタイマーを中断させないようにすることができます。 （さまざまなクロックの動作の詳細については、man clock_gettimeを参照してください）clock_gettimeで同様の実装を使用できます。

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

typedef struct timespec timespec; 

timespec diff (timespec start, timespec end); 

int main (void) { 
    timespec time1, time2, tmp; 
    int temp; 
    clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &time1); 
    for (int i = 0; i < 242000000; i++) 
     temp += temp; 
    clock_gettime (CLOCK_PROCESS_CPUTIME_ID, &time2); 
    tmp = diff (time1, time2); 
    printf (" timediff %ld:%ld\n", tmp.tv_sec, tmp.tv_nsec); 
    return 0; 
} 

timespec diff (timespec start, timespec end) 
{ 
    timespec temp; 
    if ((end.tv_nsec - start.tv_nsec) < 0) { 
     temp.tv_sec = end.tv_sec - start.tv_sec - 1; 
     temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec; 
    } else { 
     temp.tv_sec = end.tv_sec - start.tv_sec; 
     temp.tv_nsec = end.tv_nsec - start.tv_nsec; 
    } 
    return temp; 
} 

（profiling-code-using-clock_gettimeの例の礼儀、この例をテストする場合、最適化を無効）

の両方の上に見て、あなたのニーズに最適なものを選びます。

Answer 2

よく、timeコマンドを使用できます。良い説明はhereです。まず、ソースコードを実行可能バイナリにコンパイルします。 time ./executable_codeを実行し、1つまたは2つのテストに基づいて決定を下さないでください。がんばろう！

Answer 3

効率性の意味に応じて、さまざまなテスト方法があります。最も簡単なのは、timeコマンドを使用するParnabのアドバイスです。しかし、あなたが本当に何が起こっているのか理解したいなら、それは十分ではないかもしれません。

perf toolは、サイクル数、異なるレベルのキャッシュのキャッシュヒット/ミスの数、予測ミスしたブランチの数など、より多くのメトリックにアクセスできます。また、CのperfツールにアクセスするためのAPIもありますが、あまり詳しくは書かれていません。他のツールはPAPIのように存在しますが、私はそれらがお互いにどのように違うか分かりません。

また、並べ替えアルゴリズムはデータ依存（つまり、並べ替える配列によって同じ数の命令を実行しないことを意味する）なので、同じ入力でそれらを比較する必要があります。例えば、ほとんどのソートされた配列をソートする際にはいくつかの方が良いかもしれないので、非常に簡単です。