2

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

我发现在将它们用于更大的数组时，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²) 时间来计算。

4

3 回答 3

8

您将 Haskell 中的链表与数组混淆了。

链表是使用以下语法的数据类型：

[1,2,3,5]

定义为：

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

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

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

  • Repa - 快速、并行、多维数组——（教程）
  • Vector - Int 索引数组（可变和不可变）的有效实现，具有强大的循环优化框架。（教程）
  • HMatrix - 基本线性代数和其他数值计算的纯功能接口，内部使用 GSL、BLAS 和 LAPACK 实现。
于 2012-04-19T11:55:11.670 回答
5

数组有 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函数创建一个指向 thunk 的指针数组，这些指针最终将被计算以产生一个值。第一次评估价值时，您需要支付此成本。以下是用于评估的 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启用必要的严格性。

于 2012-04-19T14:09:56.290 回答
1

具体参考您的fibArray示例，试试这个，看看它是否加快了速度：

-- gradually calculate m-th item in steps of k
--     to prevent STACK OVERFLOW , etc
gradualth m k arr                         
    | m <= v = pre `seq` arr!m   
  where                                   
    pre = foldl1 (\a b-> a `seq` arr!b) [u,u+k..m]
    (u,v) = bounds arr

对我来说，forlet a=fibArray 50000的gradualth 50000 10 a运行时间为 0.65 运行时间，只需a!50000立即调用。

于 2012-04-20T01:09:14.707 回答