Является ли код Мортона наиболее эффективным для больших измерений?
Для моих текущих входных данных, которые представляют собой точки в 3D, я использую код Мортона для улучшения согласованности кэша при доступе к списку точек.
У меня есть некоторые другие данные, которые 6D и 7D. Является ли код Мортона хорошей техникой для таких измерений? Или есть другие методы? Другие методы кривой заполнения пространства были более сложными для вычисления, чем Мортон в самом 3D, мне интересно, используют ли люди альтернативную технику для 6D/7D или выше.
1 ответ
Вы должны попробовать индексирование по строкам и строкам. Они также сохраняют пространственную локализацию, но могут быть вычислены более эффективно, даже в более высоких измерениях.
Более подробно (но в менее геометрическом смысле) вы можете прочитать о индексировании по ряду и по столбцам в книге "Язык ассемблера", глава 5, стр. 211-216. Соответствующая глава доступна онлайн здесь.
И есть хорошая статья о различных методах пространственной индексации, которые вы можете рассмотреть, включая упомянутые: Самет, H. 2017. Сортировка пространственных данных. Международная энциклопедия географии. 1-11.
Индекс Гильберта и Грея здесь не вариант, так как они медленнее вычисляются, чем Мортон (большинство их реализаций содержат неявное кодирование Мортона). В основном правильная реализация Morton (на основе таблиц поиска или на основе магических чисел) и индексация по строкам / столбцам являются самыми быстрыми.