Какой бинарный оператор или функция приводит к наименьшим коллизиям?

Question

Предположим, у нас есть два long, x и y. Какой оператор или функция, включающая x и y, мог бы создать еще один длинный z, который с наименьшей вероятностью будет равен результату применения одного и того же оператора или функции к разным x и y?

Пример: Добавление было бы плохим выбором. 1 + 4 = 5, но 2 + 3 также равно 5.

РЕДАКТИРОВАТЬ: Позвольте мне объяснить, почему я задаю этот вопрос. Я создаю космическую ролевую игру. Среда игры (solarsystems) будет процедурно генерироваться из двух семян. Эти семена состоят из координат x и y системы во вселенной. Таким образом, существует высокая вероятность того, что игрок может столкнуться с системами в (500 501) и (501 500) в ходе своих приключений. Мне нужен способ, чтобы эти солнечные системы генерировались уникально. Но я также хочу убедиться, что столько координатных пар, сколько возможно, произведут уникальные семена.

РЕДАКТИРОВАТЬ 2: Я проверил два решения, данное мне. Ответ Accipitridae намного превосходил ответ Артелия. Вот код для проверки решений:

HashSet<Long> set = new HashSet<Long>();

 for(int x=0; x<1000; x++)
  for(int y=0; y<1000; y++)
   //I commented out one of the solutions at a time
   set.add((long)(((x&0x7FFFFFFF) << 33) | ((y&0x7FFFFFFF) << 2) |   ((x>>>62) & 2) | (y>>>63)));//Artelius
   set.add((long)(x - y * 7046029254386353131l));//Accipitridae

 System.out.println(set.size());

По размеру HashSet я могу сказать, сколько уникальных семян было сгенерировано с помощью каждого метода. Для этих параметров решение Artelius сгенерировало 2048 уникальных длин, а Accipitridae сгенерировало 1000000, что означает, что столкновений не было вообще.

Спасибо всем за ваши усилия по решению этой проблемы. :)

Answer 1

Если (x1, y1) и (x2, y2) - две случайные пары входов, то пусть f1 = f(x1,y1) и f2 = f(x2,y2).

То, что вы хотите сделать, это минимизировать

P( f(x1,y1) = f(x2,y2) )
 = P(f1 = f2)
 = sum for i in [LONG_MIN ... LONG_MAX]
        of P(f1 = i) * P(f2 = i)
 = sum for i in [LONG_MIN ... LONG_MAX]
        of P(f1 = i)^2

Таким образом, вы хотите минимизировать сумму квадратов вероятностей каждого из выходов вашей функции. Поскольку сумма вероятностей должна быть 1, мы знаем:

sum for i in [LONG_MIN ... LONG_MAX]
     of P(f1 = i)
  = 1

И мы также знаем, что для всех i, P(f1 = i) находится между 0 и 1 (включительно). Таким образом, интуитивно, минимизируя P(f1 = f2), нужно сделать распределение вероятностей f1 как можно более равномерным. (Это может быть доказано математически, но это не очень важно для вопроса.) В идеале P(f1 = i) и P(f1 = j) должны быть одинаковыми для всех long s i и j.

Теперь давайте рассмотрим некоторые различные возможности для природы х и у.

Сначала общий случай, когда x и y равномерно распределены по диапазону long . (Другими словами, x в равной степени может быть любым длинным. Как и y.) В этом случае мы можем указать f(x, y) = x+y, или f(x,y) = x-y, или f(x,y) = x XOR y, или даже f(x,y) = x и ( при условии нормального целочисленного переполнения) мы находим, что у нас также есть равномерно распределенное f, что означает, что все эти функции «оптимальны».

Но пример f(x,y) = x показывает вам, что на самом деле вы можете не так много здесь заработать.

Однако на практике ваши x и y, вероятно, не будут распределены равномерно. Например, если x и y оба нарисованы случайным образом из диапазона [0, 9999], то использование f(x,y) = x + y * 10000 будет всегда , чтобы получить разные выходные данные для разных входных данных.

Если в каждой паре (x, y) весьма вероятно, что x и y будут рядом друг с другом, например, (1240,1249), (1,3), (-159720, -159721), то f(x,y) = x на самом деле довольно хорошая функция-кандидат.

Если x и y «вероятно, невелики», то вам следует объединить 16 младших битов x с 16 младшими битами y, то есть f(x,y) = ((x&0xFFFF) << 16) | (y&0xFFFF), поскольку младшие биты будут распределены более равномерно, чем старшие биты .

Это работает очень хорошо, если x и y никогда не бывают отрицательными. Но если они есть, знаковый бит (который указывает, является ли число положительным или отрицательным), может быть распределен более равномерно, чем некоторые из 16 младших битов. Таким образом, вы можете использовать его вместо этого. Э.Г.

f(x,y) = ((x&0x7FFF) << 17) | ((y&0x7FFF) << 2) | ((x>>30) & 2) | (y>>31)

Поскольку случай «вероятно, не очень большой» довольно распространен, я думаю, что эта функция на самом деле будет работать довольно хорошо.

Answer 2

Мне нравится ответ и анализ Артелиуса. Особенно предложение использовать

f (x, y) = x + y * K

