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