c++ - C++ 的性能问题(使用 VC++ 2010): at runtime, 我的程序似乎随机等待了一段时间

Question

我目前正在尝试为车辆路径问题编写某种动态编程方法。在某个时刻，我有一条部分路线要添加到 minmaxheap 中，以便将最好的 100 条部分路线保持在同一阶段。大多数程序运行顺利，但当我真正想将部分路由插入堆时，事情往往会变得有点慢。该部分代码如下所示:

 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

我知道当这个 block 使用在别处实现的函数时很难对代码说些什么，但我很惊讶为什么这有时需要不到 1 毫秒，有时需要长达 16 毫秒。该程序应该执行此 block 数千次，因此这些小问题确实会极大地减慢速度。

我唯一的猜测是存储所有这些状态的堆类中的 vector 发生了一些事情，但我在构造函数中使用 vector::reserve 为 100 个项目保留了位置，所以我不明白这怎么可能仍然是一个问题。

谢谢!

Answer 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 block 之后立即设置它。 cout 命令是被另一个进程抢占的好时机。