코드에 병렬화에는 중첩된 루프

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

문제

당신은 항상 듣는 기능 코드가 본질적으로 쉽게 병렬화하지 않은 기능성 코드,그래서를 작성하기로 결정하는 기능의 기능은 다음과 같습니다.

주어진 input 의 문자열,최대 총 수의 독특한 캐릭터에 대한 각각의 문자열입니다.그래서 주어진 input [ "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 에서 처리할 수 있습 그것의 자신의 스레드가 있습니다.그럼 간단하지 않습 보인 이후 innerloop 항목을 추가 지도 사이에 공유되는 모든 입력이 있습니다.

나는 다음과 같 내부 루프를 모으로 자신의 스레드가 사용하고 싶지 않은 모든 변경 가능한 상태입니다. 내가 어떻게 다시 작성에 이 기능을 사용하여 비동기입니다.

도움이 되었습니까?

해결책

로 이미 지적,이 업데이트 경합을 시도하는 경우 다른 스레드 과정을 다른 입력 문자열을,이후 각 스레드가 증가시킬 수 있습 계산의 모든 문자입니다.할 수 있는 각 스레드의 생산 그것의 자신의 지도,다음에 추가'모든지도',그러나 그 마지막 단계는 비용이 있을 수 있습니다(지 않으로 잘 활용하는 스레드로 인해 공유된 데이터).내 생각에 큰 입력 가능성을 빠르게 실행하는 알고리즘을 사용하여 아래와 같은 각 스레드 프로세스를 다른 문자를 카운트(에 대한 모든 문자열을 입력).결과적으로,각 스레드가 자신의 독립적인 카운터,그래서 경쟁 업데이트 및 없는 마지막 단계는 결과를 결합합니다.그러나 우리가 필요한 전처리를 발견하는'세트의 독특한 문자',그리고 이 단계가 동일한 경쟁 문제입니다.(연습에서,아마 당신은 우주의 문 앞까지,예를 들어,alphabetics 수 있습니다 다음으로 만 26 쓰레드 프로세스 a-z,그리고 바이패스 이 문제를 해결합니다.) 어떤 경우에는,아마도 이 문제는 대부분에 대한 탐구'를 작성하는 방법 F#async 코드를 나누는 작업 스레드에서',그래서 코드는 아래 방법을 보여 줍니다.

#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

내가 참으로'완전히 변화 알고리즘'주로하기 때문에,내가 원래 알고리즘 당신은 특히 적합한 데이터 병렬화로 업데이트 contention.에 따라 정확하게 당신이 무엇을 배우는,이 대답지 않을 수도 있습 특별하게 만족스럽습니다.

다른 팁

를 작성할 수 있는 다음과 같다:

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

와 병렬화 그것은 두 개의 문자를 추가로 사용하는 PSeq 에서 모듈 FSharp.PowerPack.Parallel.Seq DLL 대신 평 Seq 모듈:

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

예를 들어,촬영 시간을 계산하는 주파수에서 5.5Mb 킹 제임스 성경에서 떨어지 4.75s0.66s.그것은 7.2×속도 향상에 이 8-중핵 기계입니다.

병렬 동일하지 않으로 비동기,로 지 Syme 설명.

그래서 IMO 당신이 더 나을 것을 사용하여 PLINQ 를 병렬화.

난 말하지 않 F#에서 모든지 내가 해결할 수 있다.를 사용하는 방법에 대해 생각 맵/감소:

자 n = 카드(Σ) 숫자의 기호 σ 에서 알파벳 Σ.

지도 단계:

스폰 n 프로세스의 할당 나번째 과정은 집계의 발생 횟수를 기호 σ나 에서 전체 입력 벡터입니다.

을 줄일 단계:

를 수집합해 각각의 n 프로세스에서 순서입니다.는 벡터가 귀하의 결과입니다.

지금 이 버전이 발생하지 않는 모든 개선을 통해 직렬 버전심이 숨어있는 종속기는 것이 본질적으로 하드 병렬화하지만 나는 너무 피곤하고 죽은 그것을 증명하다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top