对称矩阵的Data.Map与Data.Array？

Question

对于模糊的问题很抱歉,但我希望有经验的Haskeller,这是一个明智的选择.

我必须表示和操作对称矩阵,因此数据类型基本上有三种不同的选择:

1. 尽管如此,完整的矩阵存储(i,j)和(j,i)元素m(i,j) = m(j,i)

   Data.Array(Int,Int)Int

2. 一个地图,只存储(i,j)带有i <= j(上三角矩阵)的元素

   Data.Map(Int,Int)Int

3. 由索引索引的向量k,存储给定一些向量顺序的上三角矩阵f(i,j) = k

   Data.Array Int Int

在矩阵上需要进行许多操作,更新单个元素,查询行和列等.但是,它们主要用作容器,不需要线性代数运算(反转,det等).

如果矩阵的维数将在附近,那么哪一个选项通常是最快的20x20？当我理解正确时,每次更新((//)在数组的情况下)都需要完整的副本,因此在案例2或3中从20x20=400元素到20*21/2 = 210元素会很有意义,但对于案例2和3的访问速度较慢.在某些时候需要转换.

有没有指导方针？

顺便说一句:第三种选择并不是一个非常好的选择,因为计算f^-1需要平方根.

Answer 1

您可以尝试使用仅生成矩阵上半部分的专用Ix类使用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