云計算環(huán)境下排序算法性能的研究.pdf

1、隨著云計算環(huán)境中數(shù)據(jù)量的激增，人們急需研究在云環(huán)境下如何對大量數(shù)據(jù)進行快速有效的分析與處理。在云環(huán)境下對大量數(shù)據(jù)進行高效地排序是其中一個重要問題。一些被廣泛使用的排序算法是否能在云計算系統(tǒng)中高性能運行，運行時所需要消耗的云計算資源量都是令人非常關注的問題。本文主要進行Hadoop平臺上快速，高效，集群負載均衡度高，資源消耗少的排序算法的研究，主要工作為:
　　1)分析研究串行系統(tǒng)中效率較高的排序算法。在熟練掌握MapReduce編

2、程框架和Hadoop體系結(jié)構(gòu)的基礎上，對Radixsort，Quicksort以及Samplesort在Hadoop平臺上進行實現(xiàn)。分別對Radixsort，Quicksort和Samplesort的算法思想及在串行和并行系統(tǒng)中的復雜度問題進行比較分析。
　　2)對基于Hadoop平臺的Radixsort，Quicksort和Samplesort的執(zhí)行效率、CPU資源的消耗，內(nèi)存的消耗，以及處理機間的通信量進行研究和比較分析。通過

3、大量運行在Hadoop上的實驗，發(fā)現(xiàn)Hadoop平臺上的Samplesort相較于Radixsort和Quicksort具有排序速度快，負載均衡度高，CPU消耗低等優(yōu)勢。這一結(jié)果為云計算環(huán)境下設計更高效、節(jié)能的算法提供了有效的依據(jù)和基礎。
　　3)針對不均勻數(shù)據(jù)集的高效排序問題，研究并提出了一種排序效率高，負載均衡度高的隨機化分區(qū)Samplesort算法。Samplesort是一種在云計算環(huán)境中大量使用的排序算法。在數(shù)據(jù)可以均勻分

4、割的情況下，samplesort算法把數(shù)據(jù)分割成為多個數(shù)據(jù)塊，高速并行地對數(shù)據(jù)塊進行排序。Samplesort在處理一些密度均勻的數(shù)據(jù)集時具有較高效率，而現(xiàn)實生活中的數(shù)據(jù)集往往分布極不均勻。為了解決密度分布不均勻數(shù)據(jù)集的排序問題，提出了一種隨機化分區(qū)的樣本排序算法，RandomizedPartitionSampleSort(RPSS)。它引入了一個隨機化分區(qū)函數(shù)，能夠使得密度不均勻數(shù)據(jù)相對均勻的分布。通過大量運行在Hadoop集群上的實