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-高速、並列、多次元配列-（チュートリアル）
  • ベクター-強力なループ最適化フレームワークを使用した、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関数は、サンクへのポインターの配列を作成します。この配列は、最終的に計算されて値を生成します。初めて値を評価するときに、このコストを支払います。これが評価のためのサンクの最初のいくつかの拡張です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)

高価なのは計算自体のコストではなく、この非常に大きなサンクを作成してトラバースする必要があります。

に渡されたリストの値を厳密化しようとしましたarrayが、無限ループが発生したようです。

これを回避する一般的な方法の1つは、STArrayなどの可変配列を使用することです。要素は、配列の作成中に利用可能になったときに更新でき、最終結果は凍結されて返されます。ベクトルパッケージでは、createandconstructN関数はこれを行う簡単な方法を提供します。

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

私にとって、はlet a=fibArray 50000、gradualth 50000 10 aすぐに呼び出すだけの0.65実行時間で実行されましa!50000た。

于 2012-04-20T01:09:14.707 に答える