Эмуляция непрямоугольных массивов
Часто требуется, чтобы производительность массивов по связанным спискам не соответствовала требованию иметь прямоугольные массивы.
В качестве примера рассмотрим гексагональную сетку, показанную здесь с соседями 1-го расстояния ячейки (3, 3) в среднем сером и соседями 2-го расстояния в светло-сером. 
Скажем, нам нужен массив, который содержит для каждой ячейки индексы каждого соседа на 1 и 2 расстояния для этой ячейки. Одна небольшая проблема заключается в том, что ячейки имеют различное количество соседей по расстоянию X- ячейки на границе сетки будут иметь меньше соседей, чем ячейки, расположенные ближе к центру сетки.
(Мы хотим получить массив индексов соседей - вместо функции от координат ячейки до индексов соседей - из соображений производительности.)
Мы можем обойти эту проблему, отслеживая количество соседей в каждой ячейке. Скажем, у вас есть массив neighbors2 размера R x C x N x 2, где R количество строк сетки, C для столбцов и N максимальное количество соседей с двумя расстояниями для любой ячейки в сетке. Затем, сохраняя дополнительный массив n_neighbors2 размера R x Cмы можем отслеживать, какие индексы в neighbors2 заселены и которые просто заполнены нулями. Например, чтобы получить соседей ячейки с двумя расстояниями (2, 5), мы просто индексируем массив как таковой:
someNeigh = neighbors2[2, 5, 0..n_neighbors2[2, 5], ..]
someNeigh будет n_neighbors2[2, 5] x 2 массив (или вид) указателей, где someNeigh[0, 0] выдает строку первого соседа и someNeigh[0, 1] дает столбец первого соседа и пр. Обратите внимание, что элементы на позициях
neighbors2[2, 5, n_neighbors2[2, 5]+1.., ..]
не имеют значения; это пространство просто заполнение, чтобы держать матрицу прямоугольной.
При условии, что у нас есть функция для нахождения соседей d-расстояния для любой ячейки:
import Data.Bits (shift)
rows, cols = (7, 7)
type Cell = (Int, Int)
generateNeighs :: Int -> Cell -> [Cell]
generateNeighs d cell1 = [ (row2, col2)
| row2 <- [0..rows-1]
, col2 <- [0..cols-1]
, hexDistance cell1 (row2, col2) == d]
hexDistance :: Cell -> Cell -> Int
hexDistance (r1, c1) (r2, c2) = shift (abs rd + abs (rd + cd) + abs cd) (-1)
where
rd = r1 - r2
cd = c1 - c2
Как мы можем создать вышеупомянутые массивы neighbors2 а также n_neighbors2? Предположим, мы знаем максимальное количество соседей на 2 расстояния N заранее. Тогда можно изменить generateNeighs всегда возвращать списки одинакового размера, так как мы можем заполнить оставшиеся записи с (0, 0). Это оставляет, на мой взгляд, две проблемы:
- Нам нужна функция для заполнения
neighbors2который работает не с каждым отдельным индексом, а над срезом, в нашем случае он должен заполнять по одной ячейке за раз. n_neighbors2должны быть заполнены одновременно какneighbors2
Решение приветствуется либо с repa или же accelerate массивы.
3 ответа
Вот вам картинка с перекосом на 30 градусов вправо:
Как вы можете видеть, ваш массив на самом деле совершенно прямоугольный.
Индексы периферии соседства легко найти в виде шести прямых частей вокруг выбранной центральной ячейки, например (представьте n == 2 это расстояние периферии от центра (i,j) == (3,3) на картинке):
periphery n (i,j) =
-- 2 (3,3)
let
((i1,j1):ps1) = reverse . take (n+1) . iterate (\(i,j)->(i,j+1)) $ (i-n,j)
-- ( 1, 3)
((i2,j2):ps2) = reverse . take (n+1) . iterate (\(i,j)->(i+1,j)) $ (i1,j1)
-- ( 1, 5)
.....
ps6 = ....... $ (i5,j5)
in filter isValid (ps6 ++ ... ++ ps2 ++ ps1)
Весь район просто
neighborhood n (i,j) = (i,j) : concat [ periphery k (i,j) | k <- [1..n] ]
Для каждой комбинации ячейка / расстояние просто сгенерируйте индексы окрестности на лету и получите доступ к вашему массиву за O(1) времени для каждой пары индексов.
Полностью выписываем ответ от @WillNess и включаем предложение @leftroundabout вместо хранения индексов в одномерном векторе, и мы получаем это:
import qualified Data.Array.Accelerate as A
import Data.Array.Accelerate (Acc, Array, DIM1, DIM2, DIM3, Z(..), (:.)(..), (!), fromList, use)
rows = 7
cols = 7
type Cell = (Int, Int)
(neighs, nNeighs) = generateNeighs
-- Return a vector of indices of cells at distance 'd' or less from the given cell
getNeighs :: Int -> Cell -> Acc (Array DIM1 Cell)
getNeighs d (r,c) = A.take n $ A.drop start neighs
where
start = nNeighs ! A.constant (Z :. r :. c :. 0)
n = nNeighs ! A.constant (Z :. r :. c :. d)
generateNeighs :: (Acc (Array DIM1 Cell), Acc (Array DIM3 Int))
generateNeighs = (neighsArr, nNeighsArr)
where
idxs = concat [[(r, c) | c <- [0..cols-1]] | r <- [0..rows-1]]
(neighsLi, nNeighsLi, n) = foldl inner ([], [], 0) idxs
neighsArr = use $ fromList (Z :. n) neighsLi
nNeighsArr = use $ fromList (Z :. rows :. cols :. 5) nNeighsLi
inner (neighs', nNeighs', n') idx = (neighs' ++ cellNeighs, nNeighs'', n'')
where
(cellNeighs, cellNNeighs) = neighborhood idx
n'' = n' + length cellNeighs
nNeighs'' = nNeighs' ++ n' : cellNNeighs
neighborhood :: Cell -> ([Cell], [Int])
neighborhood (r,c) = (neighs, nNeighs)
where
neighsO = [ periphery d (r,c) | d <- [1..4] ]
neighs = (r,c) : concat neighsO
nNeighs = tail $ scanl (+) 1 $ map length neighsO
periphery d (r,c) =
-- The set of d-distance neighbors form a hexagon shape. Traverse each of
-- the sides of this hexagon and gather up the cell indices.
let
ps1 = take d . iterate (\(r,c)->(r,c+1)) $ (r-d,c)
ps2 = take d . iterate (\(r,c)->(r+1,c)) $ (r-d,c+d)
ps3 = take d . iterate (\(r,c)->(r+1,c-1)) $ (r,c+d)
ps4 = take d . iterate (\(r,c)->(r,c-1)) $ (r+d,c)
ps5 = take d . iterate (\(r,c)->(r-1,c)) $ (r+d,c-d)
ps6 = take d . iterate (\(r,c)->(r-1,c+1)) $ (r,c-d)
in filter isValid (ps6 ++ ps5 ++ ps4 ++ ps3 ++ ps2 ++ ps1)
isValid :: Cell -> Bool
isValid (r, c)
| r < 0 || r >= rows = False
| c < 0 || c >= cols = False
| otherwise = True
Это может быть сделано с помощью функции перестановки для заполнения соседей на 1 ячейку за раз.
import Data.Bits (shift)
import Data.Array.Accelerate as A
import qualified Prelude as P
import Prelude hiding ((++), (==))
rows = 7
cols = 7
channels = 70
type Cell = (Int, Int)
(neighs, nNeighs) = fillNeighs
getNeighs :: Cell -> Acc (Array DIM1 Cell)
getNeighs (r, c) = A.take (nNeighs ! sh1) $ slice neighs sh2
where
sh1 = constant (Z :. r :. c)
sh2 = constant (Z :. r :. c :. All)
fillNeighs :: (Acc (Array DIM3 Cell), Acc (Array DIM2 Int))
fillNeighs = (neighs2, nNeighs2)
where
sh = constant (Z :. rows :. cols :. 18) :: Exp DIM3
neighZeros = fill sh (lift (0 :: Int, 0 :: Int)) :: Acc (Array DIM3 Cell)
-- nNeighZeros = fill (constant (Z :. rows :. cols)) 0 :: Acc (Array DIM2 Int)
(neighs2, nNeighs2li) = foldr inner (neighZeros, []) indices
nNeighs2 = use $ fromList (Z :. rows :. cols) nNeighs2li
-- Generate indices by varying column fastest. This assures that fromList, which fills
-- the array in row-major order, gets nNeighs in the correct order.
indices = foldr (\r acc -> foldr (\c acc2 -> (r, c):acc2 ) acc [0..cols-1]) [] [0..rows-1]
inner :: Cell
-> (Acc (Array DIM3 Cell), [Int])
-> (Acc (Array DIM3 Cell), [Int])
inner cell (neighs, nNeighs) = (newNeighs, n : nNeighs)
where
(newNeighs, n) = fillCell cell neighs
-- Given an cell and a 3D array to contain cell neighbors,
-- fill in the neighbors for the given cell
-- and return the number of neighbors filled in
fillCell :: Cell -> Acc (Array DIM3 Cell) -> (Acc (Array DIM3 Cell), Int)
fillCell (r, c) arr = (permute const arr indcomb neighs2arr, nNeighs)
where
(ra, ca) = (lift r, lift c) :: (Exp Int, Exp Int)
neighs2li = generateNeighs 2 (r, c)
nNeighs = P.length neighs2li
neighs2arr = use $ fromList (Z :. nNeighs) neighs2li
-- Traverse the 3rd dimension of the given cell
indcomb :: Exp DIM1 -> Exp DIM3
indcomb nsh = index3 ra ca (unindex1 nsh)
generateNeighs :: Int -> Cell -> [Cell]
generateNeighs d cell1 = [ (row2, col2)
| row2 <- [0..rows]
, col2 <- [0..cols]
, hexDistance cell1 (row2, col2) P.== d]
-- Manhattan distance between two cells in an hexagonal grid with an axial coordinate system
hexDistance :: Cell -> Cell -> Int
hexDistance (r1, c1) (r2, c2) = shift (abs rd + abs (rd + cd) + abs cd) (-1)
where
rd = r1 - r2
cd = c1 - c2