程序员如何高性能排序多个文件？

640?wx_fmt=gif

 

640?wx_fmt=png

640?wx_fmt=png

涨工资申请还在待审批中......

 

Python 第一地位稳了!微软正式拥抱 Python !

https://edu.csdn.net/topic/python115?utm_source=csdn_bw

作为一个技术人员，技术的问题还是要解决。经过线上日志的分析，日志采用小时机制，一个小时一个日志文件，同一个小时的日志文件有多个，也就是说同一时间内的日志有可能分散在多个日志文件中，这也是Y总要合并的主要原因。每个日志文件大约有500M，大约有100个。此时，如果你阅读到此文章，该怎么做呢？不如先静心想2分钟！

 

 

640?wx_fmt=png

问题分析

 

 

要想实现Y总的需求其实还是有几个难点的：

 

  • 如何能把所有的日志文件按照时间排序？

  • 日志文件的总大小为500M*100 ，大约50G，所以全部加载到内存是不可能的；

  • 程序执行过程中，要频繁排序并查找最小元素。

 

那我们该怎么做呢？其中一个解决方案就是它：堆。

 

 

640?wx_fmt=png

解决方案

 

 

堆定义

 

堆（heap）是计算机科学中一类特殊的数据结构的统称，通常是一个可以被看做一棵树的数组对象。

 

堆总是满足下列性质：

 

  • 堆中某个节点的值总是不大于或不小于其父节点的值；

  • 堆总是一棵完全二叉树（完全二叉树要求，除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列）。

 

对于每个节点的值都大于等于子树中每个节点值的堆，叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，叫作“小顶堆”。

 

640?wx_fmt=png

堆实现

 

完全二叉树比较适合用数组来存储（链表也可以实现）。为什么这么说呢？用数组来存储完全二叉树是非常节省存储空间的。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点。

 

640?wx_fmt=jpeg

 

经过上图可以发现，数组位置0为空，虽然浪费了一个存储空间，但是当计算元素在数组位置的时候确非常方便：数组下标为X的元素的左子树的下标为2x，右子树的下标为2x+1。

 

其实实现一个堆非常简单，就是顺着元素所在的路径，向上或者向下对比然后交换位置。

 

1、添加元素

 

添加元素的时候我们习惯采用自下而上的调整方式来调整堆，我们在数组的最后一个空闲位置插入新元素，按照堆的下标上标原则查找到父元素对比，如果小于父元素的值（大顶堆），则互相交换。如图：

 

640?wx_fmt=jpeg

 

2、删除最大（最小元素）

 

对于大顶堆，堆顶的元素就是最大元素。删除该元素之后，我们需要把第二大元素提到堆顶位置。依次类推，直到把路径上的所有元素都调整完毕。

 

640?wx_fmt=jpeg

 

总结

 

  • 小顶堆的顶部元素其实就是整个堆最小的元素，大顶堆顶部元素是整个堆的最大元素。这也是堆排序的最大优点，取最小元素或者最大元素时间复杂度为O(1)。

     

  • 删除元素的时候我们要注意一点，如果采用自顶向下交换元素的方式，在很多情况下造成堆严重的不平衡（左右子树深度相差较大）的情况，为了防止类似情况，我们可以把最后一个元素提到堆顶，然后调整的策略，因为最后一个元素总是在最后一级，不会造成左右子树相差很大的情况。

     

  • 对于有重复元素的堆，一种解决方法是认为是谁先谁大，后进入堆的元素小于先进入堆的元素，这样在查找的时候一定要查彻底才行。另外一种方式是在堆的每个元素中存储一个链表，用来存放相同的元素，原理类似于散列表。不过这样在删除这个元素的时候需要特殊处理一下。

 

  • 删除堆顶数据和往堆中插入数据的时间复杂度都是O(logn)。

     

  • 不断调整堆的过程其实就是排序过程，在某些场景下，我们可以利用堆来实现排序。

 

 

全面学python的时代，作为程序员你怎么看？

https://edu.csdn.net/topic/python115?utm_source=csdn_bw

640?wx_fmt=png

asp.net core 模拟代码

 

 

以下代码经过少许修改甚至不修改的情况下可直接在生产环境应用。

 

