首页 资讯 应用 高压 设计 行业 低压 电路图 关于

嵌入式

旗下栏目: PLC 嵌入式 单片机 DCS

外排序-多路归并

嵌入式 | 发布时间:2018-06-06 | 人气: | #评论# | 本文关键字:外排序,多路归并
摘要:说到排序,大家第一反应基本上是内排序,是的,算法嘛,玩的就是内存,然而内存是有限制的,总有装不下的那一天,此时就可以来玩玩 外排序,当然在我看来,外排序考验的是一个程序员

说到排序,大家第一反应基本上是内排序,是的,算法嘛,玩的就是内存,然而内存是有限制的,总有装不下的那一天,此时就可以来玩玩外排序,当然在我看来,外排序考验的是一个程序员的架构能力,而不仅仅局限于排序这个层次。

 一:N路归并排序

1.概序

    我们知道算法中有一种叫做分治思想,一个大问题我们可以采取分而治之,各个突破,当子问题解决了,大问题也就KO了,还有一点我们知道内排序的归并排序是采用二路归并的,因为分治后有LogN层,每层两路归并需要N的时候,最后复杂度为NlogN,那么外排序我们可以将这个“二”扩大到M,也就是将一个大文件分成M个小文件,每个小文件是有序的,然后对应在内存中我们开M个优先队列,每个队列从对应编号的文件中读取TopN条记录,然后我们从M路队列中各取一个数字进入中转站队列,并将该数字打上队列编号标记,当从中转站出来的最小数字就是我们最后要排序的数字之一,因为该数字打上了队列编号,所以方便我们通知对应的编号队列继续出数字进入中转站队列,可以看出中转站一直保存了M个记录,当中转站中的所有数字都出队完毕,则外排序结束。如果大家有点蒙的话,我再配合一张图,相信大家就会一目了然,这考验的是我们的架构能力。

1528289572156162.png

图中这里有个Batch容器,这个容器我是基于性能考虑的,当batch=n时,我们定时刷新到文件中,保证内存有足够的空间。

2.构建

<1> 生成数据

   这个基本没什么好说的,采用随机数生成n条记录。

#region 随机生成数据  

  1. /// <summary>  

  2. /// 随机生成数据  

  3. ///<param name="max">执行生成的数据上线</param>  

  4. /// </summary>  

  5. public static void CreateData(int max)  

  6. {  

  7.     var sw = new StreamWriter(Environment.CurrentDirectory + "//demo.txt");  

  8.    

  9.     for (int i = 0; i < max; i++)  

  10.     {  

  11.         Thread.Sleep(2);  

  12.         var rand = new Random((int)DateTime.Now.Ticks).Next(0, int.MaxValue >> 3);  

  13.    

  14.         sw.WriteLine(rand);  

  15.     }  

  16.     sw.Close();  

  17. }  

  18. #endregion</span>  

<2> 切分数据

     根据实际情况我们来决定到底要分成多少个小文件,并且小文件的数据必须是有序的,小文件的个数也对应这内存中有多少个优先队列。

  1. #region 将数据进行分份  

  2. /// <summary>  

  3. /// 将数据进行分份  

  4. /// <param name="size">每页要显示的条数</param>  

  5. /// </summary>  

  6. public static int Split(int size)  

  7. {  

  8.     //文件总记录数  

  9.     int totalCount = 0;  

  10.    

  11.     //每一份文件存放 size 条 记录  

  12.     List<int> small = new List<int>();  

  13.    

  14.     var sr = new StreamReader((Environment.CurrentDirectory + "//demo.txt"));  

  15.    

  16.     var pageSize = size;  

  17.    

  18.     int pageCount = 0;  

  19.    

  20.     int pageIndex = 0;  

  21.    

  22.     while (true)  

  23.     {  

  24.         var line = sr.ReadLine();  

  25.    

  26.         if (!string.IsNullOrEmpty(line))  

  27.         {  

  28.             totalCount++;  

  29.    

  30.             //加入小集合中  

  31.             small.Add(Convert.ToInt32(line));  

  32.    

  33.             //说明已经到达指定的 size 条数了  

  34.             if (totalCount % pageSize == 0)  

  35.             {  

  36.                 pageIndex = totalCount / pageSize;  

  37.    

  38.                 small = small.OrderBy(i => i).Select(i => i).ToList();  

  39.    

  40.                 File.WriteAllLines(Environment.CurrentDirectory + "//" + pageIndex + ".txt", small.Select(i => i.ToString()));  

  41.    

  42.                 small.Clear();  

  43.             }  

  44.         }  

  45.         else  

  46.         {  

  47.             //说明已经读完了,将剩余的small记录写入到文件中  

  48.             pageCount = (int)Math.Ceiling((double)totalCount / pageSize);  

  49.    

  50.             small = small.OrderBy(i => i).Select(i => i).ToList();  

  51.    

  52.             File.WriteAllLines(Environment.CurrentDirectory + "//" + pageCount + ".txt", small.Select(i => i.ToString()));  

  53.    

  54.             break;  

  55.         }  

  56.     }  

  57.    

  58.     return pageCount;  

  59. }  

  60. #endregion</span>  

<3> 加入队列

    我们知道内存队列存放的只是小文件的topN条记录,当内存队列为空时,我们需要再次从小文件中读取下一批的TopN条数据,然后放入中转站继续进行比较。

  1. #region 将数据加入指定编号队列  

  2.         /// <summary>  

  3.         /// 将数据加入指定编号队列  

  4.         /// </summary>  

  5.         /// <param name="i">队列编号</param>  

  6.         /// <param name="skip">文件中跳过的条数</param>  

  7.         /// <param name="list"></param>  

  8.         /// <param name="top">需要每次读取的条数</param>  

  9.         public static void AddQueue(int i, List<PriorityQueue<int?>> list, ref int[] skip, int top = 100)  

  10.         {  

  11.             var result = File.ReadAllLines((Environment.CurrentDirectory + "//" + (i + 1) + ".txt"))  

  12.                              .Skip(skip[i]).Take(top).Select(j => Convert.ToInt32(j));  

  13.    

  14.             //加入到集合中  

  15.             foreach (var item in result)  

  16.                 list[i].Eequeue(null, item);  

  17.    

  18.             //将个数累计到skip中,表示下次要跳过的记录数  

  19.             skip[i] += result.Count();  

  20.         }  

  21.         #endregion</span>  

责任编辑:多路归并
首页 | 电气资讯 | 应用技术 | 高压电器 | 电气设计 | 行业应用 | 低压电器 | 电路图 | 关于我们 | 版权声明

Copyright 2017-2018 电气自动化网 版权所有 辽ICP备17010593号-1

电脑版 | 移动版 原创声明:本站大部分内容为原创,转载请注明电气自动化网转载;部分内容来源网络,如侵犯您的权益请发送邮件到[email protected]联系我们删除。