4

のコレクション (簡単にするために、それらをリストと呼びます) を含むデータ構造に対するこの順次手順を考えてみましょうDoubles。私が好きな限り、次のことを行ってください。

  1. 構造から 2 つの異なるリストをランダムに選択する
  2. それらのリストに基づいて統計を計算する
  3. その統計に基づいてコインを投げる
  4. コイントスの結果に基づいて、リストの1つを変更する可能性があります

目標は最終的に何かへの収束を達成することであるため、「解決策」は反復回数に比例します。この手順の実装は SO の質問hereで見ることができ、直感的な視覚化は次のとおりです。

シーケンシャル ビス

この手順は、別の OS スレッドで同時に実行する複数のワーカーを使用することで、より適切に実行できるようです。つまり、収束をより速く達成できます。例:

同時進行

これを完全に実現した実装は、利用可能なコンピューティング リソースの数をPとすると、 O(n/P)時間で解決策を達成できるはずです。

Haskell の同時実行性について調べてみるとMVar、TVar、TChan、 、 などの用語で頭がぐるぐるしてきました。明らかなことは、この手順の同時実行は、上でリンクしたものとはacid-state大きく異なるように見えるということです。しかし、手順自体は、本質的にメモリ内データベースであるもののかなり飼いならされたアルゴリズムのように見えます。これは、誰かが以前に遭遇したと確信している問題です。

私は、まともなランダムアクセス（つまり、ランダムなアイドル要素へのアクセス）と変更をサポートする、ある種の変更可能な同時データ構造を使用する必要があると思います。パフォーマンスを向上させるために必要となる可能性のあるすべてのものをつなぎ合わせようとすると、少し迷ってしまいます (たとえば、STM は疑わしいようです)。

シーケンシャルな実装よりもパフォーマンスを向上させることが目標である場合、この種のタスクに適したデータ構造、同時実行の概念などは何ですか?

4

1 に答える 1

4

複雑にしないでおく：

  • 軽量で超安価なスレッド用のforkIO 。
  • MVar、高速でスレッドセーフな共有メモリ用。
  • および適切なシーケンスタイプ (おそらくvector、前に追加するだけの場合はリスト)
  • 良い統計パッケージ
  • 高速な乱数ソース ( mersenne -random-pure64 など)

後でより凝ったものを試すことができます。生のパフォーマンスを得るには、まず物事をシンプルに保ちます。ロックの数を抑えます (たとえば、バッファーごとに 1 つ)。必ずコードをコンパイルし、スレッド化されたランタイム ( ghc -O2) を使用してください。そうすれば、すばらしいスタートを切れるはずです。

RWH には、並行 Haskellの基本をカバーする導入章があります。

于 2012-05-16T23:16:07.447 に答える