18

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

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

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

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

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

我还可以强制用户指定最大值并使用上述顺序，这会显着影响我的实现吗？（我听说 map 是基于 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++ 数组将是最佳选择，因为实现将使用密集键。谢谢

4

3 回答 3

10

unordered_map 的插入应该是O(1)并且检索应该大致是O(1)，（它本质上是一个哈希表）。

结果，您的时间安排是关闭的，或者您的实现或使用 unordered_map 有问题。

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

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

您应该考虑的一个问题是，您的实现可能需要不断地重新散列结构，正如您所说的那样，您有100mil+ items。在这种情况下，在实例化容器时，如果您大致了解将在容器中插入多少“唯一”元素，则可以将其作为参数传递给构造函数，容器将相应地用桶实例化-大小合适的表。

于 2010-02-28T06:10:46.583 回答
2

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

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

除以 max_load_factor 是为了说明哈希表操作所需的空单元格。

于 2012-06-21T17:49:41.277 回答
1

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

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

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

Edit2：您添加了一些问题的代码。你while (! LabelFile.eof() )的坏了。您通常想做类似的事情while (LabelFile >> inputdata)。您读取数据的效率也有些低 - 您显然期望的是两个由制表符分隔的数字。在这种情况下，我会写这样的循环：

while (LabelFile >> node >> label)
    Label[node] = label;
于 2010-02-28T06:12:32.510 回答