Функция сопряжения Кантора действительно одна из лучших, учитывая ее простую, быструю и компактную работу, но кое-что еще лучше опубликовано на Wolfram Мэтью Шудзиком, здесь, Ограничение функции сопряжения Кантора (относительно) состоит в том, что диапазон закодированных результатов не всегда находится в пределах 2N битового целого, если входные данные представляют собой два N битовых целых числа. То есть, если мои входные данные представляют собой два 16 битовых целых числа в диапазоне от 0 to 2^16 -1, тогда возможны 2^16 * (2^16 -1) комбинации входных данных, поэтому в силу очевидного принципа Pigeonhole нам нужен выходной размер в наименьший 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 бита.
Введите функция Шудзика :
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-разрядных целых чисел со знаком (32767, 32767) будет 2147418112, что немного меньше максимального значения для 32-разрядного целого числа со знаком.
Теперь Функция Шудзика :
(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. 64-битный выход для 16-битных входов может быть таким непростительным !!
функция Шудзика :
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-битный для диапазона со знаком, но все же лучше.
Теперь все это пока результат всегда был положительным. В мире со знаком будет еще больше экономии места, если мы сможем перевести половину вывода на отрицательную ось . Вы можете сделать это так для Шудзика:
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 к входам и прохождения через функцию, я делю результат на два и беру некоторые из них на отрицательную ось, умножая на -1.
См. Результаты, для любого ввода в диапазоне числа битов со знаком 16 выход находится в пределах целого числа битов со знаком 32, что здорово. Я не уверен, что можно сделать то же самое для функции сопряжения Кантора, но я не пытался так сильно, как это не так эффективно. Более того, больше вычислений, связанных с функцией сопряжения Кантора, означает и ее медленную .
Вот реализация 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).
Ссылка, которую я предоставил для альтернативного решения, хорошо изображает график функции, использующей каждую точку в пространстве. Удивительно видеть, что вы можете однозначно кодировать пару координат в одно число обратимо! Волшебный мир чисел !!