小顶堆实现代码

 

  1. /// <summary>
  2.     /// 小顶堆,T类型需要实现 IComparable 接口
  3.     /// </summary>
  4.     class MinHeap<T> where T : IComparable
  5.     {
  6.         private T[] container; // 存放堆元素的容器
  7.         private int capacity;  // 堆的容量，最大可以放多少个元素
  8.         private int count; // 堆中已经存储的数据个数
  9.  
  10.         public MinHeap(int _capacity)
  11.         {
  12.             container = new T[_capacity + 1];
  13.             capacity = _capacity;
  14.             count = 0;
  15.         }
  16.         //插入一个元素
  17.         public bool AddItem(T item)
  18.         {
  19.             if (count >= capacity)
  20.             {
  21.                 return false;
  22.             }
  23.             ++count;
  24.             container[count] = item;
  25.             int i = count;
  26.             while (i / 2 > 0 && container[i].CompareTo(container[i / 2]) < 0)
  27.             {
  28.                 // 自下往上堆化，交换 i 和i/2 元素
  29.                 T temp = container[i];
  30.                 container[i] = container[i / 2];
  31.                 container[i / 2] = temp;
  32.                 i = i / 2;
  33.             }
  34.             return true;
  35.         }
  36.         //获取最小的元素
  37.         public T GetMinItem()
  38.         {
  39.             if (count == 0)
  40.             {
  41.                 return default(T);
  42.             }
  43.             T result = container[1];
  44.             return result;
  45.         }
  46.         //删除最小的元素，即堆顶元素
  47.         public bool DeteleMinItem()
  48.         {
  49.             if (count == 0)
  50.             {
  51.                 return false;
  52.             }
  53.             container[1] = container[count];
  54.             container[count] = default(T);
  55.             --count;
  56.             UpdateHeap(container, count, 1);
  57.             return true;
  58.         }
  59.         //从某个节点开始从上向下 堆化
  60.         private void UpdateHeap(T[] a, int n, int i)
  61.         {
  62.             while (true)
  63.             {
  64.                 int maxPos = i;
  65.                 //遍历左右子树，确定那个是最小的元素
  66.                 if (i * 2 <= n && a[i].CompareTo(a[i * 2]) > 0)
  67.                 {
  68.                     maxPos = i * 2;
  69.                 }
  70.                 if (i * 2 + 1 <= n && a[maxPos].CompareTo(a[i * 2 + 1]) > 0)
  71.                 {
  72.                     maxPos = i * 2 + 1;
  73.                 }
  74.                 if (maxPos == i)
  75.                 {
  76.                     break;
  77.                 }
  78.                 T temp = container[i];
  79.                 container[i] = container[maxPos];
  80.                 container[maxPos] = temp;
  81.                 i = maxPos;
  82.             }
  83.         }
  84.     }

 

模拟日志文件内容

 

  1. //因为需要不停的从log文件读取内容，所以需要一个和log文件保持连接的包装
  2.     class LogInfoIndex : IComparable
  3.     {
  4.         //标志内容来自于哪个文件
  5.         public int FileIndex { get; set; }
  6.         //具体的日志文件内容
  7.         public LogInfo Data { get; set; }
  8.  
  9.         public int CompareTo(object obj)
  10.         {
  11.             var tempInfo = obj as LogInfoIndex;
  12.             if (this.Data.Index > tempInfo.Data.Index)
  13.             {
  14.                 return 1;
  15.             }
  16.             else if (this.Data.Index < tempInfo.Data.Index)
  17.             {
  18.                 return -1;
  19.             }
  20.             return 0;
  21.         }
  22.     }
  23.     class LogInfo
  24.     {       
  25.         //用int来模拟datetime 类型，因为用int 看的最直观
  26.         public int Index { get; set; }
  27.         public string UserName { get; set; }
  28.     }

 

生成模拟日志程序

 

  1.  static void WriteFile()
  2.         {
  3.             int fileCount = 0;
  4.             while (fileCount < 10)
  5.             {
  6.                 string filePath = $@"D:\log\{fileCount}.txt";
  7.                 int index = 0;
  8.                 while (index < 100000)
  9.                 {
  10.                     LogInfo info = new LogInfo() { Index = index, UserName = Guid.NewGuid().ToString() };
  11.                     File.AppendAllText(filePath, JsonConvert.SerializeObject(info)+ "\r\n");
  12.                     index++;
  13.                 }
  14.                 fileCount++;
  15.             }
  16.  
  17.         }

 

文件内容如下：

 

