Data.Map対Data.Array対称行列のですか？

Question

あいまいな質問には申し訳ありませんが、私は経験豊かなHaskellerに願っています。

Iは、対称行列を表し、操作する持っているので、データ・タイプのための3つの異なる選択肢基本的にありますm(i,j) = m(j,i)

データが、両方(i,j)と(j,i)要素を格納

1. 完全行列は配列（Int、Int）Int

2. マップのみ、要素を格納(i,j)とi <= j（上三角上三角行列を格納ARマトリックス）

   Data.Map（INT、INT）のInt

3. kによってインデックス付けベクトルは、いくつかのベクトルの順序f(i,j) = k

   Data.ArrayのIntのInt

を与え

多くの演算が行列上で必要となり、単一の要素を更新し、行と列などをクエリします。しかし、それらは主にコンテナとして機能し、線形代数演算（inversion、det、et c）が必要となります。

マトリクスの次元数が約20x20になる場合、どのオプションのうち最も高速なものがありますか？私が正しく理解すると、すべてのアップデート（アレイの場合は(//)）は完全なコピーが必要なので、ケース2または3の20x20=400の要素から20*21/2 = 210の要素に行くことは意味がありますが、ケース2の場合はアクセスが遅くなります3.ある時点で変換が必要です。

ガイドラインはありますか？

Btw：コンピューティングf^-1は平方根を必要とするため、3番目のオプションは本当に良い方法ではありません。

Answer 1

あなただけの行列の上半分を生成し、特殊な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

第4の選択肢があります。減少する大きな配列の配列を使用します。私はいずれかのオプション1（完全な配列を使用し、すべての要素を2回格納する）か、この最後のものを使用します。多くの要素を更新するつもりならば、可変配列を使うことを強くお勧めします。 IOArrayとSTArrayは一般的な選択です。

これは宿題用でない限り、Hackageも見てください。クイックルックは、行列を操作する問題が既に数回解決されていることを示唆しています。