F#の並列ソートアルゴリズムは実装が簡単

F#の並列ソートアルゴリズムは実装が簡単

F# の並列ソート アルゴリズムで最も一般的な方法の 1 つは、まず処理するデータを複数の部分に分割し、次に異なるスレッド (CPU) で処理することです。すべてのスレッドが処理を完了すると、結果が集められ、独立したスレッドでマージされて最終結果が形成されます。分割する場合、各スレッドが独自の独立したデータのみにアクセスし、グローバル データや他のスレッドのデータ (ここでのデータは読み取り専用ではないデータを指します) にアクセスしないようにします。結果をマージする場合は、効率的なアルゴリズムを使用してマージする必要があります。

ソートアルゴリズムには、マージソートアルゴリズムがあります。まず、多方向マージソートアルゴリズムを記述し、ソートする配列をCPUの数に分割し、各CPUに各部分をソートさせ、すべてのスレッドがソートを完了したら、それらをまとめて独立したスレッドでマージソートを実行します。

もう一度コードを説明します。F# に馴染みのない方もいるかもしれません。

1. マージ アルゴリズムの考え方は、各スコア グループの最小の添字から始めて、複数のソート済み配列を 1 つの大きなソート済み配列にマージすることです。最小のものを大きな配列に入れ、次にこの配列の添字を 1 つ増やしてから再度比較し、最小のものを大きな配列に入れ、すべての小さな配列の添字が末尾を指すまでこれを繰り返します。一時変数 min が使用されるため、 mutable キーワードで変更されます。

2. F# 配列の長さは、Array.length メソッドを使用して取得されます。変数と配列の代入記号は、= ではなく <- です。= は C# の == に相当します。F# には、continue や break などのキーワードはありません。

3. async キーワードは新しい並列プリミティブです。これによって展開されたコードは、f# によってスレッド プール内で自動的に非同期実行されます。結果を返す場合は、let! キーワードと return! キーワードを使用する必要があります。ソートは配列に対してのみ実行され、何も返さないため、ここでは比較的単純です。

4. (fun ab -> a - b) はラムダ式であり、自動的にComparerに変換できます。 、ソートの基準となる

5. Array.map は、配列内の各要素にメソッドを適用することを意味します。この時点では実行されませんが、パイプラインを介して Async.Parallel メソッドに渡されます。Async.Parallel メソッドは、非同期実行配列 Async<'a array> を返し、最後に Async.Run を使用して、Async.Parallel によって返された結果を実際に実行します。

6. |> はパイプラインを意味し、前の関数の結果が次の関数で使用されることを意味します。このように、1 つのステートメントで非常に一貫したロジックを表現できます。

F# 並列ソート アルゴリズムの全体的なコードは次のとおりです。

 1 #ライト
2
3 オープンシステム
4 System.Diagnosticsを開く
5 Microsoft.FSharp.Control.CommonExtensions を開く
6
7 let merge_sort destArray ソース cmp =
8 N = Array.length ソースとする
9 L = Array.length destArray - 1 とします
10 posArr = Array.create N 0 とします
11 i = 0からLまで
12 変更可能な最小値を -1 にする
13 j = 0からN - 1まで
14 posArr.[j] >= Array.length source.[j] の場合 ()
15 その他
16 min = -1 の場合、min <- j
17 その他
18 (cmp source.[j].[posArr.[j]] source.[min].[posArr.[min]]) < 0 の場合、min <- j
19 min = -1 の場合 ()
その他20
21 destArray.[i] <- source.[min].[posArr.[min]]
22 位置[分] <- 位置[分] + 1
23
24 並列ソートをcmp arr =にする
25 プロセッサカウントを Environment.ProcessorCount とします。
26 partArray = Array.create プロセッサカウント [||]
27 可変長のまま = Array.length arr
28 partLen = Array.length arr / プロセッサカウント
29
30 i = 0 からprocessorCount - 1 まで
31 i = プロセッサカウント - 1 の場合
32 temp_arr = Array.create を 0 のままにする
33 Array.Copy(arr, i*partLen, temp_arr, 0, 残り)
34 部分配列.[i] <- temp_arr
35 その他
36 temp_arr = Array.create partLen 0 とする
37 Array.Copy(arr, i*partLen, temp_arr, 0, partLen)
38 残り <- 残り - partLen
39 部分配列.[i] <- temp_arr
40
41 let a_sort_one arr =
42 非同期 {
43 配列.sort cmp arr
44 }
45
46 a_sort_all = とします
47 部分配列
48 |> Array.map (fun f -> a_sort_one f)
49 |> 非同期並列
50 |> 非同期実行
51
52 すべて並べ替え
53 ret = Array.create (Array.length arr) 0 を実行します。
54 merge_sort ret partArray (fun ab -> a - b)
55 ret
56
57 arr = Array.create 1000000 0 とします
58 rnd = new Random() とします
59 i = 0 から Array.length arr - 1 まで
60 arr.[i] <- rnd.Next()
61
62 stop = Stopwatch.StartNew() を実行します。
63 停止、開始
64 sorted_arr = parallel_sort (fun ab -> ab) arr とします
65 停止。停止
66 printfn "並列ソート結果\r\n=%A\r\n所要時間 %d ミリ秒" sorted_arr stop.ElapsedMilliseconds
67
68 stop2 = Stopwatch.StartNew() とします
69 Array.sort (fun ab -> ab) arr
70 停止。停止
71 printfn "シリアルソート結果\r\n=%A\r\n所要時間 %d ミリ秒" arr stop2.ElapsedMilliseconds
72
73 コンソール.ReadKey(true)

私の IBM X200 では、シリアル ソートには約 1200 秒、パラレル ソートには約 900 秒かかります。

F# 並列ソートアルゴリズム関連リンク:

シンプルな F# 式から並行アプリケーションを構築する

マイクロソフト

Visual Studio 2010 に F# が正式に追加される

http://developer..com/art/200812/103775.htm

この記事は、 Prince Frogブログ記事「 Frog の推奨事項: F# が並列ソート アルゴリズムを実装」から引用したものです。

<<:  C# 暗号化アルゴリズムの簡単な紹介

>>:  C# モザイク アルゴリズムの実装

ブログ    
ブログ    
ブログ    
ブログ    

推薦する

...

NLP がヘルスケアにおける AI の価値を実現する方法

複雑な AI モデルを学習するには膨大な量のデータが必要であり、ヘルスケア データは全データのほぼ ...

IT プロフェッショナルが CIO に人工知能について知ってほしい 9 つのこと

[51CTO.com クイック翻訳] 最高情報責任者 (CIO) と IT リーダーは、人工知能の実...

隠れた表現を視覚化することでニューラルネットワークをより深く理解する

この記事では、隠し表現の視覚化を使用して、ニューラル ネットワークのトレーニング プロセスをより直感...

実践的 | この記事は畳み込みニューラルネットワークを始めるのに十分です

まず、ディープラーニングとはすべてのディープラーニングアルゴリズムの総称であり、CNNは画像処理分野...

SupFusion: 香港中文大学の最新の LV 融合による 3D 検出用新 SOTA!

この記事は、Heart of Autonomous Driving の公開アカウントから許可を得て転...

Tencent TRS: 産業実践におけるメタ学習とクロスドメイン推奨

1. メタ学習1. パーソナライズモデリングの問題点推奨シナリオでは、データの 80% 分布の問題に...

AI研究 | 陸宇:人工知能はオンライン教育を改善する大きな可能性を秘めている

工業情報化部科学技術庁は、感染予防・抑制に努め、感染拡大を阻止するために、「人工知能の力を十分に発揮...

「何千人もの人々の何千もの顔」を解読し、ユーザーのポートレートを深く解釈する方法

[[201075]]ユーザー ポートレートの概念は非常に人気があります。多くの企業が「ユーザー ポー...

企業が機械学習で犯す5つの間違い

機械学習技術の発展により、企業内のさまざまな構造化コンテンツや非構造化コンテンツから、より多くの情報...

AIデザイナー「ルバン」のコア技術が明らかに:1秒間に8,000枚のポスターをデザインする方法とは?

[[228895]] AI は囲碁のゲームを変え、今度はポスターのデザインを変えています。アリババ...

巨大企業間の今後の AI 戦争: マイクロソフトは左に進んで 2B、グーグルは右に進んで 2C

AI時代の到来非常にドラマチックなのは、Microsoft Build 開発者会議と Google...

...