يوازي رمز في حلقات متداخلة

Question

كنت دائما أسمع أن رمز وظيفي بطبيعتها أسهل يوازي من غير وظيفية رمز, لذلك قررت أن أكتب وظيفة يفعل ما يلي:

إعطاء المدخلات من سلاسل, إجمالي عدد أحرف فريدة من نوعها لكل سلسلة.وذلك نظرا الإدخال [ "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

هذا الرمز هو مثالي parallelizable ، لأن كل سلسلة في input يمكن معالجتها في موضوع خاص بها.ليست بسيطة كما يبدو منذ innerloop يضيف بنود خارطة مشترك بين كل من المدخلات.

أود الحلقة الداخلية يؤخذ بها في موضوع خاص بها و لا تريد استخدام أي قابلة للتغيير الدولة. كيف يمكنني إعادة كتابة هذه الدالة باستخدام المتزامن سير العمل?

Answer 1

كما أشار بالفعل هناك تحديث الخلاف إذا كنت تحاول الحصول المواضيع المختلفة عملية الإدخال المختلفة سلاسل, لأن كل موضوع يمكن زيادة العدد من كل رسالة.هل يمكن أن يكون كل موضوع في إنتاج الخرائط الخاصة بها ، ومن ثم إضافة ما يصل جميع خرائط ، ولكن تلك الخطوة النهائية قد تكون مكلفة (و ليست مناسبة تماما إلى الاستفادة من المواضيع بسبب البيانات المشتركة).أعتقد كبيرة المدخلات من المرجح أن تعمل بشكل أسرع باستخدام خوارزمية مثل واحد أدناه ، حيث كل موضوع عمليات مختلفة الرسالة إلى عدد (لجميع السلاسل في المدخلات).ونتيجة لذلك, كل موضوع له دولته المستقلة العداد حتى لا تحديث الخلاف لا الخطوة الأخيرة إلى الجمع بين النتائج.ومع ذلك نحن بحاجة تجهيزها إلى اكتشاف مجموعة من رسائل فريدة من نوعها' ، و هذه الخطوة لا يكون نفس الخلاف المشكلة.(في الواقع, ربما كنت أعرف الكون من الشخصيات الجبهة مثلا ، alphabetics ، ومن ثم يمكن فقط يخلق 26 المواضيع العملية a-z, وتجاوز هذه المسألة.) في أي حال ، ويفترض السؤال هو الغالب حول استكشاف كيفية كتابة 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

أنا بالفعل 'تغير تماما خوارزمية', في الغالب لأنني الأصلي خوارزمية كان لديك لا سيما مناسبة لتوجيه البيانات الموازاة بسبب التحديث الخلاف.اعتمادا على بالضبط ما كنت تعلم أن هذا الجواب قد أو قد لا تكون مرضية لك.

Answer 2

يمكنك كتابة مثل هذا:

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.5 Mb الملك جيمس الكتاب المقدس يسقط من 4.75 s 0.66 s.هذا هو 7.2× تسريع على هذا 8-آلة الأساسية.

Answer 3

موازية ليس هو نفسه كما المتزامن ، لا يفسر سايم.

لذا المنظمة البحرية الدولية ستكون أفضل حالا باستخدام PLINQ إلى يوازي.

Answer 4

أنا لا أتكلم F# في كل شيء بشكل جيد, ولكن لا يمكن معالجة هذا.التفكير في استخدام الخريطة/الحد:

السماح n = بطاقة(ص) يكون عدد الرموز σ في الأبجدية Σ.

خريطة المرحلة:

تفرخ n العمليات ، حيث تعيين أنا-ال عملية رصيده إلى عدد من الحوادث من الرمز σ_أنا في كل ناقلات المدخلات.

والحد من المرحلة:

جمع الكلي لكل من n العمليات في النظام.أن ناقلات النتائج الخاصة بك.

الآن, هذا الإصدار لا يؤدي إلى أي تحسن على المسلسل الإصدار ؛ وأظن أن هناك يختبئ التبعية هنا أن يجعل هذا أصلا من الصعب يوازي ولكن أنا متعب جدا و الدماغ الميت لاثبات ذلك الليلة.