11

BST で検索を実行するのに必要な時間を正確に把握できるコードを作成する方法を見つけようとしています。現在、時間を使用しており、要素の総数は10 ^ 5のオーダーです。それは次のようになります:-

clock_t begin, end;
begin = clock();
...
...
...
end = clock();
difference = (end-begin)/CLOCKS_PER_SECOND;

ただし、これでは求めている精度が得られません。他に使用できる libc 関数はありますか?

4

6 に答える 6

3

ライブラリがサポートしている場合、C11 にはtimespec_get()、システム クロックの解像度に応じて、最大でナノ秒まで測定されるものがあります。

于 2013-08-24T12:43:12.347 に答える
2

アルゴリズムのベンチマークを行うには、少なくとも数百ミリ秒の範囲になるように何度か繰り返す必要があります。(これは標準的な方法です)。ユーザー空間でのみ発生するアルゴリズム (スレッド、システム コールなどなし) のベンチマークを行うには、秒とマイクロ秒を含む値を使用してgetrusage(RUSAGE_SELF, &r)使用する必要があります。r.ru_utime

于 2013-08-24T09:57:27.287 に答える
0

QtにはQElapsedTimer、ナノ秒までの測定をサポートするものがあります。それがどれほど正確かは証明できませんが、IIRC はさまざまなプラットフォームでさまざまな実装を使用しています。悲しいことに、それはあなたに合わないかもしれないC++です。また：

ナノ秒の解像度を提供しないプラットフォームでは、返される値は利用可能な最良の推定値になります。

このclock()機能は大まかな測定には問題ありませんが、ミリ秒の範囲で機能します。その名前に反して、最新のプロセッサのクロック周波数はかなり変動する可能性があり、CPU クロックのみに依存して実際の時間を正確に判断することは不可能であるため、CPU クロックで測定するとは思いません。IMO この概念は、CPU 周波数が一定で、電源管理や「ターボ ブースト」自動オーバークロックなどがなかった時代にさかのぼります。

編集:これも見つかりました(time.h):

    int clock_gettime(clockid_t clk_id, struct timespec *tp);

    ... and the target struct...

    struct timespec {
            time_t   tv_sec;        /* seconds */
            long     tv_nsec;       /* nanoseconds */
    };

... and the clock options...


CLOCK_REALTIME
    System-wide realtime clock. Setting this clock requires appropriate privileges. 
CLOCK_MONOTONIC
    Clock that cannot be set and represents monotonic time since some unspecified starting point. 
CLOCK_PROCESS_CPUTIME_ID
    High-resolution per-process timer from the CPU. 
CLOCK_THREAD_CPUTIME_ID
    Thread-specific CPU-time clock.
于 2013-08-24T12:20:25.500 に答える
0

BST? どのような精度が必要ですか? 32 ビット システムで 10^6 である CLOCKS_PER_SECOND で除算すると、6 桁の精度が得られますか?

結果を double にキャストしますか?

試す

difference = (double)(end-begin)/CLOCKS_PER_SECOND;

difference は double を保持できる必要があることに注意してください。

于 2013-08-24T09:49:08.173 に答える
0

あなたがやっていることは、私が最近やっていることとよく似ています。

int gettimeofday(struct timeval *tv, struct timezone *tz);機能はあなたのニーズに合っていると思います。時間情報は に入れられ、struct timeval tv秒とマイクロ秒で時間を取得します。struct timevalマニュアルページから：

struct timeval {
               time_t      tv_sec;     /* seconds */
               suseconds_t tv_usec;    /* microseconds */
};

を使用した時間測定の短い例gettimeofday:

struct timeval time;
if(gettimeofday( &time, 0 )) return -1;

long cur_time = 1000000 * time.tv_sec + time.tv_usec;
double sec = cur_time / 1000000.0;

より長い例は簡略化されており、便利に使用できるように C++ クラスとして簡単にラップされています。コードは私の github: https://github.com/lulyon/LinuxTimeCounterに配置されており、実際のプロジェクトで使用されています。

于 2013-08-24T12:47:13.860 に答える