1

私は現在、車両のルーティングの問題に対して特定の動的計画法のアプローチをコーディングしようとしています。ある時点で、同じ段階で最良の 100 個の部分ルートを維持するために、minmaxheap に追加したい部分ルートがあります。ほとんどのプログラムはスムーズに実行されますが、実際に部分的なルートをヒープに挿入したい場合は、処理が少し遅くなる傾向があります。その特定のコードを以下に示します。

 clock_t insert_start, insert_finish, check1_finish, check2_finish;

insert_start = clock();
check2_finish = clock();

if(heap.get_vector_size() < 100) {
    check1_finish= clock();
    heap.insert(expansion);
    cout << "node added" << endl;
}
else {
    check1_finish = clock();
    if(expansion.get_cost() < heap.find_max().get_cost() ) {
        check2_finish = clock();
        heap.delete_max();
        heap.insert(expansion);
        cout<< "worst node deleted and better one added"   <<endl;
    }
    else {
        check2_finish = clock();
        cout << "cost too high check"<<endl;
    }
}

number_expansions++;

cout << "check 1 takes " << check1_finish - insert_start << " ms" << endl;
cout << "check 2 takes " << check2_finish - check1_finish << "ms " << endl;

insert_finish = clock();

cout << "Inserting an expanded state into the heap takes " << insert_finish - insert_start << " clocks" << endl;

典型的な出力は次のとおりです。

cost too high check 
check1 takes 0 ms 
check2 takes 0ms 
Inserting an expanded state into the heap takes 0 clocks

cost too high check 
check1 takes 0 ms 
check2 takes 0ms 
Inserting an expanded state into the heap takes 16 clocks

cost too high check 
check1 takes 0 ms 
check2 takes 0ms 
Inserting an expanded state into the heap takes 0 clocks

このブロックが他の場所で実装されている関数を使用している場合、コードについて何かを言うのは難しいことはわかっていますが、なぜこれが 1 ミリ秒未満かかるのか、場合によっては 16 ミリ秒かかるのかについて私は驚いています。プログラムはこのブロックを何千回も実行する必要があるため、これらの小さな問題が実際に非常に遅くなります。

私の唯一の推測は、これらすべての状態を格納するヒープ クラスのベクトルで何かが起こるということですが、コンストラクターで vector::reserve を使用して 100 個のアイテムの場所を予約しているので、これがどのように問題になるかわかりません。

ありがとう！

4

4 に答える 4

1

プリエンプト。プログラムがオペレーティングシステムによってプリエンプトされる可能性があるため、他のプログラムが少しの間実行される可能性があります。

また、16ミリ秒ではありません。16クロックティックです： http ：//www.cplusplus.com/reference/clibrary/ctime/clock/

msが必要な場合は、次のことを行う必要があります。

cout << "Inserting an expanded state into the heap takes "
     << (insert_finish - insert_start) * 1000 / CLOCKS_PER_SEC
     << " ms " << endl;

最後にinsert_finish、他の結果を印刷した後に設定します。if/elseブロックの直後に設定してみてください。coutコマンドは、別のプロセスに取って代わられるのに適したタイミングです。

于 2011-04-05T16:10:23.947 に答える
0

CPU時間ではなく、「壁時間」を測定しているようです。Windows自体はリアルタイムOSではありません。デバイスドライバのような優先度の高いものによる時折の大きな問題は、まったく珍しいことではありません。

Windowsでは、コードのボトルネックを手動で探している場合は、代わりにRDTSCを使用します。さらに良いのは、手動ではなく、プロファイラーを使用することです。

于 2011-04-05T16:10:58.387 に答える
0

私の唯一の推測は、これらすべての状態を格納するヒープ クラスのベクトルで何かが起こるということですが、コンストラクターで vector::reserve を使用して 100 個のアイテムの場所を予約しているので、これがどのように問題になるかわかりません。

std::vector を使用して実装していますか? 挿入には std::vector の直線的な時間がかかります。また、ソートされたコンテナーを使用していない場合、delete max には時間がかかる場合があります。

std::set または std::multiset を使用することをお勧めします。挿入、削除、検索は常に ln(n) を取ります。

于 2011-04-05T16:12:08.420 に答える
0

時計機能はあまり正確ではないと思うので、QueryPerformanceCounter を使用して時間を測定してみてください。おそらく、クロックの精度は Windows スケジューラと同じです。シングル CPU の場合は 10 ミリ秒、マルチコア CPU の場合は 15 または 16 ミリ秒です。QueryPerformanceCounter と QueryPerformanceFreq を併用すると、ナノ秒の分解能が得られます。

于 2011-04-05T16:13:24.150 に答える