0

我目前有一个处理工作包的大型集群（50 多台计算机）。所有这些工作包结果然后由控制器计算机收集。

因此，假设数据以半随机方式到达，并且逐渐增长：

0,2,3,8,7,1,4,9,10,11,6, ...

然后我必须按顺序将数据转储到文件中。而且由于工作包超过 100M，我在缓冲区中准备好下一个后立即转储它们。

我实际上使用的std::map是这个“随机输入优先输出”，例如：

std::map<int, DataStruct> buffer;

long long next_work = 0;
while(next_work != 100000000){
    fill_buffer(buffer); //This method fills the buffer from the processing elements

    if(buffer.find(next_work) != buffer.end()){
        dump_to_file(buffer[next_work]); // Dumps it to file
        buffer.erase(next_work++);
    }
};

这个缓冲区有时（由于网络延迟、PC 延迟、断开连接等）会增长到 100000+ 个元素，这会减慢操作速度。所以，我想知道 STL 是否有更好的类来处理这种类型的操作。

在这里使用std::map合适吗？

有没有更好/ CPU 效率更高的方法？（我真的不在乎它是否有内存效率）

4

1 回答 1

1

由于没有比next_work缓冲区少的工作，因此您的地图只能包含这样一个元素作为其第一个元素。您可以改为使用begin()来访问您的迭代器，在恒定时间内获得第一个元素（然后测试它是否是您想要的那个）。但是仍然在减慢速度的是插入，它在缓冲区的当前大小中仍然是对数的。

另一种关联数据结构是哈希映射。它支持预期的恒定时间插入和查找。它不是按键排序的，但由于您只需要查找一个确切的键，这不会成为问题。

如果您的编译器支持 C++11（并且您不需要支持 C++11 之前的编译器），则有std::unordered_map. 可能只是更换课程就可以解决所有问题。也许您需要调整对代码中未显示的数据结构的其他访问，即我们不知道您如何在fill_buffer.

对于 C++03，您可以尝试boost::unordered_map。

于 2013-11-13T17:02:49.233 回答