для некоторой константы K интересно, и я хотел бы просто добавить еще несколько мыслей. То, что я делаю здесь, не ново, но очень тесно связано с Хеширование Фибоначчи , которое, я думаю, было предложено Кнутом.

Если мы используем 64-битные целые числа, то столкновение f (x1, y1) = f (x2, y2) означает

0 = (dx + dy * K) мод 2 ⁶⁴ ,

, где dx = x1 - x2 и dy = y1 - y2. Это так же, как

K = -dx * dy ^-1 mod 2 ⁶⁴ ,

где dy ^-1 - модульное обратное по модулю 2 ⁶⁴ . Если мы хотим выбрать K таким, что f (x1, y1)! = F (x2, y2) всякий раз, когда различия dx и dy малы, мы должны выбрать K так, чтобы

K = -dx * dy ^-1 mod 2 ⁶⁴ ,

не имеет такого решения, чтобы dx и dy были маленькими. Это может быть достигнуто, например, выбрав K близко к phi * 2 ⁶⁴ , где phi = (sqrt (5) -1) / 2 - золотое сечение. Золотое сечение имеет очень особое постоянное расширение дроби, то есть в определенном смысле это число, которое трудно хорошо аппроксимировать дробью.

Следовательно, для 64-разрядных целых чисел без знака можно использовать следующие функции

f (x, y) = x + y * 11400714819323198485;

или эквивалентно при использовании 64-битных целых чисел со знаком

f (x, y) = x - y * 7046029254386353131;

Answer 3

Пока вы ограничиваете набор возможных выходных значений тем же набором значений, что и операнды, которые вы используете в качестве операндов, вы не сможете сделать ничего лучше, чем сложение. Дополнение, на самом деле, вероятно, является наилучшим из возможных вариантов, потому что оно самое простое. (См. Анализ ниже)

Существует 2 ^ 64 возможных длин, поэтому есть 2 ^ 127 возможных неупорядоченных пар длин и только 2 ^ 64 возможных длин для ответа, поэтому наилучший возможный коэффициент распределения - это 2 ^ 63 различных пар, которые дают тот же ответ, который сложение (с опрокидыванием) на самом деле будет делать

РЕДАКТИРОВАТЬ: на основе комментариев ниже.

сколько бы ни было (скажем, это N битов) длинных, есть 2 ^ N разных длин, поэтому есть 2 ^ N x 2 ^ N упорядоченных пар длинных, но для целей этого анализа используются два длинных x и y в точности совпадает с использованием y и x (двоичный оператор считается коммуникативным), поэтому существует 2 ^ (2N-1) неупорядоченных пар длинных.

, поэтому при использовании неупорядоченных пар (вдвое меньше) существует 2 ^ N x (2 ^ N-1) или 2 ^ (2N-1) пар длин без дубликатов. (Если N = 64, то это 2 ^ 127). Таким образом, максимальное «распределение» распределения ответов (из меньшего набора из 2 ^ 64 длин) по неупорядоченным парам операндов (больший набор из 2 ^ 127 пар) они равномерно распределены. Вот что будет делать сложение, потому что для каждого из возможных длин в наборе всех длинных сумма его с каждым другим длинным (с опрокидыванием) будет набором ... каждого длинного.

единственное, что используются упорядоченные пары, - это то, что вы также можете использовать некоммуникативный операнд, но тогда вам придется иметь дело со всеми случаями, когда ответ не входит в набор, который вы используете для операндов (например, 5 / 4) но даже если вы просто предполагаете округление, единственное влияние на анализ состоит в том, что при использовании упорядоченных пар вы получаете 2 ^ 2N различных пар операндов вместо 2 ^ (2N-1).

Что вы можете сделать, это ограничить набор целых чисел, которые будут использоваться в качестве операндов, меньшим, чем квадратный корень из числа возможных длин (поэтому, если вы используете 64-битные длины, ограничьте свои входные значения 32-битными длинами) Затем, если вы не хотите абсолютно никакого перекрытия или дублирования (ни в одном случае, когда A op B = то же значение, что и у любого другого C op D), вы можете использовать оператор умножения, но для каждого значения X в меньшем наборе потенциальных операндов выберите X-й простое число как мультипликативный операнд. таким образом, независимо от того, какие два значения A и B вы выберете случайным образом (от 1 до макс.), операция будет умножением двух различных простых чисел. Это означает, что набор возможных операндов должен быть меньше, чем набор простых чисел, равных или меньших, чем максимально возможное значение, которое вы используете для операнда (если это 64-битные значения без знака, то это 2 ^ 64)

2-е РЕДАКТИРОВАНИЕ: в зависимости от конкретной проблемы, набор возможных операндов ограничен размерами экрана компьютера, значительно меньшим, чем количество длинных (независимо от того, на какой платформе вы находитесь). Так что это очень просто и очевидно. Чтобы гарантировать, что каждая пара возможных экранных координат будет генерировать отдельный и отличный начальный ключ, достаточно просто сдвинуть влево значение одной координаты в достаточной степени, чтобы гарантировать отсутствие побитового перекрытия с другой координатой, а затем побитового или результата с другой координатой.

Так что, если ваш экран, скажем, 3000x3000, то long lngVal = (x << 12 | y) сделает это с минимальными вычислительными затратами. </p>