Haskell中的数组

Question

Haskell中的数组

6

使用构造函数array在Haskell中如何创建一个数组？我的意思是，它是否创建第一个元素等等？如果是这样的话，它如何读取关联列表？

例如，如果我们考虑以下两个程序：

ar :: Int->(Array Int Int)
ar n = array (0,(n-1)) (((n-1),1):[(i,((ar n)!(i+1))) | i<-[0..(n-2)]])

ar :: Int->(Array Int Int)
ar n = array (0,(n-1)) ((0,1):[(i,((ar n)!(i-1))) | i<-[1..(n-1)]])

这两个是否具有不同的时间复杂度？

- Chandan

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Daniel Fischer · Accepted Answer

这取决于具体实现，但在合理的实现中，两者具有相同的复杂度（与数组大小成线性关系）。

在 GHC 的数组实现中，如果我们查看代码：

array (l,u) ies
    = let n = safeRangeSize (l,u)
      in unsafeArray' (l,u) n
                      [(safeIndex (l,u) n i, e) | (i, e) <- ies]

{-# INLINE unsafeArray' #-}
unsafeArray' :: Ix i => (i,i) -> Int -> [(Int, e)] -> Array i e
unsafeArray' (l,u) n@(I# n#) ies = runST (ST $ \s1# ->
    case newArray# n# arrEleBottom s1# of
        (# s2#, marr# #) ->
            foldr (fill marr#) (done l u n marr#) ies s2#)

{-# INLINE fill #-}
fill :: MutableArray# s e -> (Int, e) -> STRep s a -> STRep s a
-- NB: put the \s after the "=" so that 'fill' 
--     inlines when applied to three args 
fill marr# (I# i#, e) next 
 = \s1# -> case writeArray# marr# i# e s1# of 
             s2# -> next s2#

我们可以看到，首先为数组分配了一块新的内存，然后按顺序填充了arrEleBottom（这是一个带有消息“undefined array element”的error调用），然后将列表中提供的元素按它们在列表中出现的顺序写入到相应的索引中。

通常来说，由于它是一个装箱数组，在构造时写入数组的内容是一个惰性求值器，它指定了在需要时如何计算该值（显式指定的值，例如你的示例中的文字1，将导致直接指向该值的指针被写入数组）。

当强制求值这样的惰性求值器时，它可能会强制求值数组中的进一步的惰性求值器 - 如果该惰性求值器引用其他数组元素，就像这里一样。在这些具体的示例中，强制求值任何惰性求值器都会导致强制求值数组中之后或之前的所有惰性求值器，直到达到不引用另一个数组元素的条目为止。在第一个示例中，如果强制求值的第一个数组元素是索引0处的元素，则会构建一个大小与数组长度成比例的惰性求值器，然后缩减该惰性求值器，因此强制求值第一个数组元素的复杂度为O(n)，然后所有其他元素已经被评估，因此强制它们是O(1)。在第二个示例中，情况是对称的，强制求值最后一个元素会导致总评估成本。如果以不同的顺序要求元素，则评估所有惰性求值器的成本将分布在对不同元素的请求中，但总成本是相同的。评估任何尚未评估的惰性求值器的成本与其距离下一个已评估的惰性求值器成正比，并包括在它们之间评估所有惰性求值器的成本。

由于数组访问是常数时间（除了缓存效应，但如果你向前或向后填充数组，这些效应不应该有太大影响，如果索引是随机的，那么它们可能会产生很大的影响，但这仍然不会影响时间复杂度），两者的复杂度相同。

请注意，使用ar n来定义数组元素存在多次分配数组的风险（如果没有优化编译，GHC会这样做 - 我刚测试过：即使进行了优化也可能发生）。为确保只构造一个数组，请改为

ar n = result
  where
    result = array (0,n-1) (... result!index ...)