更新Matrix Haskell

Question

我将通过列表[[a]]表示项目中的矩阵

• 这是一个好主意还是我应该更好地使用数组？

• 如何使用索引(i,j)更改位置元素

Answer 1

当然,基于列表的解决方案永远不会像优化的紧密阵列那样快,因为必要的间接性以及所有缓存局部性问题.然而,这只是一个恒定的开销因素(可能相当大,但大约为100).

然而,有趣的是,嵌套列表的矩阵方法并不像它看起来那么糟糕:列表仍然是以传统的纯函数方式最自然地处理的数据结构.正如millimoose所说,你不能只是以纯粹的方式就地改变一个元素,你必须用一个元素改变整个事物的副本*.对于Ñ ✕ Ñ紧阵列基质,这是Ô(Ñ ²) -对于较大难以接受Ñ.

虽然长度为m的列表中的随机访问已经是O(m),因此比数组更糟糕,但对于更复杂的操作而言,它不会变得更糟.您可以"修改"列表中的Ô(米),您可以访问ñ ✕ ñ在嵌套列表Ø(ñ),你可以在修改Ø(ñ)!因此,如果您想对大型矩阵进行非破坏性更新,[[a]]实际上要比Array a i.

哦,这是如何工作的 - 好吧,等等

type Matrix a = [[a]]
updateMatrixAt :: (Int,Int) -> (a->a) -> Matrix a -> Matrix a
updateMatrixAt(i,j) f mat
 | (upperRows, thisRow : lowerRows ) <- splitAt i mat
 , (leftCells, thisCell: rightCells) <- splitAt j thisRow
         =                  upperRows
          ++ (leftCells ++ (f thisCell): rightCells)
                          : lowerRows
 | otherwise = error "Tried to index matrix outside range"

会做的.

*曾试图避免这种情况,但我担心这已被证明是死路一条.如果你想要真正的高性能,你应该在STmonad中使用破坏性更新,它没有任何问题,虽然它可能不太好.

Answer 2

如何使用自己的数据类型包装Map (Int,Int) a？更改元素是微不足道的,特别是对于稀疏矩阵,您可以节省大量内存.