100万データのC++ハッシュテーブル

Question

私は100万のデータオブジェクトを持っており、これらを整理してどのオブジェクトが最も多く繰り返されているかを数え、ハッシュテーブルを使ってリストする必要があります。

Answer 1

すべての操作を繰り返します。ここでは、データ構造のカップルとその長所/短所は次のとおりです。

1. ベクトル
   長所：迅速なインデックスで要素にアクセスします。それはO（1）時間に行われます。
   短所：挿入されたオブジェクトの後ろに配置されたすべてのオブジェクトを移動する必要があるため、挿入が実際に遅くなります。これはO（n）時間に行われます。データが後ろに押し込まれても、O（1）で実行されるメモリを再割り当てする必要があるため、ベクトルの挿入は遅くなりますが、この場合は定数がかなり大きくなります。

2. リスト
   pros：データを挿入する場所に関係なく、リストは非常に高速です。それはO（1）時間に行われます。
   短所：データにアクセスするのに必要な時間は、次の要素がポインタによってアクセスされるときに線形であるため、目的の値に達するまですべてをループする必要があります。これはO（n）で行われます。

3. マップと順序付けられていないマップ
   pros：それらは要素にアクセスするためにハッシュテーブルを使用するため、アクセス時間はO（1）とO（n）の間で異なります。 短所：再ハッシュする必要があるかもしれませんが、かなり遅いです。

要素にかなりアクセスしているので、ベクターを使用する方が速くなる場合があります。より良いデータ構造を提案できるように、アルゴリズムを教えてください。

もしそうでなければ、Mark Allen WeissがC++のデータ構造とアルゴリズム解析を読​​むことをお勧めします。あなたが探しているものの完全なガイドを提供します。