Haskell中的数组

Question

如何使用构造函数数组在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)]])

这两个会有不同的时间复杂度吗？

Answer 1

这取决于实现,但在合理的实现中,两者具有相同的复杂性(数组大小的线性).

在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(这是一个error带有消息"undefined array element" 的调用),然后列表中提供的元素被写入相应的索引按照它们出现在列表中的顺序.

一般来说,因为它是一个盒装数组,所以在构造时写入数组的是一个thunk,它指定了在需要时如何计算值(显式指定的值,如1示例中的文字,将导致直接指针写入数组的那个值).

当强制评估这样的thunk时,它也可能强制对数组中的其他thunk进行评估 - 如果thunk引用其他数组元素,就像这里一样.在这里的具体示例中,强制任何thunk导致后来强制所有thunk.在数组的早期,直到结束时,没有引用另一个数组元素的条目.在第一个示例中,如果强制的第一个数组元素是索引0处的那个,那么构建一个大小与数组长度成比例的thunk,然后减小,因此强制第一个数组元素具有复杂度O(n),然后所有其他元素都已经过评估,强制它们是O(1).在第二个例子中,情况是对称的,迫使最后一个元素首先产生总评估成本.如果要求元素的顺序不同,评估所有thunk的成本分散在不同元素的请求中,但总成本是相同的.评估任何尚未评估的thunk的成本与它与下一个已评估的thunk的距离成正比,并包括评估其间的所有thunk.

因为数组访问是恒定的时间(除了缓存效果,但是如果你向前或向后填充数组,那些不应该有所不同,如果索引是随机顺序,它们可能会产生很大的不同,但这仍然不会影响时间复杂度),都具有相同的复杂性.

但是请注意,您使用ar n来定义数组元素会带来分配多个数组的风险(如果编译没有优化,GHC就会这样做 - 只是测试:即使可能发生优化).为了确保只构建一个,请制作它

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