Наиболее эффективное кодирование точки с X, Y в одно уникальное число

Question

Я пытаюсь создать функцию, которая преобразует 2D-координаты (X, Y) в одно число (не имеет значения, целое число или число с плавающей запятой), но важна скорость, потому что мне нужно вызвать ее функционировать более 50 раз за кадр и 60 кадров в секунду. Который много. Кроме того, функция не может отражать себя. Я имею в виду, что мне нужен другой ответ, когда я использую что-то вроде (10, 50) или (-10, -50).

Потому что с чем-то вроде x * y и числами (10, 50) вывод равен 500, теперь, когда мы изменим числа на противоположные (- 10, -50) , результат все равно будет 500, ведь он не нужен.

Но в то же время все, что связано с экспоненциальным ростом, слишком медленное, что-то вроде 2 ** x * (2 * y + 1), хотя оно и не отражает, но имеет проблему слишком медленного с большими числами (100 000 и более) и я хотел бы высказать эту зону без лагов как можно дальше.

Надеюсь, я объяснил это достаточно ясно.

Answer 1

Python имеет целые числа бесконечной точности, так что вы можете легко кодировать это, используя два диапазона в одном и том же целом числе.

Сначала решите, какая точность вам нужна. Допустим, он равен 9,5 (до 9 общих цифр и до 5 цифр после десятичной точки), а координату, которую нужно кодировать, (107.13, 52.22).

Сначала вы найдете следующую наивысшую степень 2, превышающую 10 ^ 9, то есть 2 ^ 30.

Затем вы должны дополнить X и Y до 9 цифр без десятичный, т. е. (10713000, 5222000).

Рассматривая X как часть нижнего порядка объединенного значения, вы добавляете X к сдвинутому вверх значению Y:

10713000 + (5222000 << 30)

Теперь у вас есть большое число, которое имеет Y в верхних битах и ​​X в нижних без возможности перекрытия.

Это быстро, потому что не требует умножения, только сдвиг битов. Возможно, будет немного быстрее заменить + на | (побитовое ИЛИ), поскольку мы знаем, что нет перекрывающихся битов.

Как декодировать значения позже легко - две битовые маски и >> 30 сделают это.

Вы можете бороться с негативами, проверяя свой диапазон и используя смещение. Если допустимые значения имеют точность +/- 9,5, просто добавьте 999999999 к каждому значению перед кодированием (таким образом, самое низкое действительное значение соответствует 0, а самое высокое действительное значение соответствует 999999999 x 2, и увеличьте число сдвигов битов на единицу:

(10713000 + 999999999) | ((5222000 + 999999999) << 31)

Вот пара дополнительных скобок, чтобы было понятно.

Answer 2

Вы можете применить метод сжатия, как описано здесь . Начните с раздела 2 бумаги .

Отказ от ответственности - я один из авторов статьи. Не стесняйтесь, напишите здесь, если это кажется хорошим вариантом для вашей проблемы, и у вас есть какие-либо вопросы.