快捷導(dǎo)航

C#實(shí)現(xiàn)外排序的示例代碼

更新時(shí)間：2023年11月28日 09:34:20 作者：神仙別鬧

本文介紹了C#中的外排序技術(shù),以及如何使用C#實(shí)現(xiàn)外排序算法,通過使用排序算法,可以對大量數(shù)據(jù)進(jìn)行排序,并且可以有效地處理超大數(shù)據(jù)集,感興趣的可以了解下

一、N 路歸并排序

1.1、概序

我們知道算法中有一種叫做分治思想，一個(gè)大問題我們可以采取分而治之，各個(gè)突破，當(dāng)子問題解決了，大問題也就 KO 了，還有一點(diǎn)我們知道內(nèi)排序的歸并排序是采用二路歸并的，因?yàn)榉种魏笥?LogN 層，每層兩路歸并需要 N 的時(shí)候，最后復(fù)雜度為 NlogN，那么外排序我們可以將這個(gè)“二”擴(kuò)大到 M，也就是將一個(gè)大文件分成 M 個(gè)小文件，每個(gè)小文件是有序的，然后對應(yīng)在內(nèi)存中我們開 M 個(gè)優(yōu)先隊(duì)列，每個(gè)隊(duì)列從對應(yīng)編號(hào)的文件中讀取 TopN 條記錄，然后我們從 M 路隊(duì)列中各取一個(gè)數(shù)字進(jìn)入中轉(zhuǎn)站隊(duì)列，并將該數(shù)字打上隊(duì)列編號(hào)標(biāo)記，當(dāng)從中轉(zhuǎn)站出來的最小數(shù)字就是我們最后要排序的數(shù)字之一，因?yàn)樵摂?shù)字打上了隊(duì)列編號(hào)，所以方便我們通知對應(yīng)的編號(hào)隊(duì)列繼續(xù)出數(shù)字進(jìn)入中轉(zhuǎn)站隊(duì)列，可以看出中轉(zhuǎn)站一直保存了 M 個(gè)記錄，當(dāng)中轉(zhuǎn)站中的所有數(shù)字都出隊(duì)完畢，則外排序結(jié)束。如果大家有點(diǎn)蒙的話，我再配合一張圖，相信大家就會(huì)一目了然，這考驗(yàn)的是我們的架構(gòu)能力。

圖中這里有個(gè) Batch 容器，這個(gè)容器我是基于性能考慮的，當(dāng) batch=n 時(shí)，我們定時(shí)刷新到文件中，保證內(nèi)存有足夠的空間。

1.2、構(gòu)建

<1> 生成數(shù)據(jù)
這個(gè)基本沒什么好說的，采用隨機(jī)數(shù)生成 n 條記錄。　
<2> 切分?jǐn)?shù)據(jù)
根據(jù)實(shí)際情況我們來決定到底要分成多少個(gè)小文件，并且小文件的數(shù)據(jù)必須是有序的，小文件的個(gè)數(shù)也對應(yīng)這內(nèi)存中有多少個(gè)優(yōu)先隊(duì)列?！?br /><3> 加入隊(duì)列
我們知道內(nèi)存隊(duì)列存放的只是小文件的 topN 條記錄，當(dāng)內(nèi)存隊(duì)列為空時(shí)，我們需要再次從小文件中讀取下一批的 TopN 條數(shù)據(jù)，然后放入中轉(zhuǎn)站繼續(xù)進(jìn)行比較。
<4> 測試
最后我們來測試一下:
數(shù)據(jù)量：short.MaxValue。
內(nèi)存存放量：1200。
在這種場景下，我們決定每個(gè)文件放 1000 條，也就有 33 個(gè)小文件，也就有 33 個(gè)內(nèi)存隊(duì)列，每個(gè)隊(duì)列取 Top100 條，Batch=500 時(shí)刷新
硬盤，中轉(zhuǎn)站存放 332 個(gè)數(shù)字（因?yàn)槿胫修D(zhuǎn)站時(shí)打上了隊(duì)列標(biāo)記）,最后內(nèi)存活動(dòng)最大總數(shù)為：sum=33100+500+66=896<1200。
時(shí)間復(fù)雜度為 N*logN。

