Enquanto trabalhava na simulação de interações de partículas, deparei-me com a indexação de grade na ordem Morton (ordem Z) (Link da Wikipedia), que é considerada uma eficiente pesquisa de célula vizinha mais próxima. A principal razão que li é a ordenação quase seqüencial de células espacialmente próximas na memória.

Por estar no meio de uma primeira implementação, não consigo entender como implementar o algoritmo de forma eficiente para os vizinhos mais próximos, especialmente em comparação com uma grade uniforme básica.

Dada uma célula (x, y), é trivial obter os 8 índices de células vizinhas e calcular o respectivo z-index. Embora isso forneça tempo de acesso constante aos elementos, o índice z deve ser calculado ou consultado em tabelas predefinidas (separadas para cada eixo e OR'ing). Como isso pode ser mais eficiente? É verdade que o acesso a elementos em uma matriz A em uma ordem diz A [0] -> A1 -> A [3] -> A [4] -> ... é mais eficiente do que na ordem A [1023] -> A [12] -> A [456] -> A [56] -> .. .?

Eu esperava que exista um algoritmo mais simples para encontrar os vizinhos mais próximos na ordem z. Algo semelhante: encontre a primeira célula de vizinhos, itere. Mas isso não pode ser verdade, pois funciona bem apenas em blocos de tamanho 2 ^ 4. No entanto, existem dois problemas: quando a célula não está no limite, é possível determinar facilmente a primeira célula do bloco e iterar pelas células do bloco, mas é preciso verificar se a célula é o vizinho mais próximo. Pior é o caso, quando a célula está no limite, do que é preciso levar em conta 2 ^ 5 células. O que estou perdendo aqui? Existe um algoritmo comparativamente simples e eficiente que fará o que eu preciso?

A pergunta no ponto 1. é facilmente testável, mas não estou muito familiarizada com as instruções subjacentes que o padrão de acesso descrito gera e realmente gostaria de entender o que está acontecendo nos bastidores.

Agradecemos antecipadamente por qualquer ajuda, referências, etc ...

EDITAR:
Obrigado por esclarecer o ponto 1! Portanto, com a ordenação Z, a taxa de acertos do cache aumenta em média para as células vizinhas, interessante. Existe uma maneira de analisar as taxas de acertos / perdidos do cache?

Em relação ao ponto 2: devo acrescentar que entendo como construir a matriz ordenada por Morton para uma nuvem de pontos em R ^ d onde o índice i = f (x1, x2, ..., xd) é obtido a partir do entrelaçamento bit a bit etc. O que tento entender é se existe uma maneira melhor do que a seguinte ansatz ingênua de obter os vizinhos mais próximos (aqui em d = 2, "pseudo código"):

// 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