在c ++中map和unordered_map之间的性能差异?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (25)

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

我同时使用了地图和tr1提出的新的unordered_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(); 
}
提问于
用户回答回答于

unordered_map的插入应该是O(1),并且检索应该大致为O(1),(它本质上是一个散列表)。

你的时间,结果是方式关闭,或者有什么与你的实现或unordered_map的使用。

你需要提供更多信息,以及可能你如何使用容器。

根据n1836的6.3节,插入/复位的复杂性如下:

你应该考虑的一个问题是你的实现可能需要不断重新调整结构,就像你说你有100mil +物品一样。在这种情况下,当实例化容器时,如果你对将要在容器中插入多少“独特”元素有一个大致的了解,则可以将其作为参数传递给构造函数,并且容器将相应地通过一个存储桶来实例化,适当大小的表格。

用户回答回答于

加载unordered_map的额外时间是由于动态数组调整大小。调整大小的时间表是在表格超过其加载因子时每个单元格的数量加倍。因此,从一张空白表格中,需要整个数据表的O(lg n)个副本。您可以通过预先设置哈希表的大小来消除这些额外的副本。特别

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

除以max_load_factor是为了解决散列表操作所需的空单元。

扫码关注云+社区