haskell - 模拟非矩形数组

Question

很多时候，您希望数组的性能优于链表，但又不符合矩形数组的要求。

以六边形网格为例，此处显示单元 (3, 3) 的 1 距离邻居为中灰色，2 距离邻居为浅灰色。 假设我们想要一个数组，其中每个单元格包含该单元格的每个 1 和 2 距离邻居的索引。一个小问题是单元格具有不同数量的 X 距离邻居 - 网格边界上的单元格的邻居数量将少于靠近网格中心的单元格。

(出于性能原因，我们需要一个邻居索引数组——而不是从单元坐标到邻居索引的函数。)

我们可以通过跟踪每个单元有多少个邻居来解决这个问题。假设你有一个数组neighbors2 的大小为 R x C x N x 2，其中 R 是网格行数，C 为列，N 是网格中任何单元格的 2 距离邻居的最大数量。然后，通过保留一个大小为 R x C 的附加数组 n_neighbors2，我们可以跟踪 neighbors2 中的哪些索引已填充以及哪些索引刚刚填充零填充。例如，要检索单元格 (2, 5) 的 2 距离邻居，我们只需在数组中进行索引，如下所示:

someNeigh = Neighbors2[2, 5, 0..n_neighbors2[2, 5], ..]

someNeigh 将是一个 n_neighbors2[2, 5] x 2 索引数组(或 View )，其中 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 数组解决方案。

Answer 1

这是向右倾斜 30 度的图片:

正如您所看到的，您的数组实际上是完美的矩形。

邻域外围的索引很容易找到，作为围绕所选中心单元的六个直 block ，例如(假设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) 时间内访问数组。