基于C#实现外排序

一、N 路归并排序

1.1、概序

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

1.2、构建

<1> 生成数据
这个基本没什么好说的，采用随机数生成 n 条记录。　
<2> 切分数据
根据实际情况我们来决定到底要分成多少个小文件，并且小文件的数据必须是有序的，小文件的个数也对应这内存中有多少个优先队列。　
<3> 加入队列
我们知道内存队列存放的只是小文件的 topN 条记录，当内存队列为空时，我们需要再次从小文件中读取下一批的 TopN 条数据，然后放入中转站继续进行比较。
<4> 测试
最后我们来测试一下:
数据量：short.MaxValue。
内存存放量：1200。
在这种场景下，我们决定每个文件放 1000 条，也就有 33 个小文件，也就有 33 个内存队列，每个队列取 Top100 条，Batch=500 时刷新
硬盘，中转站存放 332 个数字（因为入中转站时打上了队列标记）,最后内存活动最大总数为：sum=33100+500+66=896<1200。
时间复杂度为 N*logN。
image.png
总的代码：

 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数据CreateData(short.MaxValue);//每个文件存放1000条var pageSize = 1000;//达到batchCount就刷新记录var batchCount = 0;//判断需要开启的队列var pageCount = Split(pageSize);//内存限制：1500条List<PriorityQueue<int?>> list = new List<PriorityQueue<int?>>();//定义一个队列中转器PriorityQueue<int?> queueControl = new PriorityQueue<int?>();//定义每个队列完成状态bool[] complete = new bool[pageCount];//队列读取文件时应该跳过的记录数int[] skip = new int[pageCount];//是否所有都完成了int allcomplete = 0;//定义 10 个队列for (int i = 0; i < pageCount; i++){list.Add(new PriorityQueue<int?>());//i：   记录当前的队列编码//list: 队列数据//skip：跳过的条数AddQueue(i, list, ref skip);}//初始化操作，从每个队列中取出一条记录，并且在入队的过程中//记录该数据所属的 “队列编号”for (int i = 0; i < list.Count; i++){var temp = list[i].Dequeue();//i:队列编码,level:要排序的数据queueControl.Eequeue(i, temp.level);}//默认500条写入一次文件List<int> batch = new List<int>();//记录下次应该从哪一个队列中提取数据int nextIndex = 0;while (queueControl.Count() > 0){//从中转器中提取数据var single = queueControl.Dequeue();//记录下一个队列总应该出队的数据nextIndex = single.t.Value;var nextData = list[nextIndex].Dequeue();//如果改对内弹出为null，则说明该队列已经，需要从nextIndex文件中读取数据if (nextData == null){//如果该队列没有全部读取完毕if (!complete[nextIndex]){AddQueue(nextIndex, list, ref skip);//如果从文件中读取还是没有，则说明改文件中已经没有数据了if (list[nextIndex].Count() == 0){complete[nextIndex] = true;allcomplete++;}else{nextData = list[nextIndex].Dequeue();}}}//如果弹出的数不为空，则将该数入中转站if (nextData != null){//将要出队的数据 转入 中转站queueControl.Eequeue(nextIndex, nextData.level);}batch.Add(single.level);//如果batch=500，或者所有的文件都已经读取完毕，此时我们要批量刷入数据if (batch.Count == batchCount || allcomplete == pageCount){var sw = new StreamWriter(Environment.CurrentDirectory + "//result.txt", true);foreach (var item in batch){sw.WriteLine(item);}sw.Close();batch.Clear();}}Console.WriteLine("恭喜，外排序完毕！");Console.Read();}#region 将数据加入指定编号队列/// <summary>/// 将数据加入指定编号队列/// </summary>/// <param name="i">队列编号</param>/// <param name="skip">文件中跳过的条数</param>/// <param name="list"></param>/// <param name="top">需要每次读取的条数</param>public static void AddQueue(int i, List<PriorityQueue<int?>> list, ref int[] skip, int top = 100){var result = File.ReadAllLines((Environment.CurrentDirectory + "//" + (i + 1) + ".txt")).Skip(skip[i]).Take(top).Select(j => Convert.ToInt32(j));//加入到集合中foreach (var item in result)list[i].Eequeue(null, item);//将个数累计到skip中，表示下次要跳过的记录数skip[i] += result.Count();}#endregion#region 随机生成数据/// <summary>/// 随机生成数据///<param name="max">执行生成的数据上线</param>/// </summary>public static void CreateData(int max){var sw = new StreamWriter(Environment.CurrentDirectory + "//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 将数据进行分份/// <summary>/// 将数据进行分份/// <param name="size">每页要显示的条数</param>/// </summary>public static int Split(int size){//文件总记录数int totalCount = 0;//每一份文件存放 size 条 记录List<int> small = new List<int>();var sr = new StreamReader((Environment.CurrentDirectory + "//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));//说明已经到达指定的 size 条数了if (totalCount % pageSize == 0){pageIndex = totalCount / pageSize;small = small.OrderBy(i => i).Select(i => i).ToList();File.WriteAllLines(Environment.CurrentDirectory + "//" + pageIndex + ".txt", small.Select(i => i.ToString()));small.Clear();}}else{//说明已经读完了，将剩余的small记录写入到文件中pageCount = (int)Math.Ceiling((double)totalCount / pageSize);small = small.OrderBy(i => i).Select(i => i).ToList();File.WriteAllLines(Environment.CurrentDirectory + "//" + pageCount + ".txt", small.Select(i => i.ToString()));break;}}return pageCount;}#endregion}}

