相关疑难解决方法(0)

我需要将原始键(int,可能很长)映射到高性能哈希映射数据结构中的struct值.

我的程序将有几百个这样的地图,每个地图通常最多只有几千个条目.但是,地图会不断地"刷新"或"翻腾"; 想象一下处理数百万add和delete消息.

C或C++中的哪些库具有适合此用例的数据结构？或者,您会如何建议自己建造？谢谢!

我最近发现了一件奇怪的事情.似乎计算Collat​​z序列长度完全没有缓存比使用缓存所有元素快 2倍.std::unordered_map

注意我确实从问题提示中是否gcc std :: unordered_map实现缓慢？如果是这样 - 为什么？我试着用这些知识来std::unordered_map表现我的能力(我使用g ++ 4.6,它确实比g ++的最新版本表现更好,我试着指定一个声音的初始桶数,我使它完全等于最大值地图必须持有的元素数量).

相比之下,使用std::vector缓存一些元素几乎比没有缓存快17倍,比使用缓慢快近40倍std::unordered_map.

我做错了什么,或者这个容器是慢的,为什么？可以让它表现得更快吗？或者,哈希映射本质上是无效的,应该尽可能避免在高性能代码中使用？

有问题的基准是:

#include <iostream>
#include <unordered_map>
#include <cstdint>
#include <ctime>

std::uint_fast16_t getCollatzLength(std::uint_fast64_t val) {
    static std::unordered_map <std::uint_fast64_t, std::uint_fast16_t> cache ({{1,1}}, 2168611);

    if(cache.count(val) == 0) {
        if(val%2 == 0)
            cache[val] = getCollatzLength(val/2) + 1;
        else
            cache[val] = getCollatzLength(3*val+1) + 1;
    }

    return cache[val];
}

int main()
{
    std::clock_t tStart = std::clock();

    std::uint_fast16_t largest …