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

Question

很抱歉问了这个含糊的问题，但我希望对于经验丰富的 Haskeller 来说这是理所当然的。

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

1. 存储 (i,j) 的完整矩阵和(j,i)元素，虽然m(i,j) = m(j,i)

   Data.Array(Int, Int) Int

2. 一张 map ，仅存储元素 (i,j)与 i <= j (上三角矩阵)

   Data.Map(Int, Int) Int

3. 索引为 k 的向量，存储给定某些向量阶的上三角矩阵 f(i,j) = k

   Data.Array Int Int

矩阵上需要进行许多操作，更新单个元素、查询行和列等。但是，它们主要充当容器，不需要线性代数运算(求逆、det 等)。

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

有什么指导方针吗？

顺便说一句:第三个选项并不是一个很好的选项，因为计算 f^-1需要平方根。

Answer 1

您可以尝试使用 Data.Array 使用专门的 Ix 类，该类仅生成矩阵的上半部分:

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