Сортировать Гильберта по алгоритму "разделяй и властвуй"?
Я пытаюсь отсортировать d-мерные векторы данных по их порядку Гильберта для массовой загрузки пространственного индекса.
Однако я не хочу явно вычислять значение Гильберта для каждой точки, что, в частности, требует установки определенной точности. В многомерных данных это включает в себя точность, такую как 32*d биты, что становится довольно грязно, чтобы сделать эффективно. Когда данные распределены неравномерно, некоторые из этих расчетов не нужны, и необходима дополнительная точность для частей набора данных.
Вместо этого я пытаюсь сделать подход разделения. Когда вы смотрите на двумерную кривую Гильберта первого порядка
1 4
| |
2---3
Сначала я бы разделил данные вдоль оси x, чтобы первая часть (не обязательно содержавшая половину объектов!) Состояла из 1 и 2 (еще не отсортированных), а вторая часть - из объектов 3 и 4. только. Затем я бы снова разделил каждую половину по оси Y, но изменил порядок в 3-4.
По сути, я хочу выполнить стратегию "разделяй и властвуй" (тесно связанную с быстрой сортировкой - для равномерно распределенных данных это должно быть даже оптимально!) И вычисляя только необходимые "биты" индекса Гильберта по мере необходимости. Таким образом, если предположить, что в "1" есть один объект, то нет необходимости вычислять его полное представление; и если объекты распределены равномерно, размеры разделов быстро уменьшатся.
Я знаю обычный учебный подход, заключающийся в преобразовании в длинное, с серым кодированием, чередование измерений. Это не то, что я ищу (есть множество примеров этого). Я явно хочу только ленивую сортировку " разделяй и властвуй". Плюс мне нужно больше чем 2D.
Кто-нибудь знает статью или алгоритм сортировки Гильберта, который работает таким образом? Или ключевая идея, как правильно "вращать", какое представление выбрать для этого? В частности, в более высоких измерениях... в 2D это тривиально; 1 поворачивается +y, +x, а 4 - -y,-x (поворачивается и переворачивается). Но в более высоких измерениях это становится более сложным, я думаю.
(Результат, конечно, должен быть таким же, как и при сортировке объектов по их порядку Гильберта с достаточно большой точностью сразу; я просто пытаюсь сэкономить время, вычисляя полное представление, когда оно не нужно, и необходимость управлять им. Многие люди держат хэш-карту "объект в число Гильберта", что довольно дорого.)
Подобные подходы должны быть возможны для кривых Пеано и Z-кривой, и, возможно, немного проще для реализации... Я, вероятно, должен сначала попробовать их (Z-кривая уже работает - она действительно сводится к чему-то, очень похожему на QuickSort, используя соответствующее среднее значение / значение сетки в виде виртуального центра и циклического прохождения измерений для каждой итерации).
Изменить: см. Ниже, как я решил это для Z и кривых Пеано. Это также работает для 2D кривых Гильберта. Но у меня пока нет правильных поворотов и инверсий для кривых Гильберта.
3 ответа
Используйте основную сортировку. Разделить каждый одномерный индекс на d .. 32 части, каждая размером 1 .. 32/d биты. Затем (от старших разрядов до младших разрядов) для каждого элемента индекса вычисляют его значение Гильберта и перетасовывают объекты в соответствующие ячейки.
Это должно хорошо работать как с равномерно, так и с неравномерно распределенными данными, как с порядком Гильберта, так и с Z-порядком. И нет необходимости в многоточечных расчетах.
Одна деталь о преобразовании частей индекса в порядок Гильберта:
- сначала извлечь необходимые биты,
- затем чередовать биты из всех измерений,
- затем преобразуйте одномерные индексы в обратный код Грея.
Если индексы хранятся в двойниках:
- Если индексы могут быть отрицательными, добавьте некоторое значение, чтобы сделать все положительным и тем самым упростить задачу.
- Определите наименьшую целочисленную степень 2, которая больше всех индексов, и разделите все индексы на это значение
- Умножьте индекс на 2^(необходимое количество бит для текущего шага сортировки). Обрезать результат, преобразовать его в целое число и использовать его для упорядочения Гильберта (чередование и вычисление обратного кода Грея)
- Вычтите результат, усеченный на предыдущем шаге, из индекса:
index = index - i
Что касается вашего варианта сортировки по основанию, я бы предложил расширить zsort (чтобы сделать hilbertsort из zsort) двумя двоичными массивами размера d (один используется в основном как стек, другой используется для инвертирования битов индекса) и значение поворота (используется для перестановки размеров).
Если верхнее значение в стеке равно 1, измените pivotize(... восходящий) на pivotize(... нисходящий), а затем для первой части рекурсии поместите это верхнее значение в стек, для второй - нажмите обратное значение Этот стек следует восстанавливать после каждой рекурсии. Содержит "дерево решений" последнего d рекурсии процедуры радикальной сортировки (в обратном коде Грея).
После d рекурсии этот стек "дерева решений" должен использоваться для пересчета как значения вращения, так и массива инверсий. Точный способ, как это сделать, нетривиален. Его можно найти по следующим ссылкам: hilbert.c или hilbert.c.
Вы можете вычислить кривую Гильберта из f(x)=y напрямую, без использования рекурсии или L-систем, или "разделяй и властвуй". В основном это серый код или обход гамильтоновых путей. Вы можете найти хорошее описание в блоге Nad, посвященном пространственному индексу Гильберта Кривого, или в восхищении хакера. Или взгляните на монотонный н-арый серый код. Я написал реализацию в php, включая кривую Мура.
Я уже ответил на этот (и другие) вопрос, но мои ответы загадочным образом исчезли. Реализация компактного индекса Гильберта из http://code.google.com/p/uzaygezen/source/browse/trunk/core/src/main/java/com/google/uzaygezen/core/CompactHilbertCurve.java (метод index()) уже позволяет ограничить число битов индекса Гильберта, вычисляемых до заданного уровня. Каждая итерация цикла из упомянутого метода вычисляет количество битов, равное размерности пространства. Вы можете легко реорганизовать цикл for для вычисления только одного уровня (т. Е. Количества бит, равного размерности пространства) за раз, делая это настолько глубоко, насколько необходимо для сравнения лексикографически двух чисел по их компактному индексу Гильберта.