5

ここで概念的に正しいかどうかを確認しようとしています。.

ゼロと 1 の間の値に制限されているなど、someExpensiveFun(x)浮動小数点データの配列内のすべての要素に対して計算コストの高い計算を回避しようとしている場合は、最初に高価な関数の出力を事前計算し、それを table に格納できます。x. .

for (int nn = 0; nn < 1000; ++nn)
{
    float tmp = ((float)nn) / 1000.f;
    lookup[nn] = someExpensiveFun(tmp);
}

次に、パフォーマンスが重要なコードの本体で使用できます。. .

y = lookup[(int)floor(x*1000.f)];

lookupハッシュテーブルの形式とx*1000関連するハッシュ関数を呼び出すことは概念的に正しいですか (用語の乱用ではありません) ?

4

5 に答える 5

4

いいえ、ルックアップ テーブルをハッシュ テーブルと呼ぶのは概念的に正しくありません。この場合、ルックアップ テーブルは単純な配列です。何かをハッシュ テーブルと呼ぶことは、ハッシュ関数が完全でない場合 (つまり、ハッシュ衝突が存在する場合) に特定の動作を意味します。配列にはこの動作がないため、これを「ハッシュ ルックアップ」と呼ぶと、リスナーやリーダーを誤解させる可能性があります。

一般に、ハッシュ テーブルやさまざまなツリーなど、あらゆる種類の連想記憶域を使用して検索操作を実行できます。あなたの場合、配列のインデックスはそのインデックスに格納されている値に関連付けられているため、一定の時間で値を検索できます。

于 2012-09-19T19:19:08.233 に答える
4

個人的には用語の乱用だと思います。人々がハッシュ テーブルに自然に期待するプロパティ、特に等しいハッシュを持つ等しくないキーについて何かを行う機能が欠けています。そして、あなたの「ハッシュ関数」は、 だけでなくfloor(x*1000.f)またはと見なされなければならないと確信しています。(int)floor(x*1000.f)x*1000.f

ハッシュテーブルは通常、範囲内の値だけでなく、キータイプの任意の値をキーとして受け入れることもできますが、おそらく私はそこにこだわりすぎています。NaNキーとして許可されていない通常のハッシュテーブルを「ハッシュテーブルではない」とは呼びません。

これには、ハッシュ テーブル (キーを整数にマップする非単射関数、配列内のインデックスとして使用される整数) と共通するいくつかのプロパティがあります。誰かがこれら 2 つのことを合わせて「ハッシュ テーブル」を特徴付けると判断したい場合は、OK、頑張ってください。それはハッシュ テーブルです :-)

于 2012-09-19T19:32:32.837 に答える
2

あなたはそれを逆に持っています。ハッシュ テーブルは常に配列の低速な代替として使用できますが、配列をハッシュ テーブルの代替として使用することはできません (いくつかの非常に厳密な前提条件が満たされない限り)。

あなたの場合、ルックアップは計算と同じ結果さえ生成せず、近似値のみを生成します。真のハッシュ テーブルは、同じインデックスにハッシュされた異なる入力を区別します。

于 2012-09-19T20:02:42.627 に答える
1

すべてのルックアップ テーブルをハッシュ テーブルで置き換えることはできますが、すべてのハッシュ テーブルをルックアップ テーブルで置き換えることはできません。そうです、ルックアップ テーブルは特別な形式のハッシュ テーブルと見なすことができ、ハッシュ テーブルはルックアップ テーブルの一般的な形式と見なすことができます。

同様に、リストは (1 つの列を持つ) 2D テーブルの特別な形式と見なすことができます。

ただし、ここではソフトウェアについて話しています。与えられた問題には無数の異なる解決策があり、データ構造を構築するための無数の異なる可能性があります。たとえば、静的なサイズまたは動的な成長、必要な一意のエントリまたは衝突処理、固定または構成可能なハッシュ関数などがあります。単純なルックアップ テーブルと完全なハッシュ テーブルの間には多くの方法があります。ここではこれだと言うことができる明確な境界線がありますが、あちらではそれになっています。

ただし (繰り返しますが)、特定のデータ構造が有用であることが判明すると、通常は独自の名前が付けられます。ここで述べたように、そのような名前には、機能に関する期待が関連付けられています。最低限必要な機能については厳密に定義されている場合もあります。他の人がコードを読めるようにしたい場合は、既知の用語に固執することをお勧めします。したがって、技術的にはハッシュ テーブルの特別な形式ですが、ルックアップ テーブルをルックアップ テーブルと呼ぶ必要があります。

于 2012-09-20T07:31:03.993 に答える
1

はい、ウィキペディアのhash tableの定義を受け入れる場合。その定義からの引用：

Ideally, the hash function should map each possible key to a unique slot index,
but this ideal is rarely achievable in practice (unless the hash keys are fixed;
i.e. new entries are never added to the table after it is created).

関数のドメインが明確に定義されており、比較的小さく、配列のインデックスに適しているため、配列を選択しました。関数のドメインには、配列のインデックスへのマッピングがあります。keyインデックスはtoと考えることができhash table、関数の出力は関連付けられた値です。

于 2012-09-19T20:10:03.560 に答える