优先队列：

 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>/// 定义一个数组来存放节点/// </summary>private List<HeapNode> nodeList = new List<HeapNode>();#region 堆节点定义/// <summary>/// 堆节点定义/// </summary>public class HeapNode{/// <summary>/// 实体数据/// </summary>public T t { get; set; }/// <summary>/// 优先级别 1-10个级别 (优先级别递增)/// </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){//将当前节点追加到堆尾nodeList.Add(new HeapNode(t, level));//如果只有一个节点，则不需要进行筛操作if (nodeList.Count == 1)return;//获取最后一个非叶子节点int parent = nodeList.Count / 2 - 1;//堆调整UpHeapAdjust(nodeList, parent);}#endregion#region 对堆进行上滤操作，使得满足堆性质/// <summary>/// 对堆进行上滤操作，使得满足堆性质/// </summary>/// <param name="nodeList"></param>/// <param name="index">非叶子节点的之后指针（这里要注意：我们/// 的筛操作时针对非叶节点的）/// </param>public void UpHeapAdjust(List<HeapNode> nodeList, int parent){while (parent >= 0){//当前index节点的左孩子var left = 2 * parent + 1;//当前index节点的右孩子var right = left + 1;//parent子节点中最大的孩子节点，方便于parent进行比较//默认为left节点var min = left;//判断当前节点是否有右孩子if (right < nodeList.Count){//判断parent要比较的最大子节点min = nodeList[left].level < nodeList[right].level ? left : right;}//如果parent节点大于它的某个子节点的话，此时筛操作if (nodeList[parent].level > nodeList[min].level){//子节点和父节点进行交换操作var temp = nodeList[parent];nodeList[parent] = nodeList[min];nodeList[min] = temp;//继续进行更上一层的过滤parent = (int)Math.Ceiling(parent / 2d) - 1;}else{break;}}}#endregion#region 优先队列的出队操作/// <summary>/// 优先队列的出队操作/// </summary>/// <returns></returns>public HeapNode Dequeue(){if (nodeList.Count == 0)return null;//出队列操作，弹出数据头元素var pop = nodeList[0];//用尾元素填充头元素nodeList[0] = nodeList[nodeList.Count - 1];//删除尾节点nodeList.RemoveAt(nodeList.Count - 1);//然后从根节点下滤堆DownHeapAdjust(nodeList, 0);return pop;}#endregion#region  对堆进行下滤操作，使得满足堆性质/// <summary>/// 对堆进行下滤操作，使得满足堆性质/// </summary>/// <param name="nodeList"></param>/// <param name="index">非叶子节点的之后指针（这里要注意：我们/// 的筛操作时针对非叶节点的）/// </param>public void DownHeapAdjust(List<HeapNode> nodeList, int parent){while (2 * parent + 1 < nodeList.Count){//当前index节点的左孩子var left = 2 * parent + 1;//当前index节点的右孩子var right = left + 1;//parent子节点中最大的孩子节点，方便于parent进行比较//默认为left节点var min = left;//判断当前节点是否有右孩子if (right < nodeList.Count){//判断parent要比较的最大子节点min = nodeList[left].level < nodeList[right].level ? left : right;}//如果parent节点小于它的某个子节点的话，此时筛操作if (nodeList[parent].level > nodeList[min].level){//子节点和父节点进行交换操作var temp = nodeList[parent];nodeList[parent] = nodeList[min];nodeList[min] = temp;//继续进行更下一层的过滤parent = min;}else{break;}}}#endregion#region 获取元素并下降到指定的level级别/// <summary>/// 获取元素并下降到指定的level级别/// </summary>/// <returns></returns>public HeapNode GetAndDownPriority(int level){if (nodeList.Count == 0)return null;//获取头元素var pop = nodeList[0];//设置指定优先级（如果为 MinValue 则为 -- 操作）nodeList[0].level = level == int.MinValue ? --nodeList[0].level : level;//下滤堆DownHeapAdjust(nodeList, 0);return nodeList[0];}#endregion#region 获取元素并下降优先级/// <summary>/// 获取元素并下降优先级/// </summary>/// <returns></returns>public HeapNode GetAndDownPriority(){//下降一个优先级return GetAndDownPriority(int.MinValue);}#endregion#region 返回当前优先队列中的元素个数/// <summary>/// 返回当前优先队列中的元素个数/// </summary>/// <returns></returns>public int Count(){return nodeList.Count;}#endregion}}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/206170.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Navicat 技术指引 | 适用于 GaussDB 的自动运行功能

