更新矩陣哈斯克爾

Question

我會列出清單代表一個項目的矩陣[A]]

• 這是一個好主意，或者我應該更好地利用陣列？

• 如何改變元素上進行索引（I，J）

Answer 1

當然，基於列表的解決方案從來沒有像優化的緊湊陣列那樣快，因爲必要的間接尋址和所有緩存局部性問題。然而，這只是一個固定的開銷因素（可能相當大，但大約爲100）。

然而，有趣的是，矩陣的嵌套列表方法並不像看起來那麼糟糕：列表仍然是以傳統的純功能方式處理的最自然的數據結構。正如millimoose所說的，你不能以純粹的方式就地改變一個元素，你必須用一個元素改變整個事物的副本。對於Ñ✕Ñ緊陣列基質，這是ø（Ñ ） - 對於較大Ñ難以接受。

雖然在長度米列表隨機訪問已經Ø（米），因此比陣列差很多，它沒有得到更復雜的操作更糟。在Ø（米）您可以「修改」的列表，你可以在Ø（ñ）訪問ň✕ň嵌套列表，你可以在Ø修改（ 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" 

會做的伎倆。

---

*有have been attempts to avoid this，但恐怕這已經證明是死路一條。如果你想要真正的高性能，你應該在ST monad中使用破壞性更新，雖然它可能不太好，但沒有什麼不對。

Answer 2

如何改變元素上進行索引（I，J）？

一般來說，你不能。您必須創建一個新的矩陣，並更改一個元素。 （使用Array而不是列表可以使這個變得稍微簡單一些，the // operator）。您可以使用MArray來進行就地更改，但幾乎所有代碼都必須使用IO。

Answer 3

如何使用自己的數據類型包裝Map (Int,Int) a？改變一個元素是微不足道的，特別是對於稀疏矩陣，你可以節省大量的內存。