1

ハッシュに基づいて、一連の特異値または構造体/クラス（一度に複数の値がハッシュされることを意味します）にインデックスを付けたいと思います。

ハッシュ関数をコーディングしたので、値、構造体、またはクラスのダイジェストを提供するのに問題はありません。問題は次のとおりです。

  • C ++ではハッシュベースのデータ構造が実際にサポートされていますか？std::mapたとえば、の些細な使用に代わるより良い方法があり、そのために2つ以上のフィールドを持つように設計されたコンテナがあるかどうかを意味 します（データ構造に実際に必要なフィールドの数はまだ決定していません）。
  • 断片化されたデータ構造を管理して10^5レコードに簡単に到達することを計画しているので、メモリ内の巨大なデータ構造を直接処理することを避け、構造の不要な部分を割り当てることが重要です。
  • この構造をディスクに保存したい場合は、シリアル化が唯一のオプションですか？

私のハッシュ関数がhash::digest()、適切なデータ構造の使用法に関する例を含む実際のコードへの最小限の参照に感謝するとします。

ありがとう。

編集：

次の理由から、順序付けられていないデータ構造を避けたいと思います。

  • 悪い分岐予測
  • それらは注文されていないため、効果的な方法で分割することはできません
  • 私の主な焦点は、この構造とその断片化の管理についてです。
4

2 に答える 2

2

コメントが本当に私たちをどこにでも連れて行っているとは思わないので、私はこれを答えとして書くつもりです：

まず、あなたは間違った木を吠えているのか、座って私たちのために小さな図を描く必要があるのか​​、私たちはあなたが何を求めているのかを理解していると思います。

一般に、私や他の多くの人は、「十分に機能しないことが証明されるまで、機能するときにstd :: vectorを使用します（インデックス付けは妥当なタイプ/範囲です）。インデックスがベクトルに対して機能しない場合は、stdを使用します。 :: map、これが適切な解決策ではないことが証明されない限り」。ただし、さらに重要なのは、使用するストレージが何であれ、メインコードから非表示にする必要があることです。データをフェッチするためのアクセサー関数が必要です。ベクター、マップ、トライ、Bツリー、ヒープ、スタック、キューなどを使用するかどうかは関係ありません。プログラムに必要な機能がインターフェイスでは、あらゆる種類のコンテナクラスにデータを格納できる必要があります。この原則により、コンテナーを使用するコードが破損するかどうかを心配することなく、必要なときに/必要に応じて実際のストレージコンテナーを変更できます。

データ構造の格納に関しては、使用しているコンテナの形式に関係なく、PODだけでなくすべてをシリアル化する必要があります。したがって、std :: stringなどのクラスを格納する場合、内部構造をファイルに格納するだけでは不十分なため、データをシリアル化する必要があります。

于 2012-12-25T01:09:16.893 に答える
1

説明の中で、「ハッシュ」関数（「ダイジェスト」と呼ばれることもあります）を使用して何かが必要であると述べています。これは、ある種のハッシュコンテナを使用することを示しているようです。ハッシュされたコンテナは本質的に順序付けされていませんが、標準ライブラリのように順序付けされていないコンテナを使用したくないとも述べていますstd::unordered_map<...>。ハッシュ関数で何が欲しいですか？

また、コンテナを「断片化」したいとおっしゃっていますが、この断片化の意味がよくわかりません。その音から、コンテナが実際には部分的にディスク上に保持されており、そのサイズのためにメモリにのみ取り込まれていることを示唆しているようです。ただし、10 ^ 5は大きなサイズではなく、実際にはかなり小さなサイズであることに注意してください。

「ハッシュ」関数が実際に順序を提供することを意味する場合、つまり、キーに厳密な弱い順序を提供し、コンテンツをバイトのシーケンスとして表示できる場合（たとえば、適切なシリアル化と逆シリアル化を使用して）、次のようになります。bツリーの検索：データセグメントに基づくデータ構造。このデータ構造のC++実装は確かにありますが、標準C++ライブラリにはありません。また、利用可能なコードもありません。また、bツリーを作成するのは簡単ではありません。

于 2012-12-25T01:58:49.480 に答える