Funkcja parowania kantora jest naprawdę jedną z lepszych, ponieważ jest prosta, szybka i zajmuje mało miejsca, ale jest coś jeszcze lepiej opublikowanego w Wolfram przez Matthew Szudzika tutaj . Ograniczeniem funkcji parowania Cantora (względnie) jest to, że zakres zakodowanych wyników nie zawsze mieści się w granicach 2N
bitowej liczby całkowitej, jeśli dane wejściowe są dwiema N
liczbami całkowitymi. Oznacza to, że jeśli moje dane wejściowe są 16
liczbami całkowitymi od dwóch bitów 0 to 2^16 -1
, to możliwe są 2^16 * (2^16 -1)
kombinacje danych wejściowych, więc zgodnie z oczywistą zasadą Pigeonhole potrzebujemy wyjścia o wielkości co najmniej 2^16 * (2^16 -1)
równej 2^32 - 2^16
lub innymi słowy mapie32
idealnie powinny być możliwe liczby bitowe. To może nie mieć praktycznego znaczenia w świecie programowania.
Funkcja parowania kantora :
(a + b) * (a + b + 1) / 2 + a; where a, b >= 0
Odwzorowanie dla dwóch maksymalnie 16-bitowych liczb całkowitych (65535, 65535) będzie wynosić 8589803520, który, jak widać, nie mieści się w 32 bitach.
Wejdź w funkcję Szudzika :
a >= b ? a * a + a + b : a + b * b; where a, b >= 0
Mapowanie dla (65535, 65535) będzie teraz 4294967295, co jak widać jest liczbą całkowitą 32-bitową (od 0 do 2 ^ 32 -1). Właśnie tam to rozwiązanie jest idealne, po prostu wykorzystuje każdy punkt w tej przestrzeni, więc nic nie może zapewnić więcej miejsca.
Teraz, biorąc pod uwagę fakt, że zwykle mamy do czynienia z podpisanymi implementacjami liczb o różnych rozmiarach w językach / frameworkach, rozważmy signed 16
liczby całkowite od - -(2^15) to 2^15 -1
(później zobaczymy, jak rozszerzyć nawet wyjście do zakresu ponad podpisany zakres). Od a
i b
muszą być pozytywne, różnią się od 0 to 2^15 - 1
.
Funkcja parowania kantora :
Odwzorowanie dla dwóch maksymalnie 16-bitowych liczb całkowitych ze znakiem (32767, 32767) będzie wynosić 2147418112, czyli niewiele więcej niż maksymalna wartość dla 32-bitowej liczby całkowitej ze znakiem.
Teraz funkcja Szudzika :
(32767, 32767) => 1073741823, znacznie mniejszy ..
Rozważmy liczby całkowite ujemne. To jest poza pierwotnym pytaniem, które znam, ale po prostu opracowaniem, aby pomóc przyszłym użytkownikom.
Funkcja parowania kantora :
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, który jest Int64. 64-bitowy sygnał wyjściowy dla 16-bitowych sygnałów wejściowych może być tak nieprzebaczalny !!
Funkcja Szudzika :
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, który jest 32-bitowy dla zakresu bez znaku lub 64-bitowy dla zakresu ze znakiem, ale wciąż lepszy.
Wszystko to, podczas gdy wyniki zawsze były pozytywne. W podpisanym świecie zaoszczędzenie miejsca zajmowałoby jeszcze więcej, gdybyśmy mogli przenieść połowę mocy wyjściowej na oś ujemną . Możesz to zrobić w ten sposób dla Szudzika:
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
Co robię: po nałożeniu ciężaru 2
na dane wejściowe i przejściu przez funkcję dzielę wyjście przez dwa i przenoszę niektóre z nich na oś ujemną, mnożąc przez -1
.
Zobacz wyniki, dla dowolnego wejścia w zakresie liczby 16
bitów ze znakiem , wyjście leży w granicach 32
fajnej liczby całkowitej ze znakiem . Nie jestem pewien, jak postąpić w ten sam sposób dla funkcji parowania Cantor, ale nie próbowałem tyle, ile nie jest tak wydajna. Co więcej, więcej obliczeń związanych z funkcją parowania Cantora oznacza również jego spowolnienie .
Oto implementacja 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;
}
Ponieważ obliczenia pośrednie mogą przekraczać limity liczby 2N
całkowitej ze znakiem, użyłem 4N
typu liczby całkowitej (ostatni podział przez 2
powoduje powrót wyniku 2N
).
Link, który podałem w alternatywnym rozwiązaniu, ładnie przedstawia wykres funkcji wykorzystującej każdy pojedynczy punkt w przestrzeni. To niesamowite, że możesz jednoznacznie zakodować parę współrzędnych w pojedynczą liczbę w sposób odwracalny! Magiczny świat liczb !!