行列へのハッシュ関数

Question

私は2つの行列を持ち、それらを比較する必要がありますが、私は位置によって位置を比較したくありません、私はそれが最良の方法ではないと思います。私はハッシュ関数を考えましたが、誰かが行列のハッシュを計算する方法を知っていますか？

Answer 1

浮動小数点配列全体のハッシュ（バイトシーケンスとして）を計算できます。比較関数が係数の小さな差に対処できるようにするには、各行列から計算された簡単なスカラーとベクトルを比較できます。各行列を複数の行列と比較する必要がある場合は意味があります。心に来る例：

trace of the matrix 
vector of L0, L1, L2 norms of all columns or rows 
diagonal of LU factorization 
tridiagonal reduction (if symmetric) 
diagonal of eigenvalues (if possible) 
diagonal of SVD 

Answer 2

あなたの行列は配列として実装されている場合は、私は彼らが等しいかどうかを判断するためにstring.hからmemcmp()を使用してお勧めしたいです。

浮動小数点値が含まれていて、実際の計算結果の値である場合、数値エラーを処理するためにεを含める必要があるため、値によって値をチェックする方法はありません。

Answer 3

最初に、2つの行列が等しいかどうかをハッシュで確認できません。 （そして、Murphyの法則が常に潜んでいる）衝突が存在する可能性があるからです。

ハッシュを計算するには、要素上の任意の関数を連鎖させます。要素を整数値（切り捨てではなくバイナリ表現）にキャストすることができれば、それらをすべてXORできますいくつかの値が同じだが、-0と+0またはNaNのような別個の表現を持つ場合、これはうまくいかないということです）。

私のアドバイスは、何らかのハッシュ関数（すべての要素の合計が有効であっても）を事前に計算することができるということです（これは重要です。比較を行うたびにハッシュを計算するという意味はありませんハッシュ値を比較して）いくつかの異なる行列を素早く破棄しますが、ハッシュ値が同じであれば、それぞれの位置を比較する必要があります。

Answer 4

あなたはハッシュを言うとき、私はあなたがチェックサム行列にしたいと思いますし、平等を確認するためにチェックサムを比較します。それぞれの行列が連続したデータのまとまりとして格納されていると仮定すると、各チャンクの開始アドレスと長さ（バイト単位）を計算し、両方のチェックサムを生成することができます。同じ）。チェックサムが非常に高い確率で同じである場合、2つの行列も等しい。正しさが重要な場合、チェックサムが一致したら、2つの行列に対して比較ループを実行できます。そうすれば、平等が非常に高い場合を除いて、比較コストを呼び出すことはありません。

wikipedia checksum reference