1

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

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

  • 如何使用索引（i，j）更改元素

4

3 回答 3

9

当然，基于列表的解决方案永远不会像优化的紧密数组那样快，因为有必要的间接性，以及它所有的缓存局部性问题。然而，这只是一个恒定的开销因素（尽管可能相当大，大约为 100）。

然而，有趣的是，矩阵的嵌套列表方法并不像看起来那么糟糕：列表仍然是最自然地以传统的纯函数方式处理的数据结构。正如 millimoose 所说，您不能仅仅以纯粹的方式就地更改元素，您必须在更改一个元素的情况下制作整个事物的副本*。对于n ✕ n紧密阵列矩阵，这是O ( n 2 ) - 对于较大的n几乎不能接受。

虽然长度为m的列表中的随机访问已经是O ( m )，因此比数组更糟糕，但对于更复杂的操作，它并没有变得更糟。您可以在O ( m )中“修改”一个列表，您可以在O ( n )中访问一个n ✕ n嵌套列表，您可以在O ( n )中修改它！所以如果你想对大型矩阵进行无损更新，实际上比.[[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 中使用破坏性更新，虽然它可能没有那么好，但它没有任何问题。

于 2012-11-23T12:27:39.357 回答
5

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

于 2012-11-23T15:09:25.520 回答
0

如何使用索引（i，j）更改元素？

一般来说，你不能。您必须创建一个更改了一个元素的新矩阵。（使用操作符Array代替列表会稍微容易一些。//）看起来您可以使用MArray来进行就地更改，但几乎所有代码都必须使用IO.

于 2012-11-23T11:51:08.037 回答