독특하고 결정적인 방식으로 두 정수를 하나로 매핑
두 개의 양의 정수 A와 B를 상상해보십시오.이 두 개를 단일 정수 C로 결합하고 싶습니다.
C에 결합하는 다른 정수 D와 E는있을 수 없습니다. 따라서 더하기 연산자와 결합하면 작동하지 않습니다. 예 : 30 + 10 = 40 = 40 + 0 = 39 + 1 연결도 작동하지 않습니다. 예 : "31"+ "2"= 312 = "3"+ "12"
이 결합 조작은 결정되어야한다 (항상 같은 입력과 같은 결과를 수득) 과 항상 양 또는 음의 정수의 어느 측에 정수를 산출한다.
당신은 bijective NxN -> N매핑을 찾고 있습니다. 이것들은 예를 들어 더브 테일링에 사용됩니다 . 소위 페어링 기능 에 대한 소개 는 이 PDF 를 참조하십시오 . Wikipedia는 특정 페어링 기능, 즉 Cantor 페어링 기능을 소개합니다 .
세 가지 언급 :
- 다른 사람들이 분명히 알 수 있듯이 페어링 기능을 구현하려는 경우 곧 큰 정수 (bignums)가 필요할 수 있습니다.
- 쌍 (a, b)와 (b, a)를 구별하지 않으려면 페어링 기능을 적용하기 전에 a와 b를 정렬하십시오.
- 사실 나는 거짓말을했다. 당신은 bijective
ZxZ -> N매핑을 찾고 있습니다. Cantor의 기능은 음수가 아닌 숫자에서만 작동합니다. 그러나 다음f : Z -> N과 같이 bijection을 쉽게 정의 할 수 있으므로 문제가되지 않습니다 .- n> = 0 인 경우 f (n) = n * 2
- n <0 인 경우 f (n) = -n * 2-1
Cantor 페어링 기능 은 간단하고 빠르며 공간 효율적이라는 점을 고려할 때 실제로 더 나은 기능 중 하나이지만 Matthew Szudzik이 Wolfram 에 더 나은 내용을 게시했습니다 . 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).
대체 솔루션에서 제공 한 링크는 공간의 모든 단일 지점을 사용하는 함수의 그래프를 멋지게 묘사합니다. 한 쌍의 좌표를 가역적으로 단일 숫자로 고유하게 인코딩 할 수 있다는 것이 놀랍습니다! 숫자의 마법 세계!
A와 B를 2 바이트로 표현할 수 있으면 4 바이트로 결합 할 수 있습니다. A를 최상위 반에, B를 최하 반에 놓습니다.
C 언어에서 이것은 (sizeof (short) = 2 및 sizeof (int) = 4라고 가정)를 제공합니다.
int combine(short A, short B)
{
return A<<16 | B;
}
short getA(int C)
{
return C>>16;
}
short getB(int C)
{
return C & 0xFFFF;
}
이것이 가능합니까?
두 정수를 결합하고 있습니다. 둘 다 -2,147,483,648에서 2,147,483,647의 범위를 가지지 만 긍정적 인 것만 취할 것입니다. 2147483647 ^ 2 = 4,61169E + 18 조합이됩니다. 각 조합은 고유해야하며 정수가되므로이 양의 숫자를 포함 할 수있는 일종의 마법 정수가 필요합니다.
아니면 내 논리에 결함이 있습니까?
양의 정수에 대한 표준 수학적 방법은 소인수 분해의 고유성을 사용하는 것입니다.
f( x, y ) -> 2^x * 3^y
단점은 이미지가 상당히 넓은 정수 범위에 걸쳐 있기 때문에 컴퓨터 알고리즘에서 매핑을 표현할 때 결과에 적합한 유형을 선택하는 데 문제가있을 수 있다는 것입니다.
당신은 부정적인를 처리하려면이 옵션을 수정할 수 x와 y5 개, 7 용어의 힘으로 플래그를 인코딩하여.
예 :
f( x, y ) -> 2^|x| * 3^|y| * 5^(x<0) * 7^(y<0)
숫자를 a첫 번째, b두 번째로 둡니다. 하자 p수 a+1번째 소수를 q수 b+1번째 소수
그러면 결과는 pqif a<b,또는 2pqif a>b입니다. 경우 a=b, 그것은하자 p^2.
매핑을 구성하는 것은 그리 어렵지 않습니다.
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
임의의 a, b에 대한 값을 얻는 방법을 알아내는 것은 조금 더 어렵습니다.
f(a, b) = s(a+b) + a, 어디 s(n) = n*(n+1)/2
- 이것은 함수입니다. 결정적입니다.
- f는 다른 (a, b) 쌍에 대해 다른 값을 매핑합니다. 다음 사실을 사용하여이를 증명할 수 있습니다
s(a+b+1)-s(a+b) = a+b+1 < a.. - 배열이 클 필요는 없으므로 배열 인덱싱에 사용하려는 경우 아주 작은 값을 반환합니다.
- 캐시에 친숙합니다. 두 개의 (a, b) 쌍이 서로 가까이 있으면 f는 숫자를 서로 가까운 (다른 방법과 비교하여) 숫자로 매핑합니다.
나는 당신이 의미하는 바를 이해하지 못했습니다 :
정수의 양 또는 음의 정수를 항상 산출해야합니다.
이 포럼에서 (보다 큼) 문자를 쓰려면 어떻게해야합니까?
Stephan202의 답변이 유일한 일반적인 답변이지만 범위가 제한된 정수의 경우 더 잘 수행 할 수 있습니다. 예를 들어, 범위가 0..10,000이면 다음을 수행 할 수 있습니다.
#define RANGE_MIN 0
#define RANGE_MAX 10000
unsigned int merge(unsigned int x, unsigned int y)
{
return (x * (RANGE_MAX - RANGE_MIN + 1)) + y;
}
void split(unsigned int v, unsigned int &x, unsigned int &y)
{
x = RANGE_MIN + (v / (RANGE_MAX - RANGE_MIN + 1));
y = RANGE_MIN + (v % (RANGE_MAX - RANGE_MIN + 1));
}
결과는 정수 유형 카디널리티의 제곱근까지 범위의 단일 정수에 맞을 수 있습니다. 이것은 Stephan202의 일반적인 방법보다 약간 더 효율적입니다. 디코딩하는 것도 상당히 간단합니다. 초보자를 위해 제곱근이 필요하지 않습니다. :)
인수로서 양의 정수 및 인수 순서가 중요하지 않은 경우 :
정렬되지 않은 페어링 기능 은 다음과 같습니다 .
<x, y> = x * y + trunc((|x - y| - 1)^2 / 4) = <y, x>x ≠ y의 경우 순서가없는 고유 한 페어링 기능은 다음과 같습니다.
<x, y> = if x < y: x * (y - 1) + trunc((y - x - 2)^2 / 4) if x > y: (x - 1) * y + trunc((x - y - 2)^2 / 4) = <y, x>
이것을 확인하십시오 : http://en.wikipedia.org/wiki/Pigeonhole_principle . A, B 및 C가 동일한 유형이면 수행 할 수 없습니다. A와 B가 16 비트 정수이고 C가 32 비트이면 쉬프팅을 사용할 수 있습니다.
해싱 알고리즘의 특성은 각 입력마다 고유 한 해시를 제공 할 수 없다는 것입니다.
다음은 @nawfal이 제공 한 방법을 기반으로 @DoctorJ 코드를 무제한 정수로 확장 한 것입니다. 인코딩 및 디코딩이 가능합니다. 일반 배열 및 numpy 배열에서 작동합니다.
#!/usr/bin/env python
from numbers import Integral
def tuple_to_int(tup):
""":Return: the unique non-negative integer encoding of a tuple of non-negative integers."""
if len(tup) == 0: # normally do if not tup, but doesn't work with np
raise ValueError('Cannot encode empty tuple')
if len(tup) == 1:
x = tup[0]
if not isinstance(x, Integral):
raise ValueError('Can only encode integers')
return x
elif len(tup) == 2:
# print("len=2")
x, y = tuple_to_int(tup[0:1]), tuple_to_int(tup[1:2]) # Just to validate x and y
X = 2 * x if x >= 0 else -2 * x - 1 # map x to positive integers
Y = 2 * y if y >= 0 else -2 * y - 1 # map y to positive integers
Z = (X * X + X + Y) if X >= Y else (X + Y * Y) # encode
# Map evens onto positives
if (x >= 0 and y >= 0):
return Z // 2
elif (x < 0 and y >= 0 and X >= Y):
return Z // 2
elif (x < 0 and y < 0 and X < Y):
return Z // 2
# Map odds onto negative
else:
return (-Z - 1) // 2
else:
return tuple_to_int((tuple_to_int(tup[:2]),) + tuple(tup[2:])) # ***speed up tuple(tup[2:])?***
def int_to_tuple(num, size=2):
""":Return: the unique tuple of length `size` that encodes to `num`."""
if not isinstance(num, Integral):
raise ValueError('Can only encode integers (got {})'.format(num))
if not isinstance(size, Integral) or size < 1:
raise ValueError('Tuple is the wrong size ({})'.format(size))
if size == 1:
return (num,)
elif size == 2:
# Mapping onto positive integers
Z = -2 * num - 1 if num < 0 else 2 * num
# Reversing Pairing
s = isqrt(Z)
if Z - s * s < s:
X, Y = Z - s * s, s
else:
X, Y = s, Z - s * s - s
# Undoing mappint to positive integers
x = (X + 1) // -2 if X % 2 else X // 2 # True if X not divisible by 2
y = (Y + 1) // -2 if Y % 2 else Y // 2 # True if Y not divisible by 2
return x, y
else:
x, y = int_to_tuple(num, 2)
return int_to_tuple(x, size - 1) + (y,)
def isqrt(n):
"""":Return: the largest integer x for which x * x does not exceed n."""
# Newton's method, via http://stackoverflow.com/a/15391420
x = n
y = (x + 1) // 2
while y < x:
x = y
y = (x + n // x) // 2
return x
당신이 제안하는 것은 불가능합니다. 항상 충돌이 발생합니다.
두 객체를 다른 단일 세트에 매핑하려면 매핑 된 세트의 최소 크기가 예상되는 조합 수 여야합니다.
32 비트 정수를 가정하면 2147483647 양의 정수가 있습니다. 순서가 중요하지 않고 반복되는 두 가지를 선택하면 2305843008139952128 조합이 생성됩니다. 이것은 32 비트 정수 세트에는 적합하지 않습니다.
그러나이 매핑을 61 비트로 맞출 수 있습니다. 64 비트 정수를 사용하는 것이 가장 쉽습니다. 높은 단어를 작은 정수로, 낮은 단어를 큰 정수로 설정하십시오.
더 간단한 것은 어떻습니까? 두 개의 숫자가 주어지면 A와 B는 str을 연결합니다 : 'A'+ ';' + 'B'. 그런 다음 출력을 hash (str)로 설정하십시오. 나는 이것이 수학적인 대답이 아니라 간단한 파이썬 (내장 해시 함수가 있음) 스크립트가 일을해야한다는 것을 알고 있습니다.
두 개의 숫자 B와 C를 가지고 단일 숫자 A로 인코딩합시다.
A = B + C * N
어디
B = A % N = B
C = A / N = C
양의 정수 A와 B가 주어지면 D = A에있는 자릿수, E = B에있는 자릿수 결과는 D, 0, E, 0, A 및 B의 연결 일 수 있습니다.
예 : A = 300, B = 12. D = 3, E = 2 결과 = 302030012. 이것은 0으로 시작하는 유일한 숫자가 0이라는 사실을 이용합니다.
Pro : 인코딩하기 쉽고, 해독하기 쉬우 며, 사람이 읽을 수 있으며, 유효 숫자를 먼저 비교할 수 있으며 계산없이 비교할 수 있으며 간단한 오류 검사가 가능합니다.
단점 : 결과의 크기가 문제입니다. 그러나 그래도 괜찮습니다. 어쨌든 컴퓨터에 무제한 정수를 저장하는 이유는 무엇입니까?
32 비트 정수를 가지고 있다고 가정 해 봅시다. A를 처음 16 비트 반으로, B를 다른 반으로 옮기는 것이 어떻습니까?
def vec_pack(vec):
return vec[0] + vec[1] * 65536;
def vec_unpack(number):
return [number % 65536, int(number / 65536)];
가능한 공간 효율적이고 계산하기에 저렴한이 외에, 정말 멋진 부작용은 포장 된 숫자에 대해 벡터 수학을 수행 할 수 있다는 것입니다.
a = vec_pack([2,4])
b = vec_pack([1,2])
print(vec_unpack(a+b)) # [3, 6] Vector addition
print(vec_unpack(a-b)) # [1, 2] Vector subtraction
print(vec_unpack(a*2)) # [4, 8] Vector multiplication
이 두 지점을 통과합니다
'IT' 카테고리의 다른 글
| CamelCase의 약어 (0) | 2020.04.25 |
|---|---|
| 새 사용자를 만들 때 ActiveModel :: ForbiddenAttributesError (0) | 2020.04.25 |
| Android에서 ScrollView를 사용하는 방법은 무엇입니까? (0) | 2020.04.25 |
| AJAX 응답이 쿠키를 설정할 수 있습니까? (0) | 2020.04.02 |
| C #에서 지역화를 사용하는 방법 (0) | 2020.04.02 |