3

次のようなハッシュ値のペアがあります

  1. 128ecf542a35ac5270a87dc740918404;d603ac0c04b9d08974482ae7fd4cf55
  2. a1288b1c7e2257a90bad9bdfb7690fbb;f23828e312d90cb7fdadd6479236119c
  3. ................................................................................. ...............

各ペアを他のペアと比較できるようにしたいと思います。つまり、次のことを意味します。

128ecf542a35ac5270a87dc740918404;d603ac0c04b9d08974482ae7fd4cf55d

そのままです。

の場合

d603ac0c04b9d08974482ae7fd4cf55d;128ecf542a35ac5270a87dc74091840

4、なるはず

128ecf542a35ac5270a87dc740918404;d603ac0c04b9d08974482ae7fd4cf55d

私の主な目標は、1 つのペアの 2 つのハッシュ値を比較し、何らかの規則に従って順序付けられた値を持つペアを返す特定の関数を持つことです。ルール自体は問題ではありません。唯一の要件は、入力が (unique1,unique2) または (unique2,unique1) のいずれかである場合、非常に高速で、常に同じ結果が得られることです。

どうも！

明白ですが非効率的な方法の 1 つは、各ハッシュ値に含まれる数値のみを合計してそれらを比較し、小さい方の合計をペアの最初の要素として、大きい方を 2 番目の位置に配置することです。

4

3 に答える 3

5

2 つの文字列を通常の文字列比較 ( compareTo) で比較し、小さい方を最初に置きます。これはあなたが望むものを保証します。実際には、ハッシュ値は最初の数文字ですでに異なり、比較では残りの文字列を調べる必要がないため、これは非常に安価であると予想しています。さらに、(あなたの例のように) 非常に少ないバイト数へのアクセスと比較は非常に安価であるため、プログラムが行う他の操作と比較して、これを非常に頻繁に行う場合にのみパフォーマンスへの影響を確認できます。

値を文字列としてではなく、バイト配列などとして持っている場合は、単純な辞書式比較を独自に実装してください。

于 2012-06-14T12:20:36.633 に答える
1

編集：私はあなたの質問と主な目標をもう一度読みました。私の答えは、2つのペアを比較することです。

ペアで2つのハッシュ値を並べ替える場合は、実際には2つのハッシュを線形に比較し、文字の最初の不一致時に低い方の値を最初に配置します。最初の数バイトで値がすでに異なる可能性があります。

Javaではできないと思いますが、C / ASMで関数を作成し、JavaからJNIを介して使用することができます。

見てみましょう：これらは32バイトのハッシュ値のペアです。あなたはペアが';'で区切られている場所を知っています バイト32。

とのように結合されたハッシュ値とhahsA := (hA1;hA2)しますhashB := (hB1;hB2)

あなたは最初のペアを取ります：

1）2つのSSEレジスタに0〜15バイトと33〜49バイトを取得し、XORします。

hashA[0-15] := ( hashA1[0-15] XOR hashA2[0-15] ).

2）SSEレジスタに16〜31バイトと50〜65バイトを取得し、XORも実行します

hashA[16-31] := ( hashA1[16-31] XOR hashA2[16-31] ).

これで、カップルの最初と2番目の16バイトのXORで満たされた2つのSSEレジスタができました。

XMM0: hashA[0-15]
XMM1: hashA[16-31]

あなたは2番目のペアを取り、同じことをします。8つのSSEレジスタがあるため、2）以降にレジスタから値を取得する必要がない場合があります。

今あなたは持っています：

XMM0: hA[0-15]
XMM1: hA[16-31]
XMM2: hB[0-15]
XMM3: hB[16-31]


if( XMM0 == XMM2 AND XMM1 == XMM3 ) then hA and hB are equal.

もちろん、ハッシュコードが32バイトよりも大きい場合は、さらに手順を実行する必要がありますが、ハッシュコードがすべて同じ長さであると仮定すると、このアルゴリズムは次のようになります。

1）2つの16バイトをロードし、xor = 3命令2）3命令

1）および2）2番目のカップルの場合：6つの命令、最後に比較用の2つの命令、およびAND用の1つの命令

これは、関数呼び出しを測定するのではなく、比較するカップルごとに15の命令のようなものになります。ハッシュ値が大きいと命令数も増えるので、O（1）とは言えません。

効率が本当に重要な場合、これは進むべき道です。しかし、とにかく、すべての文字を比較する必要があるため、O（n）未満で実行できるとは思いません。

于 2012-06-14T13:21:18.913 に答える
0

2 つの文字列が等しくない場合を最適化するのは簡単で、 の実装ではString.equals(Object)既にこれが行われています。

ただし、2 つの文字列が等しいが等しくない場合==は、本質的にO(N)です。

現在、特定の状況下でそれを改善することが可能です:

  • オブジェクトに追加のプライベート フィールドを追加することができます。
  • equalsオブジェクトの状態は、オペレーターに対して安定していなければなりません。
  • オブジェクト インスタンスの同じセットを繰り返し比較する必要があります。

これらの前提条件の下で、傾向のあるアルゴリズムがありO(1)ます。ただし、1 番目と (おそらく) 3 番目の条件が成立しないため、文字列値として表されるハッシュには適用できません。

于 2012-06-14T13:11:06.420 に答える