c++ 中 map 和 unordered_map 的性能差异

Question

我有一个简单的要求，我需要一张类型的地图。但是我需要理论上最快的检索时间。

我使用了 map 和 tr1 中新提出的 unordered_map 我发现至少在解析文件和创建地图时，通过一次插入一个元素。

map 只花了 2 分钟，而 unordered_map 花了 5 分钟。

由于它将成为在 Hadoop 集群上执行的代码的一部分，并且将包含约 1 亿个条目，因此我需要尽可能短的检索时间。

还有另一个有用的信息： 目前正在插入的数据（键）的整数范围是从 1,2,... 到 ~1000 万。

我还可以强制用户指定最大值并使用上述顺序，这会显着影响我的实现吗？ （我听说地图是基于 rb 树，并且按递增顺序插入会带来更好的性能（或最差？））

这里是代码

map<int,int> Label // this is being changed to unordered_map  
fstream LabelFile("Labels.txt");  


// Creating the map from the Label.txt  
if (LabelFile.is_open())  
{  
    while (! LabelFile.eof() )  
    {             
        getline (LabelFile,inputLine);  
        try  
        {  
            curnode=inputLine.substr(0,inputLine.find_first_of("\t"));  
            nodelabel=inputLine.substr(inputLine.find_first_of("\t")+1,inputLine.size()-1);  
            Label[atoi(curnode.c_str())]=atoi(nodelabel.c_str());  
        }  
        catch(char* strerr)  
        {  
            failed=true;  
            break;  
        }  
    }  
    LabelFile.close(); 
}

暂定解决方案：在审查评论和答案后，我相信动态 C++ 数组将是最好的选择，因为该实现将使用密集密钥。谢谢

Answer 1

unordered_map 的插入应为 O(1)，检索应大致为 O(1)，（本质上是哈希表）。

结果，您的计时方式关闭，或者您的 unordered_map 的实现或使用存在错误。

您需要提供更多信息，以及可能如何使用该容器。

根据 n1836 第 6.3 节，给出了插入/检索的复杂性：

• http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1836.pdf

您应该考虑的一个问题是您的实施可能需要不断地重新哈希结构，正如您所说，您有1亿+个项目。在这种情况下，在实例化容器时，如果您大致了解将在容器中插入多少“唯一”元素，则可以将其作为参数传递给构造函数，容器将相应地用适当大小的桶表进行实例化。

Answer 2

加载 unordered_map 的额外时间是由于动态调整数组大小造成的。调整大小计划是在表超过其负载系数时将每个单元格的数量加倍。因此，从空表中，整个数据表的副本预计为 O(lg n) 份。您可以通过预先调整哈希表的大小来消除这些额外的副本。具体来说，

Label.reserve(expected_number_of_entries / Label.max_load_factor());

除以 max_load_factor 是为了考虑哈希表运行所需的空单元。

Answer 3

unordered_map（至少在大多数实现中）提供快速检索，但与 map 相比插入速度相对较差。当数据随机排序时，一棵树通常处于最佳状态，而当数据有序时，一棵树处于最差状态（您不断地在树的一端插入，增加了重新平衡的频率）。

鉴于总条目数约为 1000 万个，您可以分配一个足够大的数组，并获得非常快速的查找 - 假设有足够的物理内存，不会导致系统抖动，但按照现代标准，这并不是一个巨大的内存量。

编辑：是的，向量基本上是一个动态数组。

Edit2：您添加的代码存在一些问题。您的 while (!LabelFile.eof() ) 已损坏。您通常想要执行类似 while (LabelFile >> inputdata) 的操作。您读取数据的效率也有些低——您显然期望的是由制表符分隔的两个数字。既然如此，我会编写如下循环：

while (LabelFile >> node >> label)
    Label[node] = label;