ネストされたループでコードを並列化する

StackOverflow https://stackoverflow.com/questions/412227

質問

機能コードは非機能コードよりも本質的に並列化が簡単であるといつも耳にするので、次の機能を実行することにしました。

文字列を入力すると、各文字列の一意の文字数が合計されます。したがって、入力 [＆quot; aaaaa＆quot ;; ＆quot; bbb＆quot ;; ＆cc; ccccccc＆quot ;; ＆quot; abbbc＆quot; ] 、このメソッドは a：6;を返します。 b：6; c：8 。

これは私が書いたものです：

(* seq<#seq<char>> -> Map<char,int> *)
let wordFrequency input =
    input
    |> Seq.fold (fun acc text ->
        (* This inner loop can be processed on its own thread *)
        text
        |> Seq.choose (fun char -> if Char.IsLetter char then Some(char) else None)
        |> Seq.fold (fun (acc : Map<_,_>) item ->
            match acc.TryFind(item) with
            | Some(count) -> acc.Add(item, count + 1)
            | None -> acc.Add(item, 1))
            acc
        ) Map.empty

input の各文字列は独自のスレッドで処理できるため、このコードは理想的には並列化可能です。 innerloopはすべての入力間で共有されるMapにアイテムを追加するため、見た目ほど簡単ではありません。

内側のループを独自のスレッドに分解したいので、可変状態を使用したくありません。 非同期ワークフローを使用してこの関数を書き直すにはどうすればよいですか

役に立ちましたか？

解決

すでに指摘したように、各スレッドはすべての文字のカウントをインクリメントできるため、異なるスレッドに異なる入力文字列を処理させようとすると、更新の競合が発生します。各スレッドに独自のマップを作成させてから、「すべてのマップを追加する」ことができますが、その最終ステップは高価になる可能性があります（共有データのためにスレッドを利用するにはあまり適していません）。以下のようなアルゴリズムを使用すると、大きな入力はより高速に実行される可能性が高いと思います。このアルゴリズムでは、各スレッドが異なる入力文字列を処理します。その結果、各スレッドには独自の独立したカウンターがあるため、更新の競合や結果を結合する最終ステップはありません。ただし、「一意の文字のセット」を検出するには前処理が必要であり、このステップには同じ競合の問題があります。 （実際には、おそらくアルファベットなどの文字の世界を知っているので、26個のスレッドを作成してazを処理し、この問題を回避できます。）いずれにせよ、問題は主に「F＃の書き方」スレッド間で作業を分割する非同期コード」であるため、以下のコードでそれを示します。

#light

let input = [| "aaaaa"; "bbb"; "ccccccc"; "abbbc" |]

// first discover all unique letters used
let Letters str = 
    str |> Seq.fold (fun set c -> Set.add c set) Set.empty 
let allLetters = 
    input |> Array.map (fun str -> 
        async { return Letters str })
    |> Async.Parallel 
    |> Async.Run     
    |> Set.union_all // note, this step is single-threaded, 
        // if input has many strings, can improve this

// Now count each letter on a separate thread
let CountLetter letter =
    let mutable count = 0
    for str in input do
        for c in str do
            if letter = c then
                count <- count + 1
    letter, count
let result = 
    allLetters |> Seq.map (fun c ->
        async { return CountLetter c })
    |> Async.Parallel 
    |> Async.Run

// print results
for letter,count in result do
    printfn "%c : %d" letter count

確かに「アルゴリズムを完全に変更しました」。これは主に、更新競合のために、元のアルゴリズムが直接データ並列化に適していないためです。正確に何を学びたいかに応じて、この答えは特に満足できる場合とそうでない場合があります。

他のヒント

このように書くことができます：

let wordFrequency =
  Seq.concat >> Seq.filter System.Char.IsLetter >> Seq.countBy id >> Map.ofSeq

さらに2文字だけで並列化し、通常の Seq FSharp.PowerPack.Parallel.Seq DLLの PSeq モジュールを使用しますcode>モジュール：

let wordFrequency =
  Seq.concat >> PSeq.filter System.Char.IsLetter >> PSeq.countBy id >> Map.ofSeq

たとえば、5.5Mbのキングジェームズ聖書の周波数を計算するのにかかる時間は、4.75秒から0.66秒に短縮されます。 7.2＆＃215;この8コアマシンの高速化。

Don Symeが説明します。

IMOでは、PLINQを使用して並列化する方が良いでしょう。

F＃はまったく話せませんが、これに対処できます。 map / reduceの使用を検討してください：

let n = card（＆＃931;）は記号の数＆＃963;アルファベットで＆＃931;。

マップステージ：

Spawn n プロセス。ここで i 番目のプロセスの割り当ては、シンボル＆＃963; iの出現回数を集計することです。 を入力ベクトル全体で。

ステージを削減：

各 n プロセスの合計を順番に収集します。そのベクトルはあなたの結果です。

現在、このバージョンではシリアルバージョンよりも改善されていません。ここに隠れている依存関係があり、これを本質的に並列化するのが難しくなっていると思いますが、今夜それを証明するには疲れすぎて頭が痛いです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top