名前、いくつかのサブ値、および連想数値を持つ一連のデータがあります。例えば：
James Value1 Value2 "1.232323/1.232334"
Jim Value1 Value2 "1.245454/1.232999"
Dave Value1 Value2 "1.267623/1.277777"
このようなエントリは、ファイルまたはデータベースに約 100,000 件保存されます。関連する数値とともに、検索に一致する結果を返すことができる最も速い方法は何ですか。
たとえば、"J" のクエリは、James と Jim の両方の結果を返し、最後の列に数値が表示されます。
二分木検索、辞書検索、索引検索などについて言及していると聞いたことがあります。どのルートを熟読するのが良いかわかりません。
これは特性が不十分な問題です。多くの最適化問題と同様に、リソースにはトレードオフがあります。可能な限り最速の応答が本当に必要な場合は、可能性のあるすべての検索を準備済みの結果のテーブルにコンパイルして、検索キーを指定すると、テーブルで検索キーを検索して結果を返すことができる方法が考えられます。
文字セットが A ～ Z および a ～ z に制限されていると仮定すると、0 ～ 4 文字の各検索キーのエントリを含むテーブルは、今日の標準では適度な量のメモリを使用します。各テーブル エントリには、次の 2 つの値が必要です。数値のリストの開始位置と終了位置。(次のようにリストをコンパイルします。名前フィールドでレコードをソートします。レコードから数値のみを抽出し、順序を維持してリストに入れます。検索キーは、そのリストから連続するレコードのサブリストを返す必要があります。これは、検索が名前フィールドのプレフィックス文字列に対するものであるためです。したがって、名前フィールドでソートすると、検索キーに一致するすべてのレコードが隣接します。)
したがって、0 から 4 文字の任意のキーを検索するテーブルを作成するには、ペアの各メンバーにレコード番号 (32 ビット以下) が含まれるペアのテーブルに必要なエントリは53 4未満です。したがって、8•534 = 60.2 MiB で十分です。(53 は、キーの終わりを示す 52 文字と 1 つのセンチネル文字があるためです。別のエンコーディングを使用すると、これをいくらか減らすことができます。)
4 文字を超えるキーをサポートするには、これを拡張する必要があります。典型的なデータでは、4 文字で検索が大幅に絞り込まれるため、最初の 4 文字で示されるレコードのセットを取り出して、それを切り詰めて最終結果を得ることができます。データに 4 文字では検索があまり減らない病理学的なケースがある場合は、この手法を装飾することができます。
では、他のリソース (エンジニアリング時間を含む) が消費されているかどうかに関係なく、速度をできるだけ速くしたいというのが本当にあなたのやりたいことでしょうか? そうでない場合、実際の目標は何ですか?