c++ - 大堆栈和稀疏散列的性能缓慢

Question

我有一大堆 unsigned long long (100M+) 我试图放入 SparseHash，但性能非常慢，因为对于每 1k 个条目，在具有 16Gb RAM 的 MacBook Pro 上大约需要 4-6 秒.

    while (stackUI.size()>0) {
       Set.insert(stackUI.top());
       stackUI.pop();
       if (stackUI.size()%1000==0) {
           cout<<stackUI.size()<<" "<<time(0)<<endl;
    }
}

我在实施中做错了什么，还是有更好的方法？

Answer 1

您是否将性能与 gcc hash_set 进行了比较？

当负载因子变高（如 0.5）时，散列容器的大小翻倍并复制所有内容。由于您已经知道哈希集将容纳多少元素（我猜是您的堆栈大小），因此请尝试在开始插入之前保留这些桶。这样，您将避免重新散列并获得显着的加速。