c++ - 大きなスタックとスパースハッシュによるパフォーマンスの低下

Question

SparseHash に入れようとしている unsigned long long (100M+) の大きなスタックがありますが、16Gb の RAM を搭載した MacBook Pro では 1k エントリごとに約 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 など)、ハッシュ コンテナーのサイズが 2 倍になり、すべてがコピーされます。ハッシュセットが保持する要素の数 (私が推測するスタック サイズ) は既にわかっているので、挿入を開始する前にそれらの数のバケットを予約してみてください。そうすれば、再ハッシュを回避し、大幅な高速化を実現できます。