3

重複の可能性:
一意かつ決定論的な方法で、2 つの整数を 1 つにマッピングする

2 つの整数 (Ruby) のペアの一意の識別子を作成しようとしています。

f(i1,i2) = f(i2, i1) = some_unique_value

つまり、i1+i2、i1*i2、i1^i2 - (i1>i2) と同様に一意ではありませんか? "i1" + "i2" : "i2" + "i1".

次の解決策は問題ないと思います。

(i1>i2) ? "i1" + "_" + "i2" : "i2" + "_" + "i1"

しかし：

  1. 結果をDBに保存してインデックス化する必要があります。したがって、私はそれが整数であり、できるだけ小さいことを好みます。
  2. Zlib.crc32(f(i1,i2)) は一意性を保証できますか?

ありがとう。

更新:

実際、結果が整数でなければならないかどうかはわかりません。多分私はそれを10進数に変換できます: (i1>i2) ? i1.i2 : i2.i1

?

4

5 に答える 5

6

あなたが探しているのはペアリング機能と呼ばれるものです。

ドイツのウィキペディアのページからの次の図は、それがどのように機能するかを明確に示しています。

http://upload.wikimedia.org/wikipedia/commons/thumb/4/41/Pairing-function.svg/350px-Pairing-function.svg.png

Ruby で実装:

def cantor_pairing(n, m)
    (n + m) * (n + m + 1) / 2 + m
end

(0..5).map do |n|
  (0..5).map do |m|
    cantor_pairing(n, m)
  end
end
=> [[ 0,  2,  5,  9, 14, 20],
    [ 1,  4,  8, 13, 19, 26],
    [ 3,  7, 12, 18, 25, 33],
    [ 6, 11, 17, 24, 32, 41],
    [10, 16, 23, 31, 40, 50],
    [15, 22, 30, 39, 49, 60]]

このペアリングの結果を、両方の入力数値を合わせたビット数のデータ型に格納する必要があることに注意してください。(両方の入力数値が 32 ビットの場合、考えられるすべての組み合わせを格納するには 64 ビットのデータ型が必要になることは明らかです。)

于 2012-12-13T21:44:46.917 に答える
2

CRC32 は一意ではないため、キーとして使用するのは適切ではありません。i1整数との最大値を知っていると仮定しますi2。

unique_id = (max_i2+1)*i1 + i2

整数が負になる可能性がある場合、または特定の正の整数を下回らない場合は、最大値と最小値が必要になります。

(max_i2-min_i2+1) * (i1-min_i1) + (i2-min_i2)

これにより、両方の整数を識別できる絶対最小数が得られます。

于 2012-12-13T20:55:31.643 に答える
2

いいえ、Zlib.crc32(f(i1,i2))i1 と i2 のすべての整数値に対して一意ではありません。

i1 と i2 も 32 ビットの数値である場合、CRC32 によって返される 32 ビットの数値に格納できるよりも多くの組み合わせが存在します。

于 2012-12-13T20:44:34.233 に答える
1

入力が 4 バイトを超える任意のバイナリ文字列である場合、4 バイトのハッシュは一意にはなりません。あなたの文字列は非常に制限されたシンボルセットからのものであるため、衝突は少なくなりますが、「いいえ、一意ではありません」.

両方の整数の可能な値の範囲よりも小さい整数を使用するには、次の 2 つの方法があります。

  1. 時折の衝突にもかかわらず機能するシステムを用意する
  2. 衝突をチェックし、何らかの再ハッシュを使用する

1:1 マッピングで問題を解決する明白な方法は、整数の 1 つの最大値を知っている必要があります。1 つに最大値を掛けてもう 1 つを加算するか、2 のべき乗の上限を決定し、それに応じて 1 つの値をシフトしてから、もう 1 つの値を OR します。いずれにせよ、すべてのビットはいずれかの整数用に予約されています。これは、「できるだけ小さい」要件を満たす場合と満たさない場合があります。

####### 文字列はペアごとに一意です。それを文字列として保存できれば、あなたは勝ちます。

于 2012-12-13T20:44:28.073 に答える
0

より良い、よりスペース効率の良いソリューションは次のとおりです。ここでの私の答え

于 2012-12-14T02:36:06.493 に答える