2011年軟考軟件設(shè)計(jì)師知識(shí)點(diǎn)：并行排序算法

　　先簡(jiǎn)單說(shuō)一下給的A，B，C 三種算法(見(jiàn)上面引用的那篇博客)，A算法將耗時(shí)的平方和開(kāi)平方計(jì)算放到比較函數(shù)中，導(dǎo)致Array.Sort 時(shí)，每次亮亮比較都要執(zhí)行平方和開(kāi)平方計(jì)算，其平均算法復(fù)雜度為 O(nlog2n) 。 而B 將平方和開(kāi)平方計(jì)算提取出來(lái)，算法復(fù)雜度降低到 O(n) ，這也就是為什么B比A效率要高很多的緣故。C 和 B 相比，將平方函數(shù)替換成了 x*x ，由于少了遠(yuǎn)程函數(shù)調(diào)用和Pow函數(shù)本身的開(kāi)銷，效率有提高了不少。我在C的基礎(chǔ)上編寫了D算法，D算法采用并行計(jì)算技術(shù)，在我的雙核筆記本電腦上數(shù)據(jù)量比較大的情況下，其排序效率較C要提高30%左右。

　　下面重點(diǎn)介紹這個(gè)并行排序算法。算法思路其實(shí)很簡(jiǎn)單，就是將要排序的數(shù)組按照處理器數(shù)量等分成若干段，然后用和處理器數(shù)量等同的線程并行對(duì)各個(gè)小段進(jìn)行排序，排序結(jié)束和，再在單一線程中對(duì)這若干個(gè)已經(jīng)排序的小段進(jìn)行歸并排序，最后輸出完整的排序結(jié)果�？荚嚧罂紤]到和.Net 2.0 兼容，沒(méi)有用微軟提供的并行庫(kù)，而是用多線程來(lái)實(shí)現(xiàn)。

　　下面是測(cè)試結(jié)果：

　　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

　　從測(cè)試結(jié)果上看，當(dāng)要排序的數(shù)組長(zhǎng)度較短時(shí)，并行排序的效率甚至還沒(méi)有不進(jìn)行并行排序高，這主要是多線程的開(kāi)銷造成的。當(dāng)數(shù)組長(zhǎng)度增大到25萬(wàn)以上時(shí)，并行排序的優(yōu)勢(shì)開(kāi)始體現(xiàn)出來(lái)，隨著數(shù)組長(zhǎng)度的增長(zhǎng)，排序時(shí)間最后基本穩(wěn)定在但線程排序時(shí)間的 74% 左右，其中并行排序的消耗大概在50%左右，歸并排序的消耗在 14%左右。由此也可以推斷，如果在4CPU的機(jī)器上，其排序時(shí)間最多可以減少到單線程的 14 + 25 = 39%。8 CPU 為 14 + 12.5 = 26.5%。

　　目前這個(gè)算法在歸并算法上可能還有提高的余地，如果哪位高手能夠進(jìn)一步提高這個(gè)算法，不妨貼出來(lái)一起交流交流。

　　下面分別給出并行排序和歸并排序的代碼：

　　并行排序類 ParallelSort

　　Paralletsort 類是一個(gè)通用的泛型，調(diào)用起來(lái)非常簡(jiǎn)單，下面給一個(gè)簡(jiǎn)單的int型數(shù)組的排序示例：

　　class IntComparer : IComparer < int >

　　{

　　IComparer Members #region IComparer 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());

　　}

　　軟考軟件設(shè)計(jì)師歷年真題匯總(2007年-2010年)

　　2011年軟件水平考試軟件設(shè)計(jì)師知識(shí)點(diǎn)總結(jié)

　　2011軟件水平考試軟件設(shè)計(jì)師輔導(dǎo)資料匯總