1

これが以前に尋ねられた場合は、事前にお詫び申し上げます。ある場合、このデータ構造が何と呼ばれるかわかりません。

N 個 (約 300 以下) のウィジェットのコレクションがあります。各ウィジェットには M 個 (約 10 個) の異なる名前があります。このコレクションは 1 回入力され、その後何度も検索されます。これを C++ で実装します。

この例として、200 人のユーザーのコレクションがあり、その名前を 7 つの異なる言語で保存している場合があります。

検索関数は基本的に次のようになります: lookup("name", A, B) は、言語 A から言語 B への名前 "name" の翻訳を返します (name がコレクションにある場合のみ)。

この種のことを効率的に行うための文献に既知のデータ構造はありますか? 最も明白な解決策は、ルックアップ用の一連のハッシュ テーブルを作成することですが、考えられるすべてのペアに対して MxM ハッシュ テーブルを用意すると、すぐに扱いにくくなり、メモリの効率が低下します。また、並べ替えられた配列 (バイナリ検索) やツリーも検討したいと思います。コレクションは巨大ではないため、log(N) ルックアップは問題ありません。

みんなありがとう！

4

2 に答える 2

1

D[u,v]ウィジェット u の言語 v の単語で ある N 行 M 列の配列 D を作成します。

また、M ハッシュ テーブル H₀...Hₘ (m は M-1) を作成しHᵥ(w).data、w が言語 v のウィジェット u の単語である場合に u となるようにします。

を実行するにはlookup(w, r, s)、
(1) セット u = Hᵣ(w).data
(2) D[u,r]w に等しい場合は を返しD[u,s]、そうでない場合は not-found を返します。

于 2013-07-23T06:03:25.227 に答える
1

目的のルックアップ関数の説明に基づいて、キーがtuple<string, Language, Language>あり、値が変換の結果である単一のハッシュ テーブルを使用できるように思えます。キー内の 2 つの言語は、文字列のソース言語と目的の翻訳の言語をそれぞれ識別します。

于 2013-07-22T23:24:52.670 に答える