4

この質問の続きです。unsafeFreezeベクトル ライブラリには融合可能な O(1) 更新関数がないようなので、 andを含まない融合可能な O(1) 更新関数を記述できないか考えていunsafeThawます。それはvector stream表現を使用すると思います-私は表現を使用して書く方法に慣れていませんstream-unstreamしたがって、この質問です。その理由は、これにより、ベクターの狭い領域のみが変更されるキャッシュに適した更新関数をベクターに書き込むことができるようになるためです。そのため、その狭い領域を処理するためだけにベクター全体をウォークスルーしたくありません (この操作は、各関数呼び出しで何十億回も発生する可能性があるため、オーバーヘッドを非常に低く保つ動機になります)。変換関数は次のようになりますmapベクトル全体を処理するため、処理が遅くなります。

私がやりたいことのおもちゃの例がありますが、upd以下の関数はunsafeThawandを使用していますunsafeFreeze- それはコアで最適化されていないようで、さらにバッファを使用しないという約束を破っています:

module Main where
import Data.Vector.Unboxed as U
import Data.Vector.Unboxed.Mutable as MU
import Control.Monad.ST

upd :: Vector Int -> Int -> Int -> Vector Int
upd v i x = runST $ do
          v' <- U.unsafeThaw v
          MU.write v' i x
          U.unsafeFreeze v'

sum :: Vector Int -> Int
sum = U.sum . (\x -> upd x 0 73) . (\x -> upd x 1 61)

main = print $ Main.sum $ U.fromList [1..3]

を使用して命令型アルゴリズムを実装する方法を知っていますSTVector。なぜこの代替アプローチが必要なのか疑問に思われている方のために、純粋なベクトルを使用GHCして特定のアルゴリズムの変換が、融合可能な純粋なベクトル ストリームを使用して記述された場合 (もちろんボンネットの下でモナド演算を使用して) を使用してどのように異なるかを確認するこのアプローチを試してみたいと思います。

を使用してアルゴリズムを作成するSTVectorと、私が望むほどうまく反復処理されないように見えます (多くの可変性が散らばっている場合、GHC オプティマイザがループを見つけるのは難しいと思います)。そのため、私はこの代替アプローチを調査して、より良いループを取得できることを確認しています。

4

2 に答える 2

3

どの関数も融合可能な更新関数です。ベクターパッケージがあなたに使用させようとしているプログラミングモデルから逃れようとしているようです

module Main where
import Data.Vector.Unboxed as U

change :: Int -> Int -> Int
change 0 n = 73
change 1 n = 61
change m n = n

myfun2 = U.sum . U.imap change .  U.enumFromStepN 1 1 
main = print $ myfun2 30000000

-- コアを調べればわかるように、これはベクトルを作成せず、ベクトルを「更新」しません。

于 2013-06-08T16:41:12.350 に答える