我目前正在尝试为车辆路线问题编写某种动态编程方法。在某个时刻,我有一个部分路由,我想将它添加到 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
我知道当这个块使用在其他地方实现的函数时,很难对代码说些什么,但我很惊讶为什么这有时需要不到一毫秒,有时需要长达 16 毫秒。程序应该执行这个块数千次,所以这些小问题确实大大减慢了速度。
我唯一的猜测是,存储所有这些状态的堆类中的向量发生了一些事情,但是我使用 vector::reserve 在构造函数中为 100 个项目保留了位置,所以我看不出这仍然是一个问题。
谢谢!