Я пытаюсь сортировать d-мерные векторы данных по их порядку Гильберта, для объемной загрузки пространственного индекса.
Однако я не хочу явно вычислять значение Гильберта для каждой точки, что, в частности, требует установки определенной точности. В высокоразмерных данных это включает в себя точность, такую как бит 32*d, который становится довольно грязным для эффективного выполнения. Когда данные распределяются неравномерно, некоторые из этих вычислений не нужны, и необходима дополнительная точность для частей набора данных.
Вместо этого я пытаюсь сделать подход к разделению. Когда вы смотрите на двумерную кривую Гильберта первого порядка
1 4
| |
2---3
Сначала я разделил данные по оси x, так что первая часть (не обязательно содержащая половину объектов!) будет состоять из 1 и 2 (еще не отсортирована), а вторая часть будет иметь объекты из 3 и 4. Затем я разделил бы каждую половину по оси Y, но изменил бы порядок на 3-4.
Поэтому, по сути, я хочу выполнить стратегию "разделяй и властвуй" (тесно связанную с QuickSort - на равномерно распределенных данных, это должно быть даже оптимальным!), и только вычислять необходимые "биты" индекса гильберта по мере необходимости. Итак, предполагая, что в "1" есть один объект, тогда нет необходимости вычислять его полное представление; и если объекты распределены равномерно, размеры разделов быстро упадут.
Я знаю обычный учебный подход для преобразования в длинное, серое кодирование, измерение чередования. Это не то, что я ищу (есть много примеров этого). Я явно хочу, чтобы ленивая сортировка "разделяй и властвуй". Кроме того, мне нужно больше, чем 2D.
Кто-нибудь знает статью или алгоритм сортировки гильберта, который работает таким образом? Или ключевая идея, как правильно получить "вращения", какое представление выбрать для этого? В частности, в более высоких размерностях... в 2D это тривиально; 1 вращается + y, + x, а 4 - -y, -x (повернут и перевернут). Но в более высоких измерениях это становится более сложным, я думаю.
(Результат должен быть таким же, как при сортировке объектов по их гильбертовому порядку с достаточно большой точностью сразу, я просто пытаюсь сэкономить время, вычисляя полное представление, когда это не нужно, и нужно управлять Многие люди хранят хэш-карту "объект с номером гильберта", что довольно дорого.)
Подобные подходы должны быть возможны для кривых Пеано и Z-кривой и, вероятно, немного проще реализовать... Я, наверное, должен попробовать их в первую очередь (Z-кривая уже работает - она действительно сводится к чему-то очень близкому к QuickSort, используя соответствующее среднее значение/значение сетки как виртуальный поворот и циклическое перемещение по размерам для каждой итерации).
Изменить: см. ниже, как я решил это для кривых Z и peano. Он также работает для 2D кривых Гильберта. Но у меня еще нет поворотов и инверсии для кривых Гильберта.
