4

私は多数のレコード、たとえば約4,000,000を持っていますが、それらに繰り返し対処し、そのレコードにリンクされているクラスに情報を入れたいと思っています。どのようなデータ構造を使用すべきかわかりませんか?ベクトル、マップ、またはハッシュマップを使用する必要があります。レコードを挿入する必要はありませんが、これらのレコード番号(または名前)のセットを含むテーブルを読み取り、そのレコードにリンクされているデータの一部を取得して、それらに対していくつかのプロセスを実行する必要があります。マップ上での検索は、この例のハッシュマップを使用しないほど高速ですか?レコードには構造としてクラスがあり、値としてクラスを持つマップまたはハッシュマップを使用したことはありません(可能な場合)。よろしくお願いします。

編集:

今のところ、すべてのレコードを同時にメモリに保持する必要はありません。>最初に構造を指定してから、いくつかのレコードからデータを取得する必要があります。レコードの総数は約2,000万です。これらの生のレコードをそれぞれ読み取り、その基本情報が作成する新しいマップまたはベクトルに存在しない場合は、残りのデータをそこに配置します。ベクトル。私は2000万件のレコードを持っているので、すべてのレコードについて400万件のレコードを調べて、そのレコードの基本情報が存在するかどうかを確認するのは非常に困難だと思います。私は約400万種類のパッケージを持っており、これらの各パッケージには複数の種類のサービスがあります(パッケージあたり約5(20/4))。

4

1 に答える 1

6

これらの3つのデータ構造には、それぞれ異なる目的があります。

Avectorは基本的に動的配列であり、インデックス値に適しています。

Amapは、O(log(n))の取得時間と挿入時間を持つソートされたデータ構造です(平衡二分木、通常は赤黒を使用して実装されます)。これは、効率的なハッシュメソッドが見つからない場合に最適です。

Ahash_mapはハッシュを使用してオブジェクトを取得します。衝突率が低く、明確に定義されたハッシュ関数がある場合、平均して一定の取得時間と挿入時間が得られます。hash_mapsは通常、map常にではありませんが、より高速です。ハッシュ関数に大きく依存します。

あなたの例では、キーがレコード番号になる場所を使用するのが最善だと思いますhash_map(レコード番号が一意であると仮定します)。

これらのレコード番号が密集している場合(つまり、インデックス間にギャップがほとんどないか、まったくない場合、たとえば、1,2,4,5,8,9,10 ...)、を使用できますvector。レコードが自動インクリメントの主キーを持ち、削除が少ないデータベースからのものである場合、これは通常の場合です。

于 2012-09-05T01:16:18.037 に答える