[發明專利]一種基于大數據快速排序算法和分布式排序處理系統

在審

• 申請號: 201710077531.4
• 申請日: 2017-02-14
• 公開（公告）號: CN108427680A
• 公開（公告）日: 2018-08-21
• 發明（設計）人: 張向利
• 申請（專利權）人: 張向利
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明提供了一種基于大數據快速排序的算法及分布式排序處理系統。排序算法采用迭代列處理方式進行快速排序，此算法最大限度降低了計算復雜度和空間復雜度，迭代列處理排序法與獨特的復合型數據結構相結合，極大地提高了排序處理效率。本發明根據迭代列處理排序法的特點，提出分布式排序處理系統的實施方案，兩者有機地結合在一起，使得本發明提出的迭代列處理排序法，可以拓展到針對大規模排序數據進行集群化分布式處理。

技術領域

本發明涉及計算機數據排序技術領域，尤其涉及大數據快速排序、分布式處理和負載均衡系統。

背景技術

當今已進入信息大爆炸的時代，算法運行效率與資源使用率直接關系到大數據處理成本的高低，大數據處理低成本運行已經成為企業核心競爭力的重要體現。現有排序算法存在計算效率不高、內存空間利用不夠充分等問題。排序算法作為大數據信息時代最基礎性的技術，提高排序算法效率和充分利用存儲資源是降低大數據處理成本的重要方式。

發明內容

本發明提出一套全新的快速排序算法，最大限度降低了計算復雜度和空間復雜度，達到充分利用計算機各種資源的目的，并且建立分布式排序處理系統，適應大規模數據處理的需要，制定了分布式處理節點的負載均衡策略。

附圖說明

附圖用來提供對本發明的進一步理解，并且構成說明書的一部分，與本發明的實施例并用于解釋本發明，并不構成對本發明的限制。在附圖中：

圖1為分布式排序處理系統流程圖；

圖2為排序算法處理流程圖。

具體實施方式

以下結合附圖對本發明的優選實施例進行說明，以便于理解本發明的原理及實施方式，此處所描述的優選實施例僅用于說明和理解本發明，并不用于限定本發明。

本發明提及的分布式排序處理系統所需硬件包括一臺“主管理節點”計算機和n(n≥1)臺“計算節點”計算機，節點之間相互聯通的網絡環境。“主管理節點”計算機負責任務分配、計算節點負載均衡閥值、監視“計算節點”任務完成情況，以及“計算節點”可用性和性能檢測。“計算節點”負責接收并執行“主管理節點”計算機分配的排序任務、向“主管理節點”計算機發送任務完成和完成任務所用時間報告。

本發明提及的“本機待處理文件”是指排序數據文本目標文件。

本發明提及的“數據元素”為文本目標文件的行數據，也就是排序處理的目標個體數據。

本發明為了更準確地說明分布式排序處理系統工作流程，以及事件處理規則，制作了具體的系統工作流程圖，見附圖1“分布式排序處理系統流程圖”。

步驟1：“主管理節點”計算機向所有“計算節點”計算機發送讀取“本機待處理文件”到內存中的指令。

步驟2：“計算節點”計算機接收到“主管理節點”計算機發出的讀取“本機待處理文件”指令后，按行讀取數據文件。

步驟3：“計算節點”計算機按行方式讀取“數據元素”，并截取“數據元素”第一個字符，假定此字符為“c”。以字符“c”為關鍵字、以“計數D”(以“1”為初始值)為鍵值插入到“散列表A”中；以字符“c”為關鍵字、以“數據元素”字符串單鏈表為鍵值插入到“散列表B”中。插入規則：如果此字符在“散列表A”中不存在，向“散列表A”和“散列表B”分別執行相應插入操作；如果此字符“c”已存在“散列表A”中，則對以字符“c”為關鍵字的“散列表A”鍵值執行累加“1”操作，向以字符“c”為關鍵字的“散列表B”字符串單鏈表鍵值中追加“數據元素”項。

步驟4：重復執行“步驟3”操作，直到“本機待處理文件”讀取完成，并向“主管理節點”計算機發送完成分割文件報告。