ハスケルの非モノリシックアレイ

Question

私は以下の質問に対する答えを受け入れましたが、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) 

これはi番目のフィールドは、i番目のフィボナッチ数を保持する長さn+1の配列です。しかし、haskellの配列にはO（n）時間のルックアップがあるため、計算にはO（n²）時間がかかります。

Answer 1

アレイには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などの可変配列を使用することです。配列の作成中に使用可能になると要素を更新し、最終結果をフリーズして戻すことができます。ベクターパッケージでは、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機能は、箱なしのベクトルで動作します。規則的なベクトル（および配列）は厳密ではないので、あなたがすでに見つけたのと同じ問題に戻る。残念ながら、IntegerのUnboxedインスタンスはありません。無制限の整数型が必要な場合（このテストではすでにfibVecがオーバーフローしています）、可変配列をIOまたはSTに作成して、必要な厳密性を有効にしています。あなたのfibArray例を特に参照

Answer 2

あなたはHaskellのリンクリストを配列と混同しています。

[1,2,3,5] 

のように定義：

リンクされたリストは、次の構文を使用するデータ・タイプである

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

これらは、O（n）のインデックスとO（1を支持する古典的な再帰的なデータ・タイプであります）prepend。

O（1）ルックアップを使用して多次元データを検索する場合は、真の配列または行列データ構造を使用する必要があります。良好な候補である：

• Repa - 高速、平行、多次元配列 - （Tutorial）
• Vector - （可変及び不変の両方）のIntインデックス配列の効率的な実施、強力なループ最適化フレームワークを有します。 （Tutorial）
• HMatrix - GSL、BLAS、およびLAPACKを使用して内部的に実装された基本線形代数と他の数値計算に対する純粋に機能的なインターフェース。

Answer 3

、これを試してみて、それは少し物事をスピードアップしている場合を参照してください。私にとって

-- 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はちょうどすぐにa!50000を呼び出すの0.65実行時に走りました。