无序地图占用大量空间

我创建了unit64_t到uint64_t的地图。这是我为assesing空间复杂度编写的代码：无序地图占用大量空间

#include <bits/stdc++.h> 
#include "sparsehash/internal/sparseconfig.h" 
#include "sparsehash/sparse_hash_map" 

using namespace std; 

int main(int argc, char *argv[]){ 

    std::string input,reference; 

    while (getline(cin,input)) { 
    reference += input; 
    input.clear(); 
    } 

    cout<<"length of reference = "<<reference.length()<<endl; 
    unordered_map<uint64_t, uint64_t> m; 
    //google::sparse_hash_map<uint64_t, pair<short,long>> m; 

    for (auto it = reference.begin(); it != reference.end(); it++) { 
     m[it-reference.begin()]= it-reference.begin(); 
    } 

    return 0; 
}

当我跑这跟在/ usr/bin/time会，这是由程序产生的输出：

length of reference = 4641652 
    Command being timed: "./a.out" 
    User time (seconds): 2.97 
    System time (seconds): 0.15 
    Percent of CPU this job got: 99% 
    Elapsed (wall clock) time (h:mm:ss or m:ss): 0:03.13 
    Average shared text size (kbytes): 0 
    Average unshared data size (kbytes): 0 
    Average stack size (kbytes): 0 
    Average total size (kbytes): 0 
    Maximum resident set size (kbytes): 251816 
    Average resident set size (kbytes): 0 
    Major (requiring I/O) page faults: 0 
    Minor (reclaiming a frame) page faults: 68259 
    Voluntary context switches: 1 
    Involuntary context switches: 104 
    Swaps: 0 
    File system inputs: 0 
    File system outputs: 0 
    Socket messages sent: 0 
    Socket messages received: 0 
    Signals delivered: 0 
    Page size (bytes): 4096 
    Exit status: 0

无序地图似乎占用了250MB的空间。这似乎是非常高的。为何会发生这种情况。与谷歌稀疏哈希相同的代码只需要89MB的空间，这是更合理的。

我不明白为什么C++无序地图占用这么多空间？

来源

2015-10-02 user1995120

我没有看到任何内容表明内存使用量应该多于或少于250mb。你为什么认为这是很多记忆？你在地图上放置了多少个元素？你有没有考虑到分配填充和地图的内务管理？你有没有考虑给我们提供相关信息？ –

是的，输入是一个大小为4.5Mb的字符串。我把每个职位都放在地图上。 – user1995120

@ user1995120：如果你在一个远远小于4GB的字符串中存储位置（最大可寻址32位数字），并且关心内存使用情况，为什么要使用64位值？（如果要保留处理大于4GB字符串的能力，您仍然可以使用模板创建代码的32位和64位版本，并在运行时使用最佳版本。 –

您有4641652条目。所以总的原始数据大小是4641652*2*8 byte ~= 74 MB。

散列表有一个重要的事实。快速哈希表有很多哈希桶，并且具有少量哈希桶的哈希表很慢。

它基本上都归结为散列冲突。如果你有很多散列桶（并且你有一个很好的散列函数），那么很少发生散列冲突。因此查找真的很快。在其他方面，如果你的表很小（不是很多哈希桶），那么哈希碰撞定期发生。因此查找功能要慢很多。

现在std::unordered_map被人为地认为是一个快速散列表，所以它有很多开销。有更多的哈希桶比条目。在这种情况下，开销约为250/74 ~= 3.3x，这似乎很正常。

但是sparsehash被设计为具有尽可能少的开销（每个条目约2位）。但是，这当然意味着它要慢得多。

如果你使用哈希映射，你应该总是考虑一下，如果你想要速度或者你想要高效的内存。

来源

2015-10-02 01:36:29 user38034

还有每个桶中的冲突（可能是一个指针）的总开销为〜37MB或总共〜121MB，和未使用的桶（因为桶列表中有许多空桶）。还有上次更新映射时较旧的较短桶阵列使用的内存。 – 1201ProgramAlarm

@ 1201ProgramAlarm：取决于实施。通过链表处理冲突将按照你所描述的方式进行，但通过链接进行冲突处理（因此散列冲突以可预测的方式将第二个条目置于其他地方）不会有这种开销（尽管它需要使用先前填充的存储桶的标记因此如果原始条目随后被删除，则链接算法可以找到移位的条目）。Python使用链接而不是列表;如果有些供应商至少在某些情况下做了同样的事情，也不会感到惊讶。 – ShadowRanger

@ShadowRanger：[“chaining”]（https://en.wikipedia.org/wiki/Hash_table#Separate_withining_with_linked_lists）是用于链接碰撞元素列表的另一个术语 - 您所描述的（并且由python使用）是已知的作为*开放寻址*或*关闭散列*。并且没有'std :: unordered_map'实现使用该技术 - 它与标准的要求不兼容（具体来说，默认的'max_load_factor'为1.0，并且只有在超过时才重新刷新）。 –

无序地图占用大量空间

回答

相关问题