1

我目前正在尝试为车辆路线问题编写某种动态编程方法。在某个时刻，我有一个部分路由，我想将它添加到 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 个项目保留了位置，所以我看不出这仍然是一个问题。

谢谢！

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 本身不是实时操作系统。设备驱动程序等高优先级的事情偶尔会出现大问题并不少见。

在 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 回答