Navicat 技术指引 | 适用于 GaussDB 的自动运行功能

Navicat Premium&#xff08;16.2.8 Windows版或以上&#xff09; 已支持对 GaussDB 主备版的管理和开发功能。它不仅具备轻松、便捷的可视化数据查看和编辑功能&#xff0c;还提供强大的高阶功能&#xff08;如模型、结构同步、协同合作、数据迁移等&#xff09;&#xff0c;这…
阅读更多...
a-select:远程搜索——防抖节流处理——基础积累

a-select:远程搜索——防抖节流处理——基础积累

a-select:远程搜索——防抖节流处理——基础积累 效果图下拉筛选数据&#xff1a;远程搜索功能&#xff1a; 效果图 下拉筛选数据&#xff1a; <a-selectshow-searchv-model"form.jobPositionCode"placeholder"请选择岗位"style"width: 100%"…
阅读更多...
Docker安装可视化工具Portainer

Docker安装可视化工具Portainer

目录 Portainer简介 Portainer安装 Portainer简介 Portainer是一款开源的容器管理平台&#xff0c;支持多种容器技术&#xff0c;如Docker、Kubernetes和Swarm等。它提供了一个易于使用的Web UI界面&#xff0c;可用于管理和监控容器和集群。Portainer旨在使容器管理更加简单…
阅读更多...
【带头学C++】----- 九、类和对象 ---- 9.1 类和对象的基本概念----(9.1.1---9.1.3)

【带头学C++】----- 九、类和对象 ---- 9.1 类和对象的基本概念----(9.1.1---9.1.3)

目录 9.1 类和对象的基本概念 9.1.1 类的封装性 9.1.2 定义类的步骤和方法 9.1.3 设计一个学生类 Student 9.1 类和对象的基本概念 9.1.1 类的封装性 类是一种用户自定义的数据类型&#xff0c;它定义了一组数据成员和成员函数。类可以看作是一个模板或者蓝图&#xff0c;用…
阅读更多...
Django之中间件与CSRF_TOKEN

Django之中间件与CSRF_TOKEN

文章目录 一、什么是中间件二、中间件有什么用三、Django自定义中间件中间件中主要方法及作用创建自定义中间件的步骤&#xff1a;process_request与process_response方法process_view方法process_exceptionprocess_template_response&#xff08;不常用&#xff09; 四、CSRF_…
阅读更多...
MySQL--慢查询（一）

MySQL--慢查询（一）

1. 查看慢查询日志是否开启 show variables like slow_query%; show variables like slow_query_log; 参数说明&#xff1a; 1、slow_query_log&#xff1a;这个参数设置为ON&#xff0c;可以捕获执行时间超过一定数值的SQL语句。 2、long_query_time&#xff1a;当SQL语句执行…
阅读更多...
latex中算法的几种模板

latex中算法的几种模板

latex中算法的几种模板_latex算法模板-CSDN博客文章浏览阅读6.2k次&#xff0c;点赞3次&#xff0c;收藏45次。latex中几种算法模板_latex算法模板https://blog.csdn.net/weixin_50514171/article/details/125136121?spm1001.2014.3001.5506
阅读更多...
【开源】基于Vue和SpringBoot的智能教学资源库系统

【开源】基于Vue和SpringBoot的智能教学资源库系统

项目编号&#xff1a; S 050 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S050&#xff0c;文末获取源码。} 项目编号&#xff1a;S050&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 课程档案模块2.3 课…
阅读更多...
Vue服务端渲染——同构渲染

Vue服务端渲染——同构渲染

Vue.js 可以用于构建客户端应用程序&#xff0c;组件的代码在浏览器中运行&#xff0c;并输出 DOM 元素。同时&#xff0c;Vue.js 还可以在 Node.js 环境中运行&#xff0c;它可以将同样的组件渲染为字符串并发送给浏览器。这实际上描述了 Vue.js 的两种渲染方式&#xff0c;即…
阅读更多...
＜Linux＞（极简关键、省时省力）《Linux操作系统原理分析之Linux 进程管理 5》（9）

＜Linux＞（极简关键、省时省力）《Linux操作系统原理分析之Linux 进程管理 5》（9）