總的代碼：

 using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 using System.Diagnostics;
 using System.Threading;
 using System.IO;
 using System.Threading.Tasks;
 
 namespace ConsoleApplication2
 {
     public class Program
     {
         public static void Main()
         {
             //生成2^15數(shù)據(jù)
             CreateData(short.MaxValue);
 
             //每個(gè)文件存放1000條
             var pageSize = 1000;
 
             //達(dá)到batchCount就刷新記錄
             var batchCount = 0;
 
             //判斷需要開啟的隊(duì)列
             var pageCount = Split(pageSize);
 
             //內(nèi)存限制：1500條
             List<PriorityQueue<int?>> list = new List<PriorityQueue<int?>>();
 
             //定義一個(gè)隊(duì)列中轉(zhuǎn)器
             PriorityQueue<int?> queueControl = new PriorityQueue<int?>();
 
             //定義每個(gè)隊(duì)列完成狀態(tài)
             bool[] complete = new bool[pageCount];
 
             //隊(duì)列讀取文件時(shí)應(yīng)該跳過的記錄數(shù)
             int[] skip = new int[pageCount];
 
             //是否所有都完成了
             int allcomplete = 0;
 
             //定義 10 個(gè)隊(duì)列
             for (int i = 0; i < pageCount; i++)
             {
                 list.Add(new PriorityQueue<int?>());
 
                 //i：   記錄當(dāng)前的隊(duì)列編碼
                 //list: 隊(duì)列數(shù)據(jù)
                 //skip：跳過的條數(shù)
                 AddQueue(i, list, ref skip);
             }
 
             //初始化操作，從每個(gè)隊(duì)列中取出一條記錄，并且在入隊(duì)的過程中
             //記錄該數(shù)據(jù)所屬的 “隊(duì)列編號(hào)”
             for (int i = 0; i < list.Count; i++)
             {
                 var temp = list[i].Dequeue();
 
                 //i:隊(duì)列編碼,level:要排序的數(shù)據(jù)
                 queueControl.Eequeue(i, temp.level);
             }
 
             //默認(rèn)500條寫入一次文件
             List<int> batch = new List<int>();
 
             //記錄下次應(yīng)該從哪一個(gè)隊(duì)列中提取數(shù)據(jù)
             int nextIndex = 0;
 
             while (queueControl.Count() > 0)
             {
                 //從中轉(zhuǎn)器中提取數(shù)據(jù)
                 var single = queueControl.Dequeue();
 
                 //記錄下一個(gè)隊(duì)列總應(yīng)該出隊(duì)的數(shù)據(jù)
                 nextIndex = single.t.Value;
 
                 var nextData = list[nextIndex].Dequeue();
 
                 //如果改對內(nèi)彈出為null，則說明該隊(duì)列已經(jīng)，需要從nextIndex文件中讀取數(shù)據(jù)
                 if (nextData == null)
                 {
                     //如果該隊(duì)列沒有全部讀取完畢
                     if (!complete[nextIndex])
                     {
                         AddQueue(nextIndex, list, ref skip);
 
                         //如果從文件中讀取還是沒有，則說明改文件中已經(jīng)沒有數(shù)據(jù)了
                         if (list[nextIndex].Count() == 0)
                         {
                             complete[nextIndex] = true;
                             allcomplete++;
                         }
                         else
                         {
                             nextData = list[nextIndex].Dequeue();
                         }
                     }
                 }
 
                 //如果彈出的數(shù)不為空，則將該數(shù)入中轉(zhuǎn)站
                 if (nextData != null)
                 {
                     //將要出隊(duì)的數(shù)據(jù) 轉(zhuǎn)入 中轉(zhuǎn)站
                     queueControl.Eequeue(nextIndex, nextData.level);
                 }
 
                 batch.Add(single.level);
 
                 //如果batch=500，或者所有的文件都已經(jīng)讀取完畢，此時(shí)我們要批量刷入數(shù)據(jù)
                 if (batch.Count == batchCount || allcomplete == pageCount)
                 {
                     var sw = new StreamWriter(Environment.CurrentDirectory + "http://result.txt", true);
 
                     foreach (var item in batch)
                     {
                         sw.WriteLine(item);
                     }
 
                     sw.Close();
 
                     batch.Clear();
                 }
             }
 
             Console.WriteLine("恭喜，外排序完畢！");
             Console.Read();
         }
 
         #region 將數(shù)據(jù)加入指定編號(hào)隊(duì)列
         /// <summary>
         /// 將數(shù)據(jù)加入指定編號(hào)隊(duì)列
         /// </summary>
         /// <param name="i">隊(duì)列編號(hào)</param>
         /// <param name="skip">文件中跳過的條數(shù)</param>
         /// <param name="list"></param>
         /// <param name="top">需要每次讀取的條數(shù)</param>
         public static void AddQueue(int i, List<PriorityQueue<int?>> list, ref int[] skip, int top = 100)
         {
             var result = File.ReadAllLines((Environment.CurrentDirectory + "http://" + (i + 1) + ".txt"))
                              .Skip(skip[i]).Take(top).Select(j => Convert.ToInt32(j));
 
             //加入到集合中
             foreach (var item in result)
                 list[i].Eequeue(null, item);
 
             //將個(gè)數(shù)累計(jì)到skip中，表示下次要跳過的記錄數(shù)
             skip[i] += result.Count();
         }
         #endregion
 
         #region 隨機(jī)生成數(shù)據(jù)
         /// <summary>
         /// 隨機(jī)生成數(shù)據(jù)
         ///<param name="max">執(zhí)行生成的數(shù)據(jù)上線</param>
         /// </summary>
         public static void CreateData(int max)
         {
             var sw = new StreamWriter(Environment.CurrentDirectory + "http://demo.txt");
 
             for (int i = 0; i < max; i++)
             {
                 Thread.Sleep(2);
                 var rand = new Random((int)DateTime.Now.Ticks).Next(0, int.MaxValue >> 3);
 
                 sw.WriteLine(rand);
             }
             sw.Close();
         }
         #endregion
 
         #region 將數(shù)據(jù)進(jìn)行分份
         /// <summary>
         /// 將數(shù)據(jù)進(jìn)行分份
         /// <param name="size">每頁要顯示的條數(shù)</param>
         /// </summary>
         public static int Split(int size)
         {
             //文件總記錄數(shù)
             int totalCount = 0;
 
             //每一份文件存放 size 條 記錄
             List<int> small = new List<int>();
 
             var sr = new StreamReader((Environment.CurrentDirectory + "http://demo.txt"));
 
             var pageSize = size;
 
             int pageCount = 0;
 
             int pageIndex = 0;
 
             while (true)
             {
                 var line = sr.ReadLine();
 
                 if (!string.IsNullOrEmpty(line))
                 {
                     totalCount++;
 
                     //加入小集合中
                     small.Add(Convert.ToInt32(line));
 
                     //說明已經(jīng)到達(dá)指定的 size 條數(shù)了
                     if (totalCount % pageSize == 0)
                     {
                         pageIndex = totalCount / pageSize;
 
                         small = small.OrderBy(i => i).Select(i => i).ToList();
 
                         File.WriteAllLines(Environment.CurrentDirectory + "http://" + pageIndex + ".txt", small.Select(i => i.ToString()));
 
                         small.Clear();
                     }
                 }
                 else
                 {
                     //說明已經(jīng)讀完了，將剩余的small記錄寫入到文件中
                     pageCount = (int)Math.Ceiling((double)totalCount / pageSize);
 
                     small = small.OrderBy(i => i).Select(i => i).ToList();
 
                     File.WriteAllLines(Environment.CurrentDirectory + "http://" + pageCount + ".txt", small.Select(i => i.ToString()));
 
                     break;
                 }
             }
 
             return pageCount;
         }
         #endregion
     }
 }

