3

1 つの大きな配列で大規模な更新を行うプログラムを作成しようとしていますが、評価は数回しかありません。計算をできるだけ怠惰にしたいのですが、どの配列表現が私の場合に適しているかわかりません。具体的には、アレイに次のことを行います。

  • サイズが固定されている
  • 一定時間アクセス
  • O(n) の n 要素を更新する
  • 遅延評価

これらの要件にどのようにアプローチしますか? サブ質問として: このユースケースに特化したライブラリはありますか?

編集：

私の質問が具体的ではなかったかもしれないので、私のケースについてもっと説明しようと思います。

比較的小さい（約1200x800）か、それよりもはるかに大きい（少なくとも8000x8000）さまざまなサイズの画像を表現しようとしています。また、1 つの画像に対して多数のレイヤーが存在するため、画面上に画像を描画したい場合、フレーム バッファー画像が多数更新されることになります。Haskell の遅延評価の性質を利用できれば、更新のたびに同じピクセルを上書きするのではなく、フレーム バッファーに 1 回だけ書き込むことができると考えました。

Haskell で配列を表現するためのいくつかのオプションを認識していますが、それらのすべてが私の場合には適合しないようです。例えば：

  • Data.Seq、Data.IntTrie : 一定時間アクセスできない
  • Data.Vector、Data.Array : n 要素の更新には O(n) よりも時間がかかります
  • ボックス化されていないバリアント : 遅延評価されていません (推測しますか?)

この場合、どのようなアプローチをとればよいでしょうか。

4

1 に答える 1

4

考慮すべき 1 つのライブラリはrepa. の重要なアイデアの 1 つはrepa、Array型がその基礎となる表現でパラメーター化されるということです。これらのサンプルは

  • D「実在しない」配列の遅延表現- 必要に応じて要素を計算するだけです。
  • Uボックス化されていないデータのボックス化されていないベクトル表現
  • ボックス化されたデータのボックス化されたベクトル表現(データのインスタンスをV作成できない場合にのみ使用)Unbox
  • 外部バッファへの参照。F外部ビットマップ グラフィックス バッファに書き込みたい場合に特に便利です。

コードをコンパイルすると、遅延した配列は最適化されなくなります。O(1)ボックス化されていない配列にアクセスできることは言うまでもありません。あなたの場合、おそらく形状のDIM2配列（2D配列）を使用するだけです。

デモンストレーションの目的で、目的と同様のことを行うプログラムを次に示します。これは、ビットマップ レイヤーとそのオフセット、および背景ビットマップのリストを取り込みます。次に、これらのレイヤーをビットマップ背景の上に描画します。画像を配列repa-ioにロードするために依存します。repa

import Data.Array.Repa.IO.BMP
import Data.Array.Repa.Shape
import Data.Array.Repa
import Data.Word

-- This is our internal representation of a bitmap
type Image s = Array s DIM2 (Word8, Word8, Word8)
data Layer s = Layer { image :: Image s, offset :: (Int, Int) }

drawLayersOnBg :: Image U -> [Layer U] -> Image D
drawLayersOnBg background layers = foldl (\bg (Layer im (x,y)) -> overlay bg (ix2 y x) im) (delay background) layers
  where
    overlay :: Image D -> DIM2 -> Image U -> Image D
    overlay bg off ov = backpermuteDft bg
                                       (\i -> let i' = i `subDim` off
                                                 in if extent ov `inShape` I'
                                                      then Just i'
                                                      else Nothing)
                                       ov

    subDim :: DIM2 -> DIM2 -> DIM2
    subDim (Z :. y :. x) (Z :. dy :. dx) = ix2 (y - dy) (x - dx)

main = do
  Right bg <- readImageFromBMP "background.bmp"
  Right l1 <- readImageFromBMP "layer1.bmp"
  Right l2 <- readImageFromBMP "layer2.bmp"
  Right l3 <- readImageFromBMP "layer3.bmp"

  out <- computeP $ drawLayersOnBg bg [ Layer l1 (200,100) , Layer l2 (100, 200), Layer l3 (-300,400) ]
  writeImageToBMP "out.bmp" out

インターネットからのランダムなビットマップを使用して、これを出力として取得しました。

出力

必要に応じて、ビットマップ出力を外部メモリ バッファに直接書き込む代わりに、fromForeignPtr外部メモリ バッファから直接ビットマップを読み取ることもできます (中間割り当てなし)。高性能が必要な場合、それらは特に興味深いものです。computeIntoPcomputeP

于 2016-12-04T09:24:04.423 に答える