首頁(yè) 考試吧論壇 Exam8視線 考試商城 網(wǎng)絡(luò)課程 模擬考試 考友錄 實(shí)用文檔 求職招聘 論文下載
2011中考 | 2011高考 | 2012考研 | 考研培訓(xùn) | 在職研 | 自學(xué)考試 | 成人高考 | 法律碩士 | MBA考試
MPA考試 | 中科院
四六級(jí) | 職稱英語(yǔ) | 商務(wù)英語(yǔ) | 公共英語(yǔ) | 托福 | 雅思 | 專四專八 | 口譯筆譯 | 博思 | GRE GMAT
新概念英語(yǔ) | 成人英語(yǔ)三級(jí) | 申碩英語(yǔ) | 攻碩英語(yǔ) | 職稱日語(yǔ) | 日語(yǔ)學(xué)習(xí) | 法語(yǔ) | 德語(yǔ) | 韓語(yǔ)
計(jì)算機(jī)等級(jí)考試 | 軟件水平考試 | 職稱計(jì)算機(jī) | 微軟認(rèn)證 | 思科認(rèn)證 | Oracle認(rèn)證 | Linux認(rèn)證
華為認(rèn)證 | Java認(rèn)證
公務(wù)員 | 報(bào)關(guān)員 | 銀行從業(yè)資格 | 證券從業(yè)資格 | 期貨從業(yè)資格 | 司法考試 | 法律顧問(wèn) | 導(dǎo)游資格
報(bào)檢員 | 教師資格 | 社會(huì)工作者 | 外銷員 | 國(guó)際商務(wù)師 | 跟單員 | 單證員 | 物流師 | 價(jià)格鑒證師
人力資源 | 管理咨詢師考試 | 秘書(shū)資格 | 心理咨詢師考試 | 出版專業(yè)資格 | 廣告師職業(yè)水平
駕駛員 | 網(wǎng)絡(luò)編輯
衛(wèi)生資格 | 執(zhí)業(yè)醫(yī)師 | 執(zhí)業(yè)藥師 | 執(zhí)業(yè)護(hù)士
會(huì)計(jì)從業(yè)資格考試會(huì)計(jì)證) | 經(jīng)濟(jì)師 | 會(huì)計(jì)職稱 | 注冊(cè)會(huì)計(jì)師 | 審計(jì)師 | 注冊(cè)稅務(wù)師
注冊(cè)資產(chǎn)評(píng)估師 | 高級(jí)會(huì)計(jì)師 | ACCA | 統(tǒng)計(jì)師 | 精算師 | 理財(cái)規(guī)劃師 | 國(guó)際內(nèi)審師
一級(jí)建造師 | 二級(jí)建造師 | 造價(jià)工程師 | 造價(jià)員 | 咨詢工程師 | 監(jiān)理工程師 | 安全工程師
質(zhì)量工程師 | 物業(yè)管理師 | 招標(biāo)師 | 結(jié)構(gòu)工程師 | 建筑師 | 房地產(chǎn)估價(jià)師 | 土地估價(jià)師 | 巖土師
設(shè)備監(jiān)理師 | 房地產(chǎn)經(jīng)紀(jì)人 | 投資項(xiàng)目管理師 | 土地登記代理人 | 環(huán)境影響評(píng)價(jià)師 | 環(huán)保工程師
城市規(guī)劃師 | 公路監(jiān)理師 | 公路造價(jià)師 | 安全評(píng)價(jià)師 | 電氣工程師 | 注冊(cè)測(cè)繪師 | 注冊(cè)計(jì)量師
繽紛校園 | 實(shí)用文檔 | 英語(yǔ)學(xué)習(xí) | 作文大全 | 求職招聘 | 論文下載 | 訪談 | 游戲

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

考試吧整理了“2011年軟考軟件設(shè)計(jì)師知識(shí)點(diǎn):并行排序算法”,幫助考生梳理知識(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(niǎo) 將平方和開(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ǔ)上編寫(xiě)了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());

  }

1 2 3 4 5 6 7 8 下一頁(yè)
  2011年上半年軟考報(bào)名時(shí)間及方式匯總

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

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

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

文章搜索
軟件水平考試欄目導(dǎo)航
版權(quán)聲明:如果軟件水平考試網(wǎng)所轉(zhuǎn)載內(nèi)容不慎侵犯了您的權(quán)益,請(qǐng)與我們聯(lián)系800@exam8.com,我們將會(huì)及時(shí)處理。如轉(zhuǎn)載本軟件水平考試網(wǎng)內(nèi)容,請(qǐng)注明出處。