優(yōu)先隊(duì)列：

 using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 using System.Diagnostics;
 using System.Threading;
 using System.IO;
 
 namespace ConsoleApplication2
 {
     public class PriorityQueue<T>
     {
         /// <summary>
         /// 定義一個(gè)數(shù)組來存放節(jié)點(diǎn)
         /// </summary>
         private List<HeapNode> nodeList = new List<HeapNode>();
 
         #region 堆節(jié)點(diǎn)定義
         /// <summary>
         /// 堆節(jié)點(diǎn)定義
         /// </summary>
         public class HeapNode
         {
             /// <summary>
             /// 實(shí)體數(shù)據(jù)
             /// </summary>
             public T t { get; set; }
 
             /// <summary>
             /// 優(yōu)先級(jí)別 1-10個(gè)級(jí)別 (優(yōu)先級(jí)別遞增)
             /// </summary>
             public int level { get; set; }
 
             public HeapNode(T t, int level)
             {
                 this.t = t;
                 this.level = level;
             }
 
             public HeapNode() { }
         }
         #endregion
 
         #region  添加操作
         /// <summary>
         /// 添加操作
         /// </summary>
         public void Eequeue(T t, int level = 1)
         {
             //將當(dāng)前節(jié)點(diǎn)追加到堆尾
             nodeList.Add(new HeapNode(t, level));
 
             //如果只有一個(gè)節(jié)點(diǎn)，則不需要進(jìn)行篩操作
             if (nodeList.Count == 1)
                 return;
 
             //獲取最后一個(gè)非葉子節(jié)點(diǎn)
             int parent = nodeList.Count / 2 - 1;
 
             //堆調(diào)整
             UpHeapAdjust(nodeList, parent);
         }
         #endregion
 
         #region 對堆進(jìn)行上濾操作，使得滿足堆性質(zhì)
         /// <summary>
         /// 對堆進(jìn)行上濾操作，使得滿足堆性質(zhì)
         /// </summary>
         /// <param name="nodeList"></param>
         /// <param name="index">非葉子節(jié)點(diǎn)的之后指針（這里要注意：我們
         /// 的篩操作時(shí)針對非葉節(jié)點(diǎn)的）
         /// </param>
         public void UpHeapAdjust(List<HeapNode> nodeList, int parent)
         {
             while (parent >= 0)
             {
                 //當(dāng)前index節(jié)點(diǎn)的左孩子
                 var left = 2 * parent + 1;
 
                 //當(dāng)前index節(jié)點(diǎn)的右孩子
                 var right = left + 1;
 
                 //parent子節(jié)點(diǎn)中最大的孩子節(jié)點(diǎn)，方便于parent進(jìn)行比較
                 //默認(rèn)為left節(jié)點(diǎn)
                 var min = left;
 
                 //判斷當(dāng)前節(jié)點(diǎn)是否有右孩子
                 if (right < nodeList.Count)
                 {
                     //判斷parent要比較的最大子節(jié)點(diǎn)
                     min = nodeList[left].level < nodeList[right].level ? left : right;
                 }
 
                 //如果parent節(jié)點(diǎn)大于它的某個(gè)子節(jié)點(diǎn)的話，此時(shí)篩操作
                 if (nodeList[parent].level > nodeList[min].level)
                 {
                     //子節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行交換操作
                     var temp = nodeList[parent];
                     nodeList[parent] = nodeList[min];
                     nodeList[min] = temp;
 
                     //繼續(xù)進(jìn)行更上一層的過濾
                     parent = (int)Math.Ceiling(parent / 2d) - 1;
                 }
                 else
                 {
                     break;
                 }
             }
         }
         #endregion
 
         #region 優(yōu)先隊(duì)列的出隊(duì)操作
         /// <summary>
         /// 優(yōu)先隊(duì)列的出隊(duì)操作
         /// </summary>
         /// <returns></returns>
         public HeapNode Dequeue()
         {
             if (nodeList.Count == 0)
                 return null;
 
             //出隊(duì)列操作，彈出數(shù)據(jù)頭元素
             var pop = nodeList[0];
 
             //用尾元素填充頭元素
             nodeList[0] = nodeList[nodeList.Count - 1];
 
             //刪除尾節(jié)點(diǎn)
             nodeList.RemoveAt(nodeList.Count - 1);
 
             //然后從根節(jié)點(diǎn)下濾堆
             DownHeapAdjust(nodeList, 0);
 
             return pop;
         }
         #endregion
 
         #region  對堆進(jìn)行下濾操作，使得滿足堆性質(zhì)
         /// <summary>
         /// 對堆進(jìn)行下濾操作，使得滿足堆性質(zhì)
         /// </summary>
         /// <param name="nodeList"></param>
         /// <param name="index">非葉子節(jié)點(diǎn)的之后指針（這里要注意：我們
         /// 的篩操作時(shí)針對非葉節(jié)點(diǎn)的）
         /// </param>
         public void DownHeapAdjust(List<HeapNode> nodeList, int parent)
         {
             while (2 * parent + 1 < nodeList.Count)
             {
                 //當(dāng)前index節(jié)點(diǎn)的左孩子
                 var left = 2 * parent + 1;
 
                 //當(dāng)前index節(jié)點(diǎn)的右孩子
                 var right = left + 1;
 
                 //parent子節(jié)點(diǎn)中最大的孩子節(jié)點(diǎn)，方便于parent進(jìn)行比較
                 //默認(rèn)為left節(jié)點(diǎn)
                 var min = left;
 
                 //判斷當(dāng)前節(jié)點(diǎn)是否有右孩子
                 if (right < nodeList.Count)
                 {
                     //判斷parent要比較的最大子節(jié)點(diǎn)
                     min = nodeList[left].level < nodeList[right].level ? left : right;
                 }
 
                 //如果parent節(jié)點(diǎn)小于它的某個(gè)子節(jié)點(diǎn)的話，此時(shí)篩操作
                 if (nodeList[parent].level > nodeList[min].level)
                 {
                     //子節(jié)點(diǎn)和父節(jié)點(diǎn)進(jìn)行交換操作
                     var temp = nodeList[parent];
                     nodeList[parent] = nodeList[min];
                     nodeList[min] = temp;
 
                     //繼續(xù)進(jìn)行更下一層的過濾
                     parent = min;
                 }
                 else
                 {
                     break;
                 }
             }
         }
         #endregion
 
         #region 獲取元素并下降到指定的level級(jí)別
         /// <summary>
         /// 獲取元素并下降到指定的level級(jí)別
         /// </summary>
         /// <returns></returns>
         public HeapNode GetAndDownPriority(int level)
         {
             if (nodeList.Count == 0)
                 return null;
 
             //獲取頭元素
             var pop = nodeList[0];
 
             //設(shè)置指定優(yōu)先級(jí)（如果為 MinValue 則為 -- 操作）
             nodeList[0].level = level == int.MinValue ? --nodeList[0].level : level;
 
             //下濾堆
             DownHeapAdjust(nodeList, 0);
 
             return nodeList[0];
         }
         #endregion
 
         #region 獲取元素并下降優(yōu)先級(jí)
         /// <summary>
         /// 獲取元素并下降優(yōu)先級(jí)
         /// </summary>
         /// <returns></returns>
         public HeapNode GetAndDownPriority()
         {
             //下降一個(gè)優(yōu)先級(jí)
             return GetAndDownPriority(int.MinValue);
         }
         #endregion
 
         #region 返回當(dāng)前優(yōu)先隊(duì)列中的元素個(gè)數(shù)
         /// <summary>
         /// 返回當(dāng)前優(yōu)先隊(duì)列中的元素個(gè)數(shù)
         /// </summary>
         /// <returns></returns>
         public int Count()
         {
             return nodeList.Count;
         }
         #endregion
     }
 }

到此這篇關(guān)于C#實(shí)現(xiàn)外排序的示例代碼的文章就介紹到這了,更多相關(guān)C# 外排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: