我目前正在尝试为车辆路径问题编写某种动态编程方法。在某个时刻,我有一条部分路线要添加到 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 个项目保留了位置,所以我不明白这怎么可能仍然是一个问题。
谢谢!
最佳答案
抢占。您的程序可能会被操作系统抢占,因此其他一些程序可以运行一会儿。
此外,它不是 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 命令是被另一个进程抢占的好时机。
关于c++ - C++ 的性能问题(使用 VC++ 2010): at runtime, 我的程序似乎随机等待了一段时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/5554822/