《Linux操作系统原理分析之Linux 进程管理 5》&#xff08;9&#xff09; 4 Linux 进程管理4.5 Linux 信号4.5.1 信号的作用和种类1.信号机制2.信号种类 4.5.2 信号的处理4.5.3 信号处理函数1&#xff0e;数据结构2&#xff0e; 处理函数 signal3&#xff0e;程序例 4 Linux 进…
阅读更多...
免杀原理(php)

免杀原理(php)

免杀原理 0x01 前言 何为免杀&#xff0c;免杀就是一种逃脱杀毒软件查杀的方法&#xff0c;免杀的目的就是绕过“墙”&#xff0c;去执行危险的操作。那么如何绕过这堵“墙”&#xff0c;就是免杀的本质。有句俗话说得好“知己知彼&#xff0c;百战不殆”&#xff0c;想要用好…
阅读更多...
岩土工程监测新利器——振弦采集仪

岩土工程监测新利器——振弦采集仪

岩土工程监测新利器——振弦采集仪 振弦采集仪是一种常用的岩土工程监测仪器&#xff0c;主要用于测量岩土体的振动和应变情况。它采用先进的数字信号处理技术&#xff0c;可以实时采集和处理振弦信号&#xff0c;快速准确地获取岩土体的振动和应变信息。 振弦采集仪具有以下优…
阅读更多...
2016年五一杯数学建模B题能源总量控制下的城市工业企业协调发展问题解题全过程文档及程序

2016年五一杯数学建模B题能源总量控制下的城市工业企业协调发展问题解题全过程文档及程序

2016年五一杯数学建模 B题 能源总量控制下的城市工业企业协调发展问题 原题再现 能源是国民经济的重要物质基础,是工业企业发展的动力&#xff0c;但是过度的能源消耗&#xff0c;会破坏资源和环境&#xff0c;不利于经济的可持续发展。目前我国正处于经济转型的关键时期&…
阅读更多...
QT网络协议知识体系（一）

QT网络协议知识体系（一）

//获取主机的名称和ip地址 //获取主机的所有信息
阅读更多...
nodejs最新电商jd m端h5st 4.2签名算法4.2版本逆向，jd API接口，jd商品数据采集

nodejs最新电商jd m端h5st 4.2签名算法4.2版本逆向，jd API接口，jd商品数据采集

前言&#xff1a; jd m端使用最新的h5st 4.2签名算法&#xff0c;与h5st 4.1版本有很大的不同。在这儿分析一下&#xff0c;供大家参考。 一、目标地址(Base64解码) aHR0cHM6Ly9zby5tLmpkLmNvbS93YXJlL3NlYXJjaC5hY3Rpb24/a2V5d29yZD0lRTklOTklQTQlRTYlQjklQkYlRTYlOUMlQkEmc2…
阅读更多...
【电路笔记】-电阻串联

【电路笔记】-电阻串联

电阻串联 文章目录 电阻串联1、概述2、电阻串联3、串联电阻电压4、电阻串联示例15、分压电路6、电阻串联示例27、电阻串联的应用8、总结 当电阻器以菊花链方式连接在一条线上时&#xff0c;电阻器被称为串联连接&#xff0c;从而导致共同电流流过它们。 1、概述 各个电阻器可以…
阅读更多...
实例成员函数指针 的 一个小细节

实例成员函数指针 的 一个小细节

你提供的代码定义了一个名为a的类&#xff0c;并初始化了一个名为b的对象。代码还包括一个main函数。 让我们逐步解析这段代码&#xff1a; class a { public:int a::* * p; // 指向int成员指针的指针int a::* pp; // 指向int成员的指针int a::* a::* ppp; // …
阅读更多...
【开源】基于Vue+SpringBoot的智能教学资源库系统

【开源】基于Vue+SpringBoot的智能教学资源库系统

项目编号&#xff1a; S 050 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S050&#xff0c;文末获取源码。} 项目编号&#xff1a;S050&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 课程档案模块2.3 课…
阅读更多...
【迅搜03】全文检索、文档、倒排索引与分词

【迅搜03】全文检索、文档、倒排索引与分词

全文检索、文档、倒排索引与分词 今天还是概念性的内容&#xff0c;但是这些概念却是整个搜索引擎中最重要的概念。可以说&#xff0c;所有的搜索引擎就是实现了类似的概念才能称之为搜索引擎。而且今天的内容其实都是相关联的&#xff0c;所以不要以为标题上有四个名词就感觉好…
阅读更多...
058-第三代软件开发-文件Model

058-第三代软件开发-文件Model

第三代软件开发-文件Model 文章目录 第三代软件开发-文件Model项目介绍文件Model 关键字&#xff1a; Qt、 Qml、 关键字3、 关键字4、 关键字5 项目介绍 欢迎来到我们的 QML & C 项目&#xff01;这个项目结合了 QML&#xff08;Qt Meta-Object Language&#xff09;…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023