Haskell中的非单片阵列

Question

我接受了下面问题的答案,但似乎我误解了haskell中的Arrays是如何工作的.我以为他们只是加强了名单.阅读以下问题时请记住这一点.

---

我发现haskell中的单片阵列在将它们用于较大的阵列时效率很低.

我无法在haskell中找到非单片的数组实现.我需要的是O(1)时间查找多维数组.

是否有支持这种情况的数组实现？

编辑:我似乎误解了整体一词.问题是似乎haskell中的数组像列表一样处理数组.我可能错了.

EDIT2:低效代码的简短示例:

fibArray n = a where
  bnds = (0,n)
  a = array bnds [ (i, f i) | i <- range bnds ]
  f 0 = 0
  f 1 = 1
  f i = a!(i-1) + a!(i-2)

这是一个长度数组,n+1其中第i个字段包含第i个斐波纳契数.但由于haskell中的数组具有O(n)时间查找,因此计算需要O(n²)时间.

Answer 1

你把Haskell中的链表与数组混淆了.

链接列表是使用以下语法的数据类型:

[1,2,3,5]

定义为:

data [a] = [] | a : [a]

这些是经典的递归数据类型,支持O(n)索引和O(1)前置.

如果您正在寻找具有O(1)查找的多维数据,则应使用真正的数组或矩阵数据结构.好的候选人是:

• 修复 - 快速,并行,多维数组 - (教程)
• Vector - Int-indexed数组(可变和不可变)的有效实现,具有强大的循环优化框架.(教程)
• HMatrix - 基本线性代数和其他数值计算的纯函数接口,内部使用GSL,BLAS和LAPACK实现.

Answer 2

数组有O(1)索引.问题是每个元素都是懒惰计算的.所以当你在ghci中运行时会发生这种情况:

*Main> :set +s
*Main> let t = 100000
(0.00 secs, 556576 bytes)
*Main> let a = fibArray t
Loading package array-0.4.0.0 ... linking ... done.
(0.01 secs, 1033640 bytes)
*Main> a!t  -- result omitted
(1.51 secs, 570473504 bytes)
*Main> a!t  -- result omitted
(0.17 secs, 17954296 bytes)
*Main> 

请注意,在查找一次之后,查找速度非常快.该array函数创建一个指向thunks的指针数组,最终将计算这些指针以生成值.第一次评估价值时,您需要支付此费用.以下是评估thunk的前几个扩展a!t:

a!t -> a!(t-1)+a!(t-2)-> a!(t-2)+a!(t-3)+a!(t-2) -> a!(t-3)+a!(t-4)+a!(t-3)+a!(t-2)

计算本身的成本并不昂贵,而是需要创建和遍历这个非常大的thunk.

我试图严格传递给列表中的值array,但这似乎导致无限循环.

一种常见的方法是使用可变数组,例如STArray.元素可以在阵列创建期间更新,并且最终结果被冻结并返回.在vector包中,create和constructN函数提供了简单的方法.

-- constructN :: Unbox a => Int -> (Vector a -> a) -> Vector a


import qualified Data.Vector.Unboxed as V
import Data.Int

fibVec :: Int -> V.Vector Int64
fibVec n = V.constructN (n+1) c
 where
  c v | V.length v == 0 = 0 
  c v | V.length v == 1 = 1 
  c v | V.length v == 2 = 1
  c v = let len = V.length v
        in v V.! (len-1) + v V.! (len-2)

但是,该fibVec功能仅适用于未装箱的矢量.常规向量(和数组)不够严格,导致回到您已经发现的同样问题.不幸的是,没有一个Unboxed实例Integer,所以如果你需要无界的整数类型(fibVec在这个测试中已经溢出),你就会陷入创建一个可变数组IO或ST启用必要的严格性.