Erlang实战：并行枚举排序

IT闲人

<div id="cnblogs_post_body">　　这是海量数据的时代！互联网每天产生的数据量远远超出了我们所能想象的范围，无论是国外的Facebook、Twitter,还是国内的微博、人人，还有各种电商们，这些互联网企业在数据上是富有的，它们掌握着海量的用户数据，同时它们也需要对这些海量数据进行分析和处理。我们以前的串行化算法似乎显得力不从心，一个是计算机本身就设计为多核的，它们存在并行化问题；另一方面，更多的计算机加入到并行的行列，并行化正成为一种潮流和趋势，因为它们能用空间换取时间和性能，或者说用更多的机器来进行分析计算。
　　我知道的常用的并行计算工具大致有三种：MapReduce、MPI，还有就是本文讨论的Erlang。MapReduce最早是google设计并实施的，现在已经成为云计算中的一个火热的技术，它通过一个映射（Map)和规约（Reduce）来进行并行数据处理，实际上它是一个实时批处理再加上一些容错处理机制来保证系统的性能和可靠性；MPI我不太熟悉，它是一个库，不是一门语言，一般与C/FORTRAN结合使用；Erlang是一个基于消息传递的并发编程语言，正因为它是基于消息的，因此没有共享内存和锁机制，因此Erlang比较简单，它是函数型编程语言，我们在编写程序时写的都是函数。
　　下面我将通过一个排序实例：枚举排序来讲述Erlang并行编程！
　　实战：并行枚举排序
　　我们先来看看其概念：枚举排序也叫秩排序（Rank Sort），该算法的基本思想是：对每一个要排序的元素统计小于它的所有元素的个数，从而得到该元素在整个序列中的位置。其时间复杂度为o(n^2)。枚举排序串行算法伪代码如下：
<div class="cnblogs_code" >View Code <div id="cnblogs_code_open_418bf0a3-c9be-4bc0-94e5-0a3425eb9fde" class="cnblogs_code_hide"> 1 输入为：a[1], a[2] , ... , a[n] 2 3 输出为：b[1], b[2] , ..., b[n] 4 5 for i =1 to n do 6 7     1)k =1 8 9     2)for j = 1 to n do10 11           if a > a[j] then12 13              k= k + 114 15          endif16 17       endfor18 19       3)b[k] = a20 21 endfor