在Haskell非单片阵列 [英] Non-monolithic arrays in Haskell

问题描述

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

I have accepted an answer to the question below, but It seemed I misunderstood how Arrays in haskell worked. I thought they were just beefed up lists. Keep that in mind when reading the question below.

我发现，在Haskell的单片阵列使用它们更大的阵列时是非常低效的。

I've found that monolithic arrays in haskell are quite inefficient when using them for larger arrays.

我一直没能找到一个非单一的实现在Haskell阵列。我需要的是O（1）时间查找多维阵列上。

I haven't been able to find a non-monolithic implementation of arrays in haskell. What I need is O(1) time look up on a multidimensional array.

有支持此数组的实现？

编辑：我似乎误解了长期铁板一块。的问题是，它似乎在Haskell对待像列表的阵列的阵列等。我可能是错的。

I seem to have misunderstood the term monolithic. The problem is that it seems like the arrays in haskell treats an array like a list. I might be wrong though.

EDIT2：低效code的简单的例子：

Short example of inefficient code:

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个Fibonacci数。但是，由于在Haskell阵列具有O（n）时间的查找，它需要O（N²）的时间来计算。

this is an array of length n+1 where the i'th field holds the i'th fibonacci number. But since arrays in haskell has O(n) time lookup, it takes O(n²) time to compute.

推荐答案

数组有O（1）建立索引。的问题是，每个元件被懒惰地计算。因此，这是发生了什么，当你在ghci中运行以下命令：

Arrays have O(1) indexing. The problem is that each element is calculated lazily. So this is what happens when you run this in 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> 

注意，查找速度非常快，在它已经被抬起头来一次。在阵列函数创建一个指针数组最终将被计算能产生价值的thunk。您评估值的第一次，你付出这笔费用。以下是在thunk的前几个扩展评估的T ：

Note that lookup is very fast, after it's already been looked up once. The array function creates an array of pointers to thunks that will eventually be calculated to produce a value. The first time you evaluate a value, you pay this cost. Here are a first few expansions of the thunk for evaluating 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。

It's not the cost of the calculations per se that's expensive, rather it's the need to create and traverse this very large thunk.

我试图传递给阵列列表strictifying的值，但似乎导致死循环。

I tried strictifying the values in the list passed to array, but that seemed to result in an endless loop.

围绕这一点的一种常见的方法是使用一个可变的阵列，比如一个STArray。该元素可以作为它们的阵列创建期间是可用的更新，并且最终结果被冻结并返回。在矢量包，创建和 constructN 功能提供了简便的方法来做到这一点。

One common way around this is to use a mutable array, such as an STArray. The elements can be updated as they're available during the array creation, and the end result is frozen and returned. In the vector package, the create and constructN functions provide easy ways to do this.

-- 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)

BUT 的 fibVec 功能仅适用于未装箱的载体。定期向量（和数组）也不够严格，导致回你已经发现了同样的问题。不幸的是没有为整数一个无盒装实例，因此，如果您需要无限的整数类型（本 fibVec 已经在本次测试溢出）你坚持创造 IO 或 ST 一个可变的数组，使必要的严格性。

BUT, the fibVec function only works with unboxed vectors. Regular vectors (and arrays) aren't strict enough, leading back to the same problem you've already found. And unfortunately there isn't an Unboxed instance for Integer, so if you need unbounded integer types (this fibVec has already overflowed in this test) you're stuck with creating a mutable array in IO or ST to enable the necessary strictness.

这篇关于在Haskell非单片阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！