對於對稱矩陣，Data.Map與Data.Array？

Question

對不起，這個模糊的問題，但我希望對一個有經驗的Haskeller這是一個明智之舉。

我有表示和操縱對稱矩陣，所以有基本上爲數據類型三個不同​​的選項：

1. 完整矩陣存儲兩個(i,j)和(j,i)元件，雖然m(i,j) = m(j,i)

   數據。陣列（Int，Int）Int

2. 一張僅存儲元素(i,j)與i <= j（上三角形AR矩陣）

   Data.Map（INT，INT）中等

3. 通過k索引的矢量，存儲給定的一些矢量順序f(i,j) = k

   Data.Array詮釋詮釋

上三角矩陣

許多操作對矩陣都是必需的，更新單個元素，查詢行和列等。但是，它們主要充當容器，沒有線性代數運算（反演，det等c）將是必需的。

如果矩陣的維數將在20x20左右，哪一個選項是最快的選項？當我理解正確的時候，每個更新（在數組情況下爲(//)）需要完整副本，因此在情況2或3中從20x20=400元素到20*21/2 = 210元素會有很大的意義，但是對於情況2 。和3.需要在某個時候進行轉換。

是否有任何指導方針？

順便說一句：第三個選項不是一個很好的選擇，因爲計算f^-1需要平方根。

Answer 1

你可以嘗試使用Data.Array使用專門的九類僅生成矩陣的上半部分：

newtype Symmetric = Symmetric { pair :: (Int, Int) } deriving (Ord, Eq) 

instance Ix Symmetric where 
    range ((Symmetric (x1,y1)), (Symmetric (x2,y2))) = 
     map Symmetric [(x,y) | x <- range (x1,x2), y <- range (y1,y2), x >= y] 
    inRange (lo,hi) i = x <= hix && x >= lox && y <= hiy && y >= loy && x >= y 
     where 
      (lox,loy) = pair lo 
      (hix,hiy) = pair hi 
      (x,y) = pair i 
    index (lo,hi) i 
     | inRange (lo,hi) i = (x-loy)+(sum$take(y-loy)[hix-lox, hix-lox-1..]) 
     | otherwise = error "Error in array index" 
     where 
      (lox,loy) = pair lo 
      (hix,hiy) = pair hi 
      (x,y) = pair i 

sym x y 
    | x < y = Symmetric (y,x) 
    | otherwise = Symmetric (x,y) 



*Main Data.Ix> let a = listArray (sym 0 0, sym 6 6) [0..] 
*Main Data.Ix> a ! sym 3 2 
14 
*Main Data.Ix> a ! sym 2 3 
14 
*Main Data.Ix> a ! sym 2 2 
13 
*Main Data.Ix> length $ elems a 
28 
*Main Data.Ix> let b = listArray (sym 0 0, sym 19 19) [0..] 
*Main Data.Ix> length $ elems b 
210 

Answer 2

還有第四種選擇：使用一個遞減大數組的數組。我會選擇1（使用完整的數組，並將每個元素存儲兩次）或最後一個。如果您打算更新很多元素，我強烈建議使用可變數組; IOArray和STArray是流行的選擇。

除非這是作業或其他東西，否則您還應該查看Hackage。快速查看錶明操縱矩陣的問題已經被解決了幾次。