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

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

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

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

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