ая над моделированием взаимодействий частиц, я наткнулся на индексацию сетки в Мортон-порядке (Z-порядок) (Ссылка на википедию) который обеспечивает эффективный поиск ближайшей соседней соты. Основная причина, которую я прочитал, - это почти последовательное упорядочение пространственно близких ячеек в памяти.

Находясь в середине первой реализации, я не могу понять, как эффективно реализовать алгоритм для ближайших соседей, особенно по сравнению с базовой равномерной сеткой.

Учитывая ячейку (x, y), тривиально получить 8 индексов соседних ячеек и вычислить соответствующий z-индекс. Хотя это обеспечивает постоянное время доступа к элементам, z-индекс должен быть либо рассчитан, либо найден в предварительно определенных таблицах (отдельно для каждой оси и операции OR). Как это может быть более эффективным? Верно ли, что доступ к элементам в массиве A в порядке, скажем, A [0] -> A1 -> A [3] -> A [4] -> ... более эффективно, чем в порядке A [1023] -> A [12] -> A [456] -> A [56] -> .. .?

Я ожидал, что существует более простой алгоритм поиска ближайших соседей в z-порядке. Что-то в этом роде: найти первую ячейку соседей, повторить. Но это не может быть правдой, поскольку это хорошо работает только в пределах 2 ^ 4 блоков. Однако есть две проблемы: когда ячейка не находится на границе, можно легко определить первую ячейку блока и выполнить итерацию по ячейкам в блоке, но нужно проверить, является ли ячейка ближайшим соседом. Хуже случай, когда ячейка лежит на границе, чем нужно учитывать 2 ^ 5 ячеек. Что мне здесь не хватает? Есть ли сравнительно простой и эффективный алгоритм, который будет делать то, что мне нужно?

Вопрос в пункте 1. легко тестируется, но я не очень знаком с базовыми инструкциями, которые генерирует описанный шаблон доступа, и очень хотел бы понять, что происходит за кулисами.

Заранее спасибо за любую помощь, ссылки и т.д ...

РЕДАКТИРОВАТЬ:
Спасибо за разъяснение пункта 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