640?wx_fmt=jpeg

 

测试程序

 

  1. static void Main(string[] args)
  2.         {
  3.             int heapItemCount = 10;
  4.             int startIndex = 0;
  5.             StreamReader[] allReader = new StreamReader[10];
  6.             MinHeap<LogInfoIndex> container = new MinHeap<LogInfoIndex>(heapItemCount);
  7.  
  8.             //首先每个文件读取一条信息          
  9.             while(startIndex< heapItemCount)
  10.             {
  11.                 string filePath = $@"D:\log\{startIndex}.txt";
  12.                 System.IO.StreamReader reader = new System.IO.StreamReader(filePath);
  13.                 allReader[startIndex] = reader;
  14.                 string content= reader.ReadLine();
  15.                 var contentObj = JsonConvert.DeserializeObject<LogInfo>(content);
  16.                 LogInfoIndex item = new LogInfoIndex() {  FileIndex= startIndex , Data= contentObj };
  17.                 container.AddItem(item);
  18.                 startIndex++;
  19.             }
  20.             //然后开始循环出堆，入堆
  21.             while (true)
  22.             {
  23.                 var heapFirstItem = container.GetMinItem();
  24.                 if (heapFirstItem == null)
  25.                 {
  26.                     break;
  27.                 }
  28.                 container.DeteleMinItem();
  29.  
  30.                 File.AppendAllText($@"D:\log\total.txt", JsonConvert.SerializeObject(heapFirstItem.Data) + "\r\n");
  31.                 var nextContent = allReader[heapFirstItem.FileIndex].ReadLine();
  32.                 if (string.IsNullOrWhiteSpace( nextContent))
  33.                 {
  34.                     //如果其中一个文件已经读取完毕 则跳过
  35.                     continue;
  36.                 }
  37.                 var contentObj = JsonConvert.DeserializeObject<LogInfo>(nextContent);
  38.                 LogInfoIndex item = new LogInfoIndex() { FileIndex = heapFirstItem.FileIndex, Data = contentObj };
  39.                 container.AddItem(item);
  40.             }
  41.             //释放StreamReader
  42.             foreach (var reader in allReader)
  43.             {
  44.                 reader.Dispose();
  45.             }
  46.             Console.WriteLine("完成");        
  47.             Console.Read();
  48.         }

 

最终排序结果如下图：

 

640?wx_fmt=jpeg

 

机器使用CPU内存完全没有达到所有排序文件的总大小：

 

640?wx_fmt=png

作者：菜菜，一个奔走在通往互联网更高之路的工程师，热衷于互联网技术。目前就职于某互联网教育公司，应用服务端主要负责人。拥有10年+互联网开发经验。热衷于高性能、高并发、分布式技术领域的研究。 主要工作语言为C#和Golang 。

声明：本文为作者投稿，版权归对方所有，编辑郭芮。

 

 热 文 推 荐  

☞ 苹果的“价格战”还能走多远？ | 畅言

☞ Angular、React 当前，Vue.js 优劣几何？

程序员如何在 HTTPS 中高效配置通配符证书？| 技术头条

☞ 315 后，等待失业的程序员

☞ 套路贷+套路培训，IT 培训机构造假术大公开 | 程序员有话说

那位13岁就当上老板的开发者是如何炼成的？

☞ 好莱坞大片! 为躲避死亡威胁, 只用15步, 这个密码朋克大叔就从世界"消失"了...

确认！贾扬清加盟阿里，任技术副总裁

都道业务提升坑大事儿多，但英特尔云方案却说“简单”

☞ Python 爬取蔡徐坤的 10 万转发数据，竟是假流量？

 

 

System.out.println("点个在看吧！");
console.log("点个在看吧！");
print("点个在看吧！");
printf("点个在看吧！\n");
cout << "点个在看吧！" << endl;
Console.WriteLine("点个在看吧！");
Response.Write("点个在看吧！");
alert("点个在看吧！")
echo "点个在看吧！"

45K！刚面完 AI 岗，这些技术必须掌握！

https://edu.csdn.net/topic/ai30?utm_source=csdn_bw

 

640?wx_fmt=png喜欢就点击“在看”吧！

CSDN
微信公众号
成就一亿技术人
注：本文转载自blog.csdn.net的CSDN资讯的文章"https://blog.csdn.net/csdnnews/article/details/88684898"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！