[algorithm] 독특하고 결정적인 방식으로 두 정수를 하나로 매핑

캔터 페어링 기능은 정말 빨리 간단한을 고려 거기 더 나은 사람 중 하나, 공간 효율적이지만 더 나은 볼프람에 게시 무언가가 여기에, 매튜 Szudzik으로는 . Cantor pairing 기능의 한계는 (상대적으로) 2N입력이 2 N비트 정수인 경우 인코딩 된 결과의 범위가 항상 비트 정수 의 한계 내에 머 무르지 않는다는 것 입니다. 내 입력이 두 경우 즉, 16에 이르기까지 비트 정수는 0 to 2^16 -1다음이 있습니다 2^16 * (2^16 -1)가능한 입력의 조합이 이렇게 명백한에 의해, 미루다 원리 , 우리는 적어도 크기의 출력이 필요 2^16 * (2^16 -1)동일, 2^32 - 2^16또는 다른 말로,의지도를32비트 번호는 이상적으로 실현 가능해야합니다. 이것은 프로그래밍 세계에서 실질적으로 중요하지 않을 수 있습니다.

캔터 페어링 기능 :

(a + b) * (a + b + 1) / 2 + a; where a, b >= 0

최대 16 비트 정수 두 개 (65535, 65535)에 대한 매핑은 8589803520이며 32 비트에는 맞지 않습니다.

Szudzik의 기능을 입력하십시오 :

a >= b ? a * a + a + b : a + b * b;  where a, b >= 0

(65535, 65535)에 대한 매핑은 이제 4294967295이며 32 비트 (0 ~ 2 ^ 32 -1) 정수입니다. 이것이이 솔루션이 이상적인 곳이며, 해당 공간의 모든 단일 지점을 활용하기 때문에 더 효율적인 공간을 확보 할 수있는 것은 없습니다.

이제 우리가 일반적으로 언어 / 프레임 워크에서 다양한 크기의 부호있는 구현을 처리한다는 사실을 고려하여 signed 16비트 정수 범위에서 범위를 고려해 봅시다 -(2^15) to 2^15 -1(나중에 부호 범위까지 확장하기 위해 출력을 확장하는 방법을 살펴 보겠습니다). 이후 a및 것은 b그들이 범위 긍정적해야 0 to 2^15 - 1.

캔터 페어링 기능 :

최대 16 비트 부호있는 정수 2 개 (32767, 32767)에 대한 매핑은 부호있는 32 비트 정수의 최대 값보다 짧은 2147418112입니다.

이제 Szudzik의 기능 :

(32767, 32767) => 1073741823, 훨씬 작습니다.

음의 정수를 고려해 봅시다. 그것은 내가 아는 원래의 질문을 넘어서지 만 미래 방문자를 돕기 위해 정교하게 만듭니다.

캔터 페어링 기능 :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
(A + B) * (A + B + 1) / 2 + A;

(-32768, -32768) => 8589803520이며 Int64입니다. 16 비트 입력을위한 64 비트 출력은 용납 할 수 없습니다 !!

Szudzik의 기능 :

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

(-32768, -32768) => 4294967295 : 부호없는 범위의 경우 32 비트 또는 부호있는 범위의 경우 64 비트이지만 여전히 더 좋습니다.

출력이 항상 양의 동안이 모든 것. 부호있는 세계에서는 출력의 절반을 음의 축으로 전송할 수 있으면 공간이 훨씬 절약됩니다 . Szudzik의 경우 다음과 같이 할 수 있습니다.

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
C = (A >= B ? A * A + A + B : A + B * B) / 2;
a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;

(-32768, 32767) => -2147483648

(32767, -32768) => -2147450880

(0, 0) => 0

(32767, 32767) => 2147418112

(-32768, -32768) => 2147483647

내가하는 일 : 2입력에 가중치를 적용 하고 함수를 거친 후 출력을 2로 나누고을 곱하여 출력을 음의 축으로 가져갑니다 -1.

부호있는 16비트 수 범위의 입력에 대한 결과 는 출력이 부호있는 32비트 정수 의 한계 내에 있습니다 . Cantor 페어링 기능에 대해 동일한 방법을 사용하는 방법을 잘 모르겠지만 효율적이지 않은 방법으로 시도하지 않았습니다. 또한 Cantor 페어링 기능과 관련된 계산이 많을수록 속도가 느려집니다 .

다음은 C # 구현입니다.

public static long PerfectlyHashThem(int a, int b)
{
    var A = (ulong)(a >= 0 ? 2 * (long)a : -2 * (long)a - 1);
    var B = (ulong)(b >= 0 ? 2 * (long)b : -2 * (long)b - 1);
    var C = (long)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

public static int PerfectlyHashThem(short a, short b)
{
    var A = (uint)(a >= 0 ? 2 * a : -2 * a - 1);
    var B = (uint)(b >= 0 ? 2 * b : -2 * b - 1);
    var C = (int)((A >= B ? A * A + A + B : A + B * B) / 2);
    return a < 0 && b < 0 || a >= 0 && b >= 0 ? C : -C - 1;
}

중간 계산이 2N부호있는 정수의 한계를 초과 할 수 있기 때문에 4N정수 유형 을 사용했습니다 (마지막 나누기 2는 결과를 로 가져옵니다 2N).

대체 솔루션에서 제공 한 링크는 공간의 모든 단일 지점을 활용하는 함수의 그래프를 멋지게 묘사합니다. 한 쌍의 좌표를 가역적으로 단일 숫자로 고유하게 인코딩 할 수 있다는 것이 놀랍습니다! 숫자의 마법 세계 !!

답변

int combine(short A, short B)
{
    return A<<16 | B;
}

short getA(int C)
{
    return C>>16;
}

short getB(int C)
{
    return C & 0xFFFF;
}

f( x, y ) -> 2^x * 3^y

f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)

   1 2 3 4 5 (a, b)! = (b, a) 인 경우이 매핑을 사용하십시오.
1,012 6 10
2 4 7 11 16
3 5 8 12 17 23
4 9 13 18 24 31
5 14 19 25 32 40

   1 2 3 4 5 (a, b) == (b, a) (거울) 인 경우이 매핑을 사용하십시오.
10012 4 6
2 1 3 5 7 10
3 2 5 8 11 14
44 8 11 15 19
5 6 10 14 19 24


    0 1 -1 2 -2 음수 / 양수가 필요한 경우 사용하십시오
 0012 6
 11 3 5 7 10
-12 5 8 11 14
 2 4 8 11 15 19
-2 6 10 14 19 24