問題

フォルダーを調べて、フォルダー内の各画像の平均色を見つける Haskell プログラムを作成しました。hackage の repa-devil パッケージを使用して、画像を repa 配列に読み込みます。赤、青、緑のすべての値を加算し、ピクセル数で割って平均を求めます。

このプログラムも、Python イメージ ライブラリを使用して Python で作成しました。同じ方法で画像の平均を見つけます。

これらの両方を 301 個のイメージを含むフォルダーで実行すると、Haskell バージョンは 0.2 秒 (0.87 対 0.64) 優れています。Haskell はコンパイル済み言語 (インタープリター型言語よりも高速であることが多い) であり、repa 配列のパフォーマンスが優れていると聞いていたため、これは奇妙に思えます (ただし、これはリストなどの他の Haskell データ型と比較しただけかもしれません)。

私が試したこと

私が最初にしたことは、明示的な再帰を使用していることに気づいたので、折り畳みを使用して置き換えることにしました。これは、配列の境界を超えているかどうかを確認する必要がなくなったことも意味します。

これにより実行速度が遅くなった (1.2 秒) ため、コードをプロファイリングして、ほとんどの時間が費やされている場所を確認することにしました (明らかなボトルネックが発生した場合や、repa-devil パッケージが単に遅い場合に備えて)。プロファイルによると、時間の約 58% が f 関数に費やされ、時間の約 35% が addCol に費やされました。

残念ながら、これをより速く実行する方法は考えられません。関数は単なる配列インデックスと加算です - Python コードと同じです。このコードのパフォーマンスを改善する方法はありますか、それとも Python イメージ ライブラリはパフォーマンスを向上させるだけですか?

Repa を見始めたばかりで、ステンシル操作によって読み取り/書き込みされるラップアラウンド、トーラス スタイルの 2D 配列を最適に実装する方法を知りたいと考えています。ST モナドとミュータブル ベクトルを使用する前にこれを実装しましたが、これは Repa ではサポートされていないようです。いくつかのアプローチが可能と思われます:

• 配列を「トラバース」して、各要素で自分自身をラップするインデックスを実行できます。単純なステンシルの場合、どこにでもラッピング ロジックを適用するコストは非常に厳しいため、これは避ける必要があります。

• Data.Array.Repa.Stencil は必要な境界条件をサポートしていませんが、Data.Array.Repa.Algorithms.Convolve のように見えます。ドキュメンテーションは、パフォーマンスが大幅に低下することを示唆していますが、

• 私が理解していることから、スライスを使用して配列のサブセットをトラバースできます。したがって、内部 (1, 1) - (w-2, h-2)、境界を表す 2 つの水平スラブと 2 つの垂直スラブを定義し、2 つの異なる関数/ステンシルを使用してそれらをトラバースし、結果として 1 つの配列を得ることができます。 ? これに関するサンプルコードまたはその他のドキュメントはありますか?

• Repaにも「パーティション」という概念があるようですが、境界条件の実装に使用できますか?

どれが最速である可能性が高いですか? 不足しているオプションはありますか？

ありがとう！

合計で約 1,700 万行を含む少数の ASCII ファイルがあり、各行またはほとんどの行に 36 バイトの固定識別子があります。したがって、私のデータは長方形です。固定幅の行がたくさんあります。Haskell を使用して、すべての行を読み取り、正規表現を使用して識別子を抽出し (そこまでは問題ありません)、それらを並べ替えて一意の識別子の数をカウントします (に非常に近いgrep | sort | uniq)。（各ファイルから並列に読み取ることで、すでに並列化しています。）単純な問題のように聞こえますが...

ソート段階の前であっても、この問題からまともなパフォーマンスを引き出すのは難しいと思います。これが私が持っている限りです。 String36 バイトの ASCII ではやり過ぎなので、ByteString. しかし、サイズが 1700 万の (リンクされた) リストは悪い考えのように思えるので、試してみIOVector ByteStringました。しかし、これはかなり遅いようです。ベクトルに何百万もの小さな ByteString を保持しているため、ガベージ コレクションに問題がある+RTS -sと思います。

Repa またはある種の単一の巨大なByteString/ IOVector Char8/whatever を使用して (各行の正確な幅が 36 であることを知っているため)、スレッドごとに 1 つの巨大な長方形配列にデータを格納する必要があると考えていました。これにより、GC の問題が軽減されます。 . ただし、後で行を並べ替える必要はあります。Repa は並べ替えをサポートしていないようで、自分で並べ替えアルゴリズムを作成したくありません。そのため、巨大な長方形の配列を持ちながら、それを並べ替える方法がわかりません。

使用するライブラリ、設定する GC フラグ、またはその他の提案はありますか? マシンには 24 個のコアと 24 GB の RAM があるため、ハードウェアの制約はありません。Haskell に残りたいのは、問題なく動作している関連コード (同じファイルを解析し、要約統計を生成している) がたくさんあり、それを書き直したくはないからです。

Repa Array を使用して、Haskell で 3 フェーズ ストラクチャード ライト スキャンのフェーズ アンラッピング アルゴリズムを実装しようとしています。ポイント（幅/ 2、高さ/ 2）から外側に再帰するフラッドフィルベースのアンラップアルゴリズムを実装したいと考えています。残念ながら、その再帰方法を使用すると、メモリ不足の例外が発生します。私は Haskell と Repa ライブラリを初めて使用するので、明らかに間違ったことをしているように見えるかどうか疑問に思っていました。これについて何か助けていただければ幸いです。

更新 (@leventov):

Yarr で変更可能な配列を使用して、次のパス フォローイング アルゴリズムを実装することを検討しています。(出版物: K. Chen、J. Xi、Y. Yu & JF Chicharo、「Fast quality-guided flood-fill phase unwrapping algorithm for threedimensional fringe pattern profilometry」、産業用アプリケーションの光学計測と検査、2010 年、pp. 1 -9.)

問題

Repaがどのように機能するかを理解しようとしていますが、 Repa Examplesパッケージの「ぼかし」サンプル コードを使用していました。コードは次を使用しますstencil2 Quasi Quote。

これは単なるTemplateHaskellスニペットで、関数を生成します:

TH を使用しても問題ありませんが、coefs を Repa Array に保持したいので、代わりに Repa Array を使用するようにコードを変更しましたが、私のコードは元のコードに比べて 2 倍遅く動作します。

いくつかの派手なメモ

Repa の作成者はハードコーディングされた 7 行 7 列の値の行列を使用して係数を取得していることに気付きました: http://hackage.haskell.org/package/repa-3.2.3.3/docs/src/Data-Array-Repa-Stencil- Dim2.html#forStencil2 (参照: template7x7)

質問

1. なぜ元のように最適化されていないのか、どうすれば修正できるのかお聞きしたいです。イメージに対してステンシル (Repa 配列) の畳み込みを実行できるようにする「畳み込み」関数を作成したいと考えています。
2. GHCにコードを最適化させるために、そのようなハードコードされた行列を本当に使わなければならないのでしょうか? そのような「ハック」を使わずに高速な Haskell コードを作成する方法は本当にありませんか?

コード

オリジナルぼかし機能：

私のぼかし機能:

コードの残りの部分:

コンパイル:ghc -O2 -threaded -fllvm -fforce-recomp Main.hs -ddump-splices

多数のプログラミング例を試すことで、Haskell repa ライブラリを調査しています。repa を使用して一般的な画像処理アルゴリズムを実装することを目指しています。

レパの例

repa リポジトリには、役立つコード例がいくつかあります。これらはすべてArray U DIM2 aorArray DIM2 Floatまたはタイプの画像を操作しますArray U DIM2 Double。

画像ファイル IO

イメージ ファイル IO には 2 つのオプションがあります。

1. PNG、BMP、JPG、TIF をサポートするrepa-devilパッケージ。残念ながら、これらは上記の repa の例に準拠しない配列型に解析されます。これは、repa-devil メンテナーがここで確認しています。
2. repa-ioパッケージは、 repa-examplesの画像の配列型パラメーターにより厳密に対応しますが、BMP ファイルのみをサポートします。

repa-devil (repa-examples とは互換性がありません)

repa-examples パッケージの画像のタイプArray F DIM3 Word8は 、またはArray F DIM2 Word8グレースケール画像の場合です。これは、repa-examples のイメージは 2 次元配列であり、repa-devil のイメージは 3 次元配列であるため、repa-devil を使用して repa-examples の例で処理するイメージを読み取ることができないことを意味します。

repa-io (repa-examples との互換性あり)

repa-examples と repa-io の間には、より密接な対応があります。

今回は、BMP 画像ファイルは(Word8,Word8,Word8)、おそらく R、G、および B の値を表すために、タイプ の要素を持つ 2 次元配列に解析されています。それでも、repa-examples パッケージの唯一の互換性のある関数はtoGreyScale上記のものです。他のすべての関数は、Array U DIM2 FloatorArray DIM2 Floatまたは型の値を操作しますArray U DIM2 Double。

質問

1. を除いてtoGreyScale、repa-examples のすべての例はグレースケール画像での使用にのみ適していますか? これは型を見ると理にかなっていますが、カラー画像のレパの例がないことは驚くべきことです。たとえば、blurnot の型が代わりにある理由は次のとおりです。 blur :: Monad m => Int -> Array U DIM2 (Word8, Word8, Word8) -> m (Array U DIM2 (Word8, Word8, Word8))
2. float が でキャプチャする値はArray U DIM2 Float? 0 から 255 までのグレースケール値ですか?
3. repa-io パッケージに JPG/PNG/TIF IO サポートを追加する作業はありましたか?

問題

既に存在する可能性のある repa ライブラリ内の関数を探しています。次のような関数が必要です。

1. 2D 配列を取ります
2. ウィンドウ サイズを指定する 2 つの整数
3. 2D 配列の指定されたサイズの各ウィンドウで、新しい値 (この特定のウィンドウの小さな値など) を計算します。

例

min3x3 ウィンドウで関数をマッピング:

戻ります:

のBoundClamp  コンストラクターに似たスキームを使用していることに注意してくださいData.Array.Repa.Stencil。これはステンシル畳み込みではありません。つまり、2D 配列のすべての要素にステンシルを適用しているわけではありません。代わりに、配列の各ウィンドウで関数を実行し、エッジの範囲外の要素には 2D 配列のエッジで最も近い値が割り当てられます。

可能な解決策の種類

関数は次のようになります。

これはすでに存在するものですか、それともコード化するのは簡単ですか?