5

関数型コードは非関数型コードよりも本質的に並列化が容易であると常に耳にするので、次のことを行う関数を作成することにしました。

文字列の入力が与えられた場合、各文字列の一意の文字の数を合計します。したがって、入力が与えられると[ "aaaaa"; "bbb"; "ccccccc"; "abbbc" ]、メソッドはを返します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の各文字列は独自のスレッドで処理できるため、このコードは理想的には並列化可能です。インナーループはすべての入力間で共有されるマップにアイテムを追加するため、見た目ほど簡単ではありません。

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

4

4 に答える 4

3

次のように記述できます。

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

通常のモジュールの代わりに DLLPSeqからのモジュールを使用するために、2 つの余分な文字だけで並列化します。FSharp.PowerPack.Parallel.SeqSeq

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

たとえば、5.5Mb の欽定訳聖書から周波数を計算するのにかかる時間は、4.75 秒から 0.66 秒に短縮されます。これは、この 8 コア マシンで 7.2 倍のスピードアップです。

于 2010-02-13T07:18:13.937 に答える
2

すでに指摘したように、異なるスレッドに異なる入力文字列を処理させようとすると、更新の競合が発生します。これは、各スレッドがすべての文字のカウントをインクリメントできるためです。各スレッドに独自のマップを生成させてから「すべてのマップを追加」することもできますが、その最終ステップはコストがかかる可能性があります (データが共有されるため、スレッドの利用にはあまり適していません)。大規模な入力は、次のようなアルゴリズムを使用してより高速に実行される可能性が高いと思います。各スレッドは、(入力内のすべての文字列に対して) 異なる文字カウントを処理します。その結果、各スレッドには独自の独立したカウンターがあるため、更新の競合や結果を結合する最終ステップはありません。ただし、「一意の文字のセット」を発見するには前処理が必要であり、このステップにも同じ競合の問題があります。（実際には、

#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

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

于 2009-01-05T19:40:09.747 に答える
1

Don Syme が説明しているように、Parallel は async と同じではありません。

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

于 2009-01-14T04:36:12.913 に答える
0

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

n = card（Σ）をアルファベットΣの記号数σとします 。

マップステージ：

n個のプロセスを生成します。ここで、 i番目のプロセスの割り当ては、入力ベクトル全体でのシンボルσiの出現数を集計することです。

ステージを減らす：

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

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

于 2009-01-05T04:29:13.597 に答える