1

セットアップ: 文字列と文字列のペアに関連付けられた特徴ベクトルを保存する必要があります。文字列と文字列のペアは、入出力関係をエンコードします。比較的少数の入力X(例: 5) があり、各入力xに対して比較的少数の出力Y|x(例: 10) があります。

問題は、どのデータ構造が最速かということです。

追加の関連情報:

  1. 通常、出力は入力ごとに異なり、それぞれXが同じ数の出力を持つとは限りません。
  2. 検索は「何度も」行われます (おそらく 1000 回)。
  3. 入力は同じ頻度でサンプリングされますが、各入力に対して、通常は 1 つまたは 2 つの出力が頻繁にアクセスされ、残りはほとんどアクセスされないか、まったくアクセスされません。

現在、以下の3つの可能性を考えています。

  1. list-of-lists : インデックス ( input を表すX[i]) で外側のリストにアクセスし、インデックス ( output を表す) で内側のリストにアクセスしますY[i][j]。
  2. hash-of-hashes : 上記と同じ。
  3. フラット ハッシュ: key = (input,output).
4

1 に答える 1

0

文字列がある場合、とにかくハッシュを利用せずにリストのリストを効率的に使用するためにインデックスを検索する方法は不明です。インデックスへの参照を保持するものを渡すことができる場合（たとえば、出力のセットが固定されていて、それらの列挙を定義できる場合）、文字列の代わりにリストのリストが高速になります（ 「必ずしもリンクリストではない」という意味で、O（1）要素にアクセスできます）。それ以外の場合は、直接ハッシュして労力を節約することもできます。

そうでない場合は、ハッシュのハッシュとフラットハッシュが残ります。アクセスパターンはどのようなものですか？あなたはいつもX、Yを要求するつもりですか、それともXのすべての出力にアクセスする必要がありますか？Hash（X + Y）は、hash（X）+ hash（Y）とほぼ同等です（どちらも通常、すべての文字を調べてハッシュを生成します。したがって、個々のハッシュは、わずかに（ほぼ確実に無視できる程度に）より柔軟になります。 ）オーバーヘッド。3から、とにかくハッシュのハッシュが必要になる可能性があるようです。

于 2013-03-10T03:08:46.113 に答える