3

Haskell に関するこのトピックでは多くのことが議論されましたが (例: mutable-array-implementation )、配列/ベクトルの頻繁な変更とランダム アクセスが必要な場合のベスト プラクティスが何であるかはまだわかりません。

長さ 1,000,000 のベクトルを考えてみましょう。それに対する操作には、入力に基づいてそのサブセット (小さい、たとえば 1000) にアクセスし、入力に基づいて値を変更することが含まれます。さらに、このような操作を２００万回繰り返す。タスク自体は、非常に非効率的ですが、たとえば次のようなリストなどの純粋なデータ構造で実装できます。

type Vect = [Int]

f :: Vect -> [[Int]] -> Vect
f x indsList = foldl g x indsList

-- g is just an example of random-access and modifications on the values.
g :: Vect -> [Int] -> Vect
g x inds = map h $ zip x [0..]
    where h (x, i) = if i `elem` inds then x !! i + 1 else x !! i

Hash/Map データ構造 (例: IntMap) は効率的な大量のランダム アクセスに使用できますが、配列/ベクトルも使用する必要があります。さらに重要なことに、大量の変更は、メモリの複製を回避するために可変構造によって対処する必要があります。実際、Haskellには変更可能なランダムアクセス配列/ベクトルがありますか? ST/IO モナドが使用されている場合、そのような制御は設定のパフォーマンスに影響しますか?

4

2 に答える 2

6

Haskell には効率的な可変配列があります。

  • STUArray非常に洗練されているが、多くの場合、多くの境界チェックと特別な最適化をほとんど行わないインデックスIx作成方法論があり、理論的に可能であるよりも少し遅くなります。

  • いずれData.Vectorもオーバーヘッドがほとんどなく、ストリーム フュージョンの最適化を多用し、シンプルな「リストのような」インターフェイスを好みます。つまり、サンプルを不変ベクトルに直接非常に簡単に転送でき、それでも予想よりも優れたパフォーマンスが得られる可能性があります。

    import Data.Vector.Unboxed as VU

type Vect = VU.Vector Int

f :: Vect -> [[Int]] -> Vect
f x indsList = VU.foldl g x indsList


g :: Vect -> [Int] -> Vect
g x inds = VU.zipWith h x [0..]
    -- h is just an example of modifications on the values.
    where h x i
           | i`elem`inds   = x VU.! i + 1
           | otherwise     = x VU.! i

STはい、変更可能な更新のためにモナドで作業したいでしょう。「そのようなコントロールはパフォーマンスに影響を与えますか」という意味がわかりません。コンパイラが実証済みの型安全性を最適化すると、命令型言語にも存在しない「コントロール」は実際にはありません。どのGHCが非常にうまく機能しますか? を使用すると、C のパフォーマンスにかなり近づけることができますData.Vector.Unboxed。避けられないオーバーヘッドは常にいくらかありますが、それは主にガベージ コレクションなどの問題に関係しており、Java でも発生します。

STとはモナドであるためIO、実際には、コンパイラーは命令型言語では不可能な、より高レベルの最適化を行うことができます。

パフォーマンス、特に配列操作のパフォーマンスについては、RWHなど、多くの場所で説明されています。

于 2013-07-26T22:57:43.467 に答える