- 浏览: 69893 次
- 性别:
- 来自: 常州
文章分类
最新评论
-
yx1989:
不错,讲解得很清楚
Scanner的用法误区 -
lijunjie337:
你这是DES还是3DES啊??
JAVA中3des加密算法 -
啸笑天:
...
关键字 过滤算法 -
javamvp:
看看
策略设计模式 -
bianku:
...
成为Java高手的25个学习要点
今天早晨看到 蛙蛙池塘 的这篇博客 谁能把这个程序的性能提升一倍?---并行排序算法 。促使我写了一个并行排序算法,这个排序算法充分利用多核CPU进行并行计算,从而提高排序的效率。 先简单说一下蛙蛙池塘 给的A,B,C 三种算法(见上面引用的那篇博客),A算法将耗时的平方和开平方计算放到比较函数中,导致Array.Sort 时,每次亮亮比较都要执行平方和开平方计算,其平均算法复杂度为 O(nlog2n) 。 而B 将平方和开平方计算提取出来,算法复杂度降低到 O(n) ,这也就是为什么B比A效率要高很多的缘故。C 和 B 相比,将平方函数替换成了 x*x ,由于少了远程函数调用和Pow函数本身的开销,效率有提高了不少。我在C的基础上编写了D算法,D算法采用并行计算技术,在我的双核笔记本电脑上数据量比较大的情况下,其排序效率较C要提高30%左右。 下面重点介绍这个并行排序算法。算法思路其实很简单,就是将要排序的数组按照处理器数量等分成若干段,然后用和处理器数量等同的线程并行对各个小段进行排序,排序结束和,再在单一线程中对这若干个已经排序的小段进行归并排序,最后输出完整的排序结果。考虑到和.Net 2.0 兼容,我没有用微软提供的并行库,而是用多线程来实现。 下面是测试结果: n A B C D 32768 0.7345 0.04122 0.0216 0.0254 65535 1.5464 0.08863 0.05139 0.05149 131072 3.2706 0.1858 0.118 0.108 262144 6.8423 0.4056 0.29586 0.21849 524288 15.0342 0.9689 0.7318 0.4906 1048576 31.6312 1.9978 1.4646 1.074 2097152 66.9134 4.1763 3.0828 2.3095 从测试结果上看,当要排序的数组长度较短时,并行排序的效率甚至还没有不进行并行排序高,这主要是多线程的开销造成的。当数组长度增大到25万以上时,并行排序的优势开始体现出来,随着数组长度的增长,排序时间最后基本稳定在但线程排序时间的 74% 左右,其中并行排序的消耗大概在50%左右,归并排序的消耗在 14%左右。由此也可以推断,如果在4CPU的机器上,其排序时间最多可以减少到单线程的 14 + 25 = 39%。8 CPU 为 14 + 12.5 = 26.5% 目前这个算法在归并算法上可能还有提高的余地,如果哪位高手能够进一步提高这个算法,不妨贴出来一起交流交流。 下面分别给出并行排序和归并排序的代码: 并行排序类 ParallelSort Paralletsort 类是一个通用的泛型,调用起来非常简单,下面给一个简单的int型数组的排序示例: class IntComparer : IComparer < int > { IComparer Members #region IComparer<int> Members public int Compare( int x, int y) { return x.CompareTo(y); } #endregion } public void SortInt( int [] array) { Sort.ParallelSort < int > parallelSort = new Sort.ParallelSort < int > (); parallelSort.Sort(array, new IntComparer()); } 只要实现一个T类型两两比较的接口,然后调用ParallelSort 的 Sort 方法就可以了,是不是很简单? 下面是 ParallelSort类的代码 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; namespace Sort { /**/ /// <summary> /// ParallelSort /// </summary> /// <typeparam name="T"></typeparam> public class ParallelSort < T > { enum Status { Idle = 0 , Running = 1 , Finish = 2 , } class ParallelEntity { public Status Status; public T[] Array; public IComparer < T > Comparer; public ParallelEntity(Status status, T[] array, IComparer < T > comparer) { Status = status; Array = array; Comparer = comparer; } } private void ThreadProc(Object stateInfo) { ParallelEntity pe = stateInfo as ParallelEntity; lock (pe) { pe.Status = ParallelSort < T > .Status.Running; Array.Sort(pe.Array, pe.Comparer); pe.Status = ParallelSort < T > .Status.Finish; } } public void Sort(T[] array, IComparer < T > comparer) { // Calculate process count int processorCount = Environment.ProcessorCount; // If array.Length too short, do not use Parallel sort if (processorCount == 1 || array.Length < processorCount) { Array.Sort(array, comparer); return ; } // Split array ParallelEntity[] partArray = new ParallelEntity[processorCount]; int remain = array.Length; int partLen = array.Length / processorCount; // Copy data to splited array for ( int i = 0 ; i < processorCount; i ++ ) { if (i == processorCount - 1 ) { partArray[i] = new ParallelEntity(Status.Idle, new T[remain], comparer); } else { partArray[i] = new ParallelEntity(Status.Idle, new T[partLen], comparer); remain -= partLen; } Array.Copy(array, i * partLen, partArray[i].Array, 0 , partArray[i].Array.Length); } // Parallel sort for ( int i = 0 ; i < processorCount - 1 ; i ++ ) { ThreadPool.QueueUserWorkItem( new WaitCallback(ThreadProc), partArray[i]); } ThreadProc(partArray[processorCount - 1 ]); } private static void A(Vector[] vectors) { Array.Sort(vectors, new VectorComparer()); } private static void B(Vector[] vectors) { int n = vectors.Length; for ( int i = 0 ; i < n; i ++ ) { Vector c1 = vectors[i]; c1.T = Math.Sqrt(Math.Pow(c1.X, 2 ) + Math.Pow(c1.Y, 2 ) + Math.Pow(c1.Z, 2 ) + Math.Pow(c1.W, 2 )); } Array.Sort(vectors, new VectorComparer2()); } private static void C(Vector[] vectors) { int n = vectors.Length; for ( int i = 0 ; i < n; i ++ ) { Vector c1 = vectors[i]; c1.T = Math.Sqrt(c1.X * c1.X + c1.Y * c1.Y + c1.Z * c1.Z + c1.W * c1.W); } Array.Sort(vectors, new VectorComparer2()); } private static void D(Vector[] vectors) { int n = vectors.Length; for ( int i = 0 ; i < n; i ++ ) { Vector c1 = vectors[i]; c1.T = Math.Sqrt(c1.X * c1.X + c1.Y * c1.Y + c1.Z * c1.Z + c1.W * c1.W); } Sort.ParallelSort < Vector > parallelSort = new Sort.ParallelSort < Vector > (); parallelSort.Sort(vectors, new VectorComparer2()); } } } // Wait all threads finish for ( int i = 0 ; i < processorCount; i ++ ) { while ( true ) { lock (partArray[i]) { if (partArray[i].Status == ParallelSort < T > .Status.Finish) { break ; } } Thread.Sleep( 0 ); } } // Merge sort MergeSort < T > mergeSort = new MergeSort < T > (); List < T[] > source = new List < T[] > (processorCount); foreach (ParallelEntity pe in partArray) { source.Add(pe.Array); } mergeSort.Sort(array, source, comparer); } } } 多路归并排序类 MergeSort using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace Sort { /**/ /// <summary> /// MergeSort /// </summary> /// <typeparam name="T"></typeparam> public class MergeSort < T > { public void Sort(T[] destArray, List < T[] > source, IComparer < T > comparer) { // Merge Sort int [] mergePoint = new int [source.Count]; for ( int i = 0 ; i < source.Count; i ++ ) { mergePoint[i] = 0 ; } int index = 0 ; while (index < destArray.Length) { int min = - 1 ; for ( int i = 0 ; i < source.Count; i ++ ) { if (mergePoint[i] >= source[i].Length) { continue ; } if (min < 0 ) { min = i; } else { if (comparer.Compare(source[i][mergePoint[i]], source[min][mergePoint[min]]) < 0 ) { min = i; } } } if (min < 0 ) { continue ; } destArray[index ++ ] = source[min][mergePoint[min]]; mergePoint[min] ++ ; } } } } 主函数及测试代码 在蛙蛙池塘 代码基础上修改 using System; using System.Collections.Generic; using System.Diagnostics; namespace Vector4Test { public class Vector { public double W; public double X; public double Y; public double Z; public double T; } internal class VectorComparer : IComparer < Vector > { public int Compare(Vector c1, Vector c2) { if (c1 == null || c2 == null ) throw new ArgumentNullException( " Both objects must not be null " ); double x = Math.Sqrt(Math.Pow(c1.X, 2 ) + Math.Pow(c1.Y, 2 ) + Math.Pow(c1.Z, 2 ) + Math.Pow(c1.W, 2 )); double y = Math.Sqrt(Math.Pow(c2.X, 2 ) + Math.Pow(c2.Y, 2 ) + Math.Pow(c2.Z, 2 ) + Math.Pow(c2.W, 2 )); if (x > y) return 1 ; else if (x < y) return - 1 ; else return 0 ; } } internal class VectorComparer2 : IComparer < Vector > { public int Compare(Vector c1, Vector c2) { if (c1 == null || c2 == null ) throw new ArgumentNullException( " Both objects must not be null " ); if (c1.T > c2.T) return 1 ; else if (c1.T < c2.T) return - 1 ; else return 0 ; } } internal class Program { private static void Print(Vector[] vectors) { // foreach (Vector v in vectors) // { // Console.WriteLine(v.T); // } } private static void Main( string [] args) { Vector[] vectors = GetVectors(); Console.WriteLine( string .Format( " n = {0} " , vectors.Length)); Stopwatch watch1 = new Stopwatch(); watch1.Start(); A(vectors); watch1.Stop(); Console.WriteLine( " A sort time: " + watch1.Elapsed); Print(vectors); vectors = GetVectors(); watch1.Reset(); watch1.Start(); B(vectors); watch1.Stop(); Console.WriteLine( " B sort time: " + watch1.Elapsed); Print(vectors); vectors = GetVectors(); watch1.Reset(); watch1.Start(); C(vectors); watch1.Stop(); Console.WriteLine( " C sort time: " + watch1.Elapsed); Print(vectors); vectors = GetVectors(); watch1.Reset(); watch1.Start(); D(vectors); watch1.Stop(); Console.WriteLine( " D sort time: " + watch1.Elapsed); Print(vectors); Console.ReadKey(); } private static Vector[] GetVectors() { int n = 1 << 21 ; Vector[] vectors = new Vector[n]; Random random = new Random(); for ( int i = 0 ; i < n; i ++ ) { vectors[i] = new Vector(); vectors[i].X = random.NextDouble(); vectors[i].Y = random.NextDouble(); vectors[i].Z = random.NextDouble(); vectors[i].W = random.NextDouble(); } return vectors;
发表评论
-
矩阵求逆算法
2009-06-04 08:40 1738/** * 求矩阵A的逆矩阵Ai *@param A ... -
赫夫曼编码
2009-06-04 08:38 1246/* Name: 赫夫曼编码 Copyright: 始 ... -
关键字 过滤算法
2009-06-04 08:37 3715因为过滤关键字机制到处可见,于是聪明的网友就会想到各种各样的方 ... -
关键字过滤解决方案
2009-06-04 08:36 1590关键字过滤功能自然无比重要,但是如果要在代码中对每个输入进行检 ... -
多优先级队列调度算法
2009-06-04 08:33 2778一、多优先级队列调度 ... -
堆排序算法的实现
2009-06-04 08:31 715#include <stdio.h> void ... -
递推关系算法
2009-06-04 08:29 770题目描述: 斐波那契研究的兔子是每隔两个月开始成熟,现在我 ... -
插入排序算法
2009-06-04 08:28 771思想:将整个数组分成已排(左边)和待排(右边)两个部分,开始时 ... -
SIPC认证算法java实现
2009-06-04 08:23 1124SIPC的认证算法,支持SHA1和MD5。 i ... -
n个元素的全排列算法
2009-06-04 08:21 1108/* * 输出n个元素的全排列 */ #inc ... -
MethodTable内存空间分配中加法运算算法
2009-06-04 08:20 733在分析MethodTable具体分配内存实现的时候,看到了计算 ... -
lockfree 算法
2009-06-04 08:17 1054lockfree的本质是乐观锁。也就是说,它假设多数情况下,别 ... -
java中的冒泡算法
2009-06-04 08:15 791public class SortDemo { pub ... -
JAVA中3des加密算法
2009-06-04 08:14 2380package test; /* * 当前文件:T ... -
排列方法
2008-11-23 14:17 765排序有很多种方法,常用的有三种:冒泡排序、选择排序、插入排序 ...
相关推荐
4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现
快速排序的并行实现,提高效率。快速排序算法并行化的一个简单思想是,对每次划分过后所得到的两个序列分别使用两个处理器完成递归排序。
针对不同的排序算法,选择C语言来实现它们各自的源代码。
Verilog/C++实现排序算法:Verilog/C++实现排序算法:冒泡排序、选择排序、并行全比较排序、串行全比较排序。
多核处理器中一种改进的并行排序算法.pdf
LogGP Analysis of Parallel Sorting Algorithms 并行排序算法的LogGP分析.doc
java设计模式四大常用架构迭代模型并行排序算法.pdf
java设计模式_四大常用架构_迭代模型_并行排序算法
使用MPI计算的完整的PSRS(并行排序(parallel sorting by regular sampling))代码。并行计算课实验所用代码。
只需两个时钟即可输出12个数据的排序结果,内容简单易懂
利用MPI实现快速排序的并行算法,算法使用C语言实现
信息作为硕士论文的一部分,对C ++中实现的顺序排序算法与CUDA中实现的并行排序算法之间的比较进行了研究。 我们实现了七个算法:双音排序,多步双音排序,自适应双音排序,合并排序,快速排序,基数排序和样本排序...
介绍多种并行计算的算法,并行性性能分析 从模型,算法,编程多个角度具体讲解并行计算的实现
快速排序是一种最基本的排序算法。对于一个有序数组采取了取首位为基准的方法,快速排序的时间复杂度将会是(O (n^2)),这将会与冒泡排序无差别,针对其过程,对每次划分后的两个子区分别使用两个处理器完成递归...
4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现
4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的并行实现的流程图 8、完成快速排序的并行算法的实现
本文主要介绍了枚举排序、快速排序、PSRS排序算法以及它们的MPI编程实现。排序是数据处理中经常使用的一种重要运算,如何进行排序,特别是如何进行高效的排序,是计算机应用中的重要课题。排序的对象一般是一组记录...
包括了FPGA实现并行全排序的RTL代码和仿真文件,可以用于IP设计中的数值排序
基于FPGA的并行全比较排序算法.pdf