F#并行排序算法轻松实现

F#并行排序算法中其中有一种比较常见的方法就是先把要处理的数据分成若干份，然后让不同的线程（CPU）去处理，然后所有的线程处理完成后，把结果汇聚在一起，在一个独立的线程里完成结果合并，从而形成最终结果。在做分割的时候尽量让每个线程只访问自己独立的数据，而不访问全局数据和其它线程的数据（这里说的数据是非只读数据），在合并结果的时候要有一种高效的算法来合并。

排序算法里有归并排序算法，我们先写一个多路归并排序算法，然后把要排序的数组分成CPU的个数份，让每个CPU去对每一份进行排序，所有线程排序完成后汇聚在一起，在一个独立的线程里进行归并排序。

大概再解释一下代码，可能有些人对F#还不熟悉。

1、归并算法的思路就是把多个已经排序的数组合并成一个大的排序数组，先从每个分数组的最小下标开始，谁都最小就放到大数组里，然后这个数组的下标加一，然后再比较，再把最小的放到大数组里，重复，直到所有的小数组的下标已经指向到末尾。其中会用到一个临时变量min，所以用mutable关键字修饰。

2、F#的数组的长度用Array.length方法得出，变量和数组的赋值符号是<-,而不是=，=相当于c#里的==，f#里没有continue和break等关键字

3、async关键字是一个新的并行基元，用它扩住的代码由f#自动的异步在线程池里执行，如果里面要返回结果的话，要用let!和return!关键字，我们的排序只是对数组进行操作，并不返回，所以这里比较简单。

4、(fun a b -> a - b)是一个lamda表达式，它可以自动转换成Comparer，起到排序依据的作用

5、Array.map表示把一个数组里的每个元素应用一个方法，它这时候不执行，会通过管道传递给Async.Parallel方法，Async.Parallel方法返回一个异步执行数组Async<'a array>，最后用Async.Run来真正执行Async.Parallel返回的结果。

6、|>表示管道的意思，大致就是把前一个函数的结果让后一个函数来用，这样一条语句可以表达很连贯的逻辑。

F#并行排序算法整体代码如下：

我本机，IBM X200测试串行排序大约在1200多秒，并行排序在900秒左右。

F#并行排序算法相关链接：

从简单的F# 表达式构建并发应用程序

http://msdn.microsoft.com/zh-cn/magazine/cc967279.aspx

Visual Studio 2010将正式包含F#