Преимущества поиска ближайшего соседа с помощью порядка Мортона?
Работая над моделированием взаимодействия частиц, я наткнулся на индексирование сетки в порядке Мортона (Z-порядок) ( Ссылка на Википедию ), которая, как считается, обеспечивает эффективный поиск ближайших соседних сот. Основная причина того, что я ve read - это почти последовательное упорядочение пространственно близких ячеек в памяти.
Находясь в середине первой реализации, я не могу понять, как эффективно реализовать алгоритм для ближайших соседей, особенно по сравнению с базовой однородной сеткой.
Учитывая ячейку (x, y) легко получить 8 индексов соседних ячеек и вычислить соответствующий z-индекс. Хотя это обеспечивает постоянное время доступа к элементам, z-индекс должен либо вычисляться, либо искать его в предварительно определенных таблицах (отдельно для каждой оси и операции ИЛИ). Как это может быть более эффективным? Верно ли, что доступ к элементам в массиве A в порядке, скажем, A [0] -> A 1 -> A [3] -> A [4] -> ... более эффективен, чем в порядке A [1023] -> A [12] -> A [456] -> A [56] -> ...?
I ' Мы ожидали, что существует более простой алгоритм для поиска ближайших соседей в z-порядке. Что-то вроде: найти первую ячейку соседей, повторить. Но это не может быть правдой, так как это хорошо работает только в пределах блоков размером 2 ^ 4. Однако есть две проблемы: когда ячейка не находится на границе, можно легко определить первую ячейку блока и перебрать ячейки в блоке, но нужно проверить, является ли ячейка ближайшим соседом. Хуже того, когда ячейка лежит на границе, нужно учитывать 2 ^ 5 ячеек. Что мне здесь не хватает? Есть ли сравнительно простой и эффективный алгоритм, который сделает то, что мне нужно?
Вопрос в пункте 1. легко проверить, но я ' m не очень знаком с базовыми инструкциями, которые генерирует описанный шаблон доступа, и очень хотел бы понять, что происходит за кулисами.
Заранее благодарим за любую помощь, ссылки и т. Д.
РЕДАКТИРОВАТЬ:
Спасибо за разъяснение пункта 1! Итак, с Z-порядком скорость попадания в кеш увеличивается в среднем для соседних ячеек, что интересно. Есть ли способ профилировать процент попаданий / пропусков кеша?
По пункту 2: Я должен добавить, что я понимаю, как построить упорядоченный по Мортону массив для облака точек в R ^ d, где индекс i = f (x1, x2, ..., xd) получается из побитового чередования и т. Д. Что я пытаюсь сделать поймите, есть ли лучший способ, чем следующий наивный анзац, для получения ближайших соседей (здесь в d = 2, «псевдокод»):
// Get the z-indices of cells adjacent to the cell containing (x, y)
// Accessing the contents of the cells is irrelevant here
(x, y) \elem R^2
point = (x, y)
zindex = f(x, y)
(zx, zy) = f^(-1)(zindex) // grid coordinates
nc = [(zx - 1, zy - 1), (zx - 1, zy), (zx - 1, zy + 1), // neighbor grid
(zx , zy - 1), (zx, zy + 1), // coordinates
(zx + 1, zy - 1), (zx + 1, zy), (zx + 1, zy + 1)]
ni= [f(x[0], x[1]) for x in nc] // neighbor indices