何百万もの文字列があるとします。各文字列には int 値があります。入力文字列でこの値を取得したいのですが、多くのスペースを必要とするため、このすべての文字列を保存したくありません。すべてまたは少なくとも多くの文字列をメモリに格納する必要があるため、ハッシュ テーブルを使用できません。私の場合、適切なデータ構造は何ですか（文字列を追加または削除する必要はありません。すでにデータを準備しており、読み取りは許可されている操作のみです）
1858 次
4 に答える
4
一般的な部分文字列を保存しないようにするには、 tryを使用します。
于 2013-03-29T15:27:10.623 に答える
3
単語リストを前処理できる場合は、CMPHなどの完全なハッシュを見てください。( gperfも別ですが、より小さなデータセット向けに最適化されているようです。)
CMPH ドキュメントから:
完全ハッシュ関数は、n 個のキーの静的セットを m 個の整数のセットに衝突なしでマップします。ここで、m は n 以上です。m が n に等しい場合、関数は最小と呼ばれます。
...
CMPH ライブラリは、最新のより効率的なアルゴリズムを、使いやすく、製品品質の高速な API にカプセル化します。このライブラリは、メイン メモリに収まらない大きなエントリを処理するように設計されています。1億を超えるキーを持つセットの最小完全ハッシュ関数を構築するために使用され、成功しています...
于 2013-03-30T00:17:48.883 に答える
1
高速かつコンパクトになるように設計されており、文字列キー用に設計されたバージョンがあるJudy treeを参照してください。その実装はsourceforgeで入手できます。
于 2013-03-29T23:55:36.623 に答える
0
現在の質問の限られた情報に基づいて、ハッシュテーブルを使用しない理由は有効ではないようです。うまく実装すればかなり効率的です。また、必要に応じて重複文字列を格納するメモリを無駄にしないという利点もあり、重複文字列が可能であればメモリ消費をさらに削減できます。
ルックアップの方法に工夫があれば、圧縮された形式の各文字列をハッシュ テーブルに格納することもできます。弦の長さは通常どれくらいですか？
于 2013-03-29T15:26:23.940 に答える