3

C++ から JavaScript に移植したハッシュ アルゴリズムの分布を確認するために、簡単なキャンバス ビジュアライゼーションを作成しました。

ハッシュを何に変更しても、ハッシュ関数から他のほとんどの数値よりも正確に 2 倍の頻度で 0 が選択されるという点で、0 は非常に偏っているという奇妙な動作が見られます。

デモはhttp://jsfiddle.net/x5L73/2/で見ることができます。

元の C++ アルゴリズム: http://www.azillionmonkeys.com/qed/hash.html

そして、私が参照しているコードの一部は、jsFiddle の下部にあります。

// hash is 0 twice as often as anything else
var hash = app.Hash( word ) % ( 3499 )
  ,   b1 = 0|hash / 59
  ,   b2 =   hash % 59;

私にとって奇妙なのは、それを変更するために選択したものに関係なく、他の値の2hash倍の頻度でゼロになることです。この例では 0回ですが、それ以外の数値はヒット回数です。これは、以下を介したブルート フォース テストによって決定されました。1/34991/6998

if( hash!==1234 ){ nonZero++; }else{ zero++ } // 1234 is a random number to check       
if( Math.random() < .00001 ){ console.log( zero, nonZero, 0|nonZero/zero ); }

ここで何が欠けていますか???

4

1 に答える 1

4

これは非常に楽しい事実であり、整数を処理するときに役立つ可能性がありますが、ハッシュと同様に、エラーはJavaScriptにも負のゼロがあるという事実によるものではありません...

OPによって報告された元の原因は次のとおりです。

これは、ビジュアライゼーションで誤ってすべての負の数を破棄していたためです。

うん、負の数はそれほど些細なことではありません、私たちの心は時々それらを無視する傾向があります-特に彼らが長い間整数を含む特定の難しい問題に焦点を当てているとき、ちょうど良いハッシュ方法を見つけようとして、そして一見一見に切り替えるようにはるかに簡単なタスク：結果を表示する...

したがって、本当の答えは次のとおりです。負のゼロに加えて、JavaScriptにはさらに多くの負の数もあります...視覚化の簡単なタスクであっても、それらをカウントすることを忘れないでください。

TL; DR

これは、同様のシナリオを引き起こす可能性があるため、将来同様の問題を抱えている人に役立つ可能性があるため、ここに残しておきます。

この質問を見てください：JavaScriptでは+0と-0（JavaScriptでは負のゼロと正のゼロ）

引用：

JavaScriptは、IEEE745標準を使用して数値を表します。ウィキペディアから：

符号付きゼロは、関連する符号を持つゼロです。通常の算術では、-0 = +0 = 0です。ただし、計算では、一部の数値表現では2つのゼロが存在し、多くの場合、 -0（負のゼロ）と+0（正のゼロ）で表されます。これは、整数の一部の符号付き数値表現、およびほとんどの浮動小数点数値表現で発生します。数値0は通常+0としてエンコードされますが、+0または-0のいずれかで表すことができます。

浮動小数点演算のIEEE754標準（現在、浮動小数点数をサポートするほとんどのコンピューターおよびプログラミング言語で使用されています）には、+0と-0の両方が必要です。ゼロは、1 / −0 = −∞および1 / + 0 = +∞、ゼロによる除算は±0/±0および±∞/±∞に対してのみ未定義であるような拡大実数線の変形と見なすことができます。 。

于 2013-03-06T09:06:42.230 に答える