はじめに

この記事は競プロ Advent Calendar 2022 八日目の記事です。卒業研究の中で競プロをしていてちょっとだけ役立ったことを書きます。

競プロ要素がどこにあったか

現在自分が進めている卒業研究では、処理にかかる実行時間を測定することでうまくいったかどうかの評価を行います。同じ研究室の先輩が書いた論文を読んだところ、プログラムを100回程度繰り返し動作させた場合の処理時間の最大値、最小値、平均値が記載されていたので、自分もそれにならって最大値、最小値、平均値を求めることにしました。その中でも、平均値を求めるところで落とし穴があったのでそれを書きます。

実行時間を測定する

研究ではC言語を使っているので、C言語で細かい単位で時間を測定できる方法を探しました。その結果、 timespec という構造体と clock_gettime() という関数を使うことでナノ秒単位で時間を測定できることが分かったため、これを採用しました。疑似的なソースコードで表現すると下のようになります。

#include <stdio.h>
#include <time.h>
int main()
{
    struct timespec before, after;
    clock_gettime(CLOCK_REALTIME, &before);
    // ここに処理時間を測定したい関数を入れる
    clock_gettime(CLOCK_REALTIME, &after);
    printf("%ld.%9ld\n", before.tv_sec, before.tv_nsec);
    printf("%ld.%9ld\n", after.tv_sec, after.tv_nsec);
    return 0; 
}

あとは after - before を計算するだけ、と言いたいのですが、構造体なのでそう簡単には計算できません。timespec は時間を秒で表現したときの整数部分を表すメンバ変数と小数点以下を表すメンバ変数に分かれているので、繰り上がりが起きた場合のことを考慮する必要があります。これを踏まえた上で、 after - before を計算するコードを書くと以下のようになります。

#include <stdio.h>
#include<time.h>
int main() { 
    struct timespec before, after, result;
    clock_gettime(CLOCK_REALTIME, &before);
    // ここに処理時間を測定したい関数を入れる
    clock_gettime(CLOCK_REALTIME, &after);
    printf("%ld.%9ld\n", before.tv_sec, before.tv_nsec);
    printf("%ld.%9ld\n", after.tv_sec, after.tv_nsec);
    if(after.tv_nsec < before.tv_nsec) {
        result.tv_nsec = after.tv_nsec - before.tv_nsec + 1000000000;
        result.tv_sec = after.tv_sec - before.tv_sec - 1;
    } else {
        result.tv_nsec = after.tv_nsec - before.tv_nsec;
        result.tv_sec = after.tv_sec - before.tv_sec;
    }
    printf("%ld.%9ld\n", result.tv_sec, result.tv_nsec);
    return 0;
}

平均値を求める

実行時間を測定することができたので、それを元に平均値を求めます。

WAになる実装

研究では100回繰り返して平均値を求めるのですが、この記事の中では10回だけ繰り返して計算することにします。

#include <stdio.h>
#include <time.h>
#include <unistd.h>
int main() { 
    struct timespec before, after, result[100], average;
    int i;
    average.tv_sec = 0, average.tv_nsec = 0;
    for(i = 0; i < 10; i++) {
        clock_gettime(CLOCK_REALTIME, &before);
        // ここに処理時間を測定したい関数を入れる
        usleep(999499);
        clock_gettime(CLOCK_REALTIME, &after);
        if(after.tv_nsec < before.tv_nsec) {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec + 1000000000;
            result[i].tv_sec = after.tv_sec - before.tv_sec - 1;
        } else {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec;
            result[i].tv_sec = after.tv_sec - before.tv_sec;
        }
        average.tv_sec += result[i].tv_sec;
        average.tv_nsec += result[i].tv_nsec;
        printf("%ld.%9ld\n", result[i].tv_sec, result[i].tv_nsec);
    }
    average.tv_sec /= 10, average.tv_nsec /= 10;
    printf("%ld.%9ld\n", average.tv_sec, average.tv_nsec);
    return 0;
}

これを実行すると

1.   328800
0.999643800
1.   716000
0.999598500
0.999711900
0.999845900
0.999581600
0.999785400
1.   607300
1.   112100
0.599993130

という結果となりました。このように、1.0秒以上のケースと0.9秒のケースが混ざると明らかに間違った答えが返ってきてしまいます。

ACになる実装

timespec の変数を一度 long long 型に変換してから平均値を求めることで、このバグを修正できます。

#include <stdio.h>
#include <time.h>
#include <unistd.h>
int main() { 
    struct timespec before, after, result[100];
    long long average;
    int i;
    average = 0;
    for(i = 0; i < 10; i++) {
        clock_gettime(CLOCK_REALTIME, &before);
        // ここに処理時間を測定したい関数を入れる
        usleep(999499);
        clock_gettime(CLOCK_REALTIME, &after);
        if(after.tv_nsec < before.tv_nsec) {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec + 1000000000;
            result[i].tv_sec = after.tv_sec - before.tv_sec - 1;
        } else {
            result[i].tv_nsec = after.tv_nsec - before.tv_nsec;
            result[i].tv_sec = after.tv_sec - before.tv_sec;
        }
        average += (long long)result[i].tv_sec * 1000000000;
        average += (long long)result[i].tv_nsec;
        printf("%ld.%9ld\n", result[i].tv_sec, result[i].tv_nsec);
    }
    average /= 10;
    printf("%lld.%9lld\n", average / 1000000000, average % 1000000000);
    return 0;
}

これを実行すると

0.999956600
1.   362300
0.999662700
0.999860000
1.   495200
0.999632900
0.999929000
0.999637000
1.   339900
1.   311800
1.    18740

という結果となりました。これは信用できそうです。

まとめ

感想

解法自体は特に難しくないのですが、研究ではジャッジサーバは存在しないため、バグが生まれそうなケースを自分で考えなければなりません。バグが残っている状況を考えるところで競プロが役に立ったと感じました。

その後

教授に相談した結果、ソースコードの中に平均値を求める実装を書くのではなく、

1回ごとに実行時間を画面に出力し
結果をExcelに貼り付けて計算

したほうが良いということでした。そのほうが実行時間の分布も見ることができる上に、実行時間を記録として残すことができるというメリットもあるそうです。（実は競プロは役に立たない？？？）

最後まで読んでいただき、ありがとうございました。

polyester-kpr’s blog

競プロをしていて役に立ったこと