前言

今天分享一下日常工作中遇到的性能问题和解决方案,比较零碎,后续会持续更新(运行环境为.net core 3.1)

本次分享的案例都是由实际生产而来,经过简化后作为举例

Part 1(作为简单数据载体时class和struct的性能对比)

关于class和struct的区别,根据经验,在实际开发的绝大多数场景,都会使用class作为数据类型,但是如果是作为简单数据的超大集合的类型,并且不涉及到拷贝、传参等其他操作的时候,可以考虑使用struct,因为相对于引用类型的class分配在堆上,作为值类型的struct是分配在栈上的,这样就拥有了更快的创建速度和节约了指针的空间,列举了3000万个元素的集合分别以class和struct作为类型,做如下测试(测试工具为vs自带的 Diagnostic Tools):

class Program {
static void Main (string[] args) {
var structs = new List<StructTest> ();
var stopwatch1 = new Stopwatch ();
stopwatch1.Start ();
for (int i = 0; i < 30000000; i++) {
structs.Add (new StructTest { Id = i, Value = i });
}
stopwatch1.Stop ();
var structsTotalMemory = GC.GetTotalMemory (true);
Console.WriteLine ($"使用结构体时消耗内存:{structsTotalMemory}字节,耗时:{stopwatch1.ElapsedMilliseconds}毫秒");
Console.ReadLine ();
} public struct StructTest {
public int Id { get; set; }
public int Value { get; set; }
}
}

class Program {
static void Main (string[] args) {
var classes = new List<ClassTest> ();
var stopwatch2 = new Stopwatch ();
stopwatch2.Start ();
for (int i = 0; i < 30000000; i++) {
classes.Add (new ClassTest { Id = i, Value = i });
}
stopwatch2.Stop ();
var classesTotalMemory = GC.GetTotalMemory (true);
Console.WriteLine ($"使用类时消耗内存:{classesTotalMemory}字节,耗时:{ stopwatch2.ElapsedMilliseconds}毫秒");
Console.ReadLine ();
} public struct StructTest {
public int Id { get; set; }
public int Value { get; set; }
}
}

通过计算,struct的空间消耗包含了:每个结构体包含两个存放在栈上的整型,每个整型占4个字节,每个结构体占8字节,乘以3000万个元素共计占用240,000,000字节, 跟实际测量值大体吻合;

而class的空间消耗较为复杂,包含了:每个类包含两个存在堆上的整型,每个整型占4字节,两个存在栈上的指针,因为是64位计算机所以每个指针占8字节,再加上类自身的指针8字节,每个类占24字节(4+4+8+8+8),乘以3000万个元素共计占用960,000,000字节,跟实际测量值大体吻合。时间消耗方面class因为存在内存分配,耗时5秒左右,远大于struct的1.5秒。

基于此次测试,

更多关于class和struct的关系和区别请移步微软官方文档   https://docs.microsoft.com/en-us/dotnet/standard/design-guidelines/choosing-between-class-and-struct

Part 2(集合嵌套遍历的优化)

关于嵌套集合遍历,我们以两层集合嵌套遍历,每个集合存放10000个乱序的整型,然后统计同时存在两个集合的元素个数,从上到下分别以常规嵌套循环,使用HashSet类型,参考PostgreSQL的MergeJoin思路举例:

class Program {
static void Main (string[] args) {
var l1s = new List<int> ();
var l2s = new List<int> ();
var rd = new Random ();
for (int i = 0; i < 10000; i++) {
l1s.Add (rd.Next (1, 10000));
l2s.Add (rd.Next (1, 10000));
} var sw = new Stopwatch ();
sw.Start ();
var r = new HashSet<int> ();
foreach (var l1 in l1s) {
foreach (var l2 in l2s) {
if (l1 == l2) {
r.Add (l1);
}
}
}
sw.Stop ();
Console.WriteLine ($"共找到{r.Count}个元素同时存在于l1s和l2s,共计耗时{sw.ElapsedMilliseconds}毫秒");
Console.ReadLine ();
}

class Program {
static void Main (string[] args) {
var l1s = new HashSet<int> ();
var l2s = new HashSet<int> ();
var rd = new Random ();
while (l1s.Count < 10000)
l1s.Add (rd.Next (1, 100000));
while (l2s.Count < 10000)
l2s.Add (rd.Next (1, 100000)); var sw = new Stopwatch ();
sw.Start ();
var r = new List<int> ();
foreach (var l1 in l1s) {
if (l2s.Contains (l1)) {
r.Add (l1);
}
}
sw.Stop ();
Console.WriteLine ($"共找到{r.Count}个元素同时存在于l1s和l2s,共计耗时{sw.ElapsedMilliseconds}毫秒");
Console.ReadLine ();
}

class Program {
static void Main (string[] args) {
var l1s = new List<int> ();
var l2s = new List<int> ();
var rd = new Random ();
for (int i = 0; i < 10000; i++) {
l1s.Add (rd.Next (1, 10000));
l2s.Add (rd.Next (1, 10000));
} var sw = new Stopwatch ();
sw.Start ();
var r = new List<int> ();
l1s = l1s.OrderBy (x => x).ToList ();
l2s = l2s.OrderBy (x => x).ToList ();
var l1index = 0;
var l2index = 0;
for (int i = 0; i < 10000; i++) {
var l1v = l1s[l1index];
var l2v = l2s[l2index];
if (l1v == l2v) {
r.Add (l1v);
l1index++;
l2index++;
}
if (l1v > l2v && l2index < 10000)
l2index++;
if (l1v < l2v && l1index < 10000)
l1index++; if (l1index == 9999 && l2index == 9999)
break;
}
sw.Stop ();
Console.WriteLine ($"共找到{r.Count}个元素同时存在于l1和l2s,共计耗时{sw.ElapsedMilliseconds}毫秒");
Console.ReadLine ();
}

由结果可见,常规嵌套遍历耗时1秒,时间复杂度为O(n2);使用HashSet耗时3毫秒,HashSet底层使用了哈希表,通过循环外层集合,对内层集合直接进行hash查找,时间复杂度为O(n); 参考PostgreSQL的MergeJoin思路耗时19毫秒,思路为先对集合进行排序,再标记当前位移,利用数组可以下标直接取值的特性,时间复杂度为O(n)。由此可见,对于数据量较大的集合,嵌套循环要尤为重视起来。

更多关于merge join的设计思路请移步PostgreSQL的官方文档  https://www.postgresql.org/docs/12/planner-optimizer.html

要注意的是,无论是使用哈希表还是排序,都会引入额外的损耗,毕竟在计算机的世界里,要么以时间换空间,要么以空间换时间,如果想同时优化时间或空间可以办到吗?在某些场景上也是有可能的,可以参考我之前的博文,通过内存映射文件结合今天讲的内容,可以尝试一下。

如有任何问题,欢迎大家随时指正,分享和试错也是个学习的过程,谢谢大家~

日常分享:关于时间复杂度和空间复杂度的一些优化心得分享(C#)的更多相关文章

  1. MongoDB优化心得分享

    这里总结下这段时间使用mongo的心得,列出了几个需要注意的地方. 1. 系统参数及mongo参数设置 mongo参数主要是storageEngine和directoryperdb,这两个参数一开始不 ...

  2. 从js 讲解时间复杂度和空间复杂度

    1. 博客背景 今天有同事在检查代码的时候,由于函数写的性能不是很好,被打回去重构了,细思极恐,今天和大家分享一篇用js讲解的时间复杂度和空间复杂度的博客 2. 复杂度的表示方式 之前有看过的,你可能 ...

  3. C#中常用的排序算法的时间复杂度和空间复杂度

    常用的排序算法的时间复杂度和空间复杂度   常用的排序算法的时间复杂度和空间复杂度 排序法 最差时间分析 平均时间复杂度 稳定度 空间复杂度 冒泡排序 O(n2) O(n2) 稳定 O(1) 快速排序 ...

  4. [Java初探外篇]__关于时间复杂度与空间复杂度

    前言 我们在前面的排序算法的学习中了解到了,排序算法的分类,效率的比较所使用到的判断标准,就包括时间复杂度和空间复杂度,当时因为这两个定义还是比较难以理解的,所以决定单独开一篇文章,记录一下学习的过程 ...

  5. 算法时间复杂度、空间复杂度(大O表示法)

    什么是算法? 计算机是人的大脑的延伸,它的存在主要是为了帮助我们解决问题. 而算法在计算机领域中就是为了解决问题而指定的一系列简单的指令集合.不同的算法需要不同的资源,例如:执行时间或消耗内存. 如果 ...

  6. php算法基础----时间复杂度和空间复杂度

    算法复杂度分为时间复杂度和空间复杂度. 其作用: 时间复杂度是指执行算法所需要的计算工作量: 而空间复杂度是指执行这个算法所需要的内存空间. (算法的复杂性体现在运行该算法时的计算机所需资源的多少上, ...

  7. Python语言算法的时间复杂度和空间复杂度

    算法复杂度分为时间复杂度和空间复杂度. 其作用: 时间复杂度是指执行算法所需要的计算工作量: 而空间复杂度是指执行这个算法所需要的内存空间. (算法的复杂性体现在运行该算法时的计算机所需资源的多少上, ...

  8. Unity MMORPG游戏优化经验分享

    https://mp.weixin.qq.com/s/thGF2WVUkIQYQDrz5DISxA 今天由Unity技术支持工程师高岩,根据实际的技术支持工作经验积累,分享如何对Unity MMORP ...

  9. 百度APP移动端网络深度优化实践分享(二):网络连接优化篇

    本文由百度技术团队“蔡锐”原创发表于“百度App技术”公众号,原题为<百度App网络深度优化系列<二>连接优化>,感谢原作者的无私分享. 一.前言 在<百度APP移动端网 ...

  10. 百度APP移动端网络深度优化实践分享(一):DNS优化篇

    本文由百度技术团队“蔡锐”原创发表于“百度App技术”公众号,原题为<百度App网络深度优化系列<一>DNS优化>,感谢原作者的无私分享. 一.前言 网络优化是客户端几大技术方 ...

随机推荐

  1. jq选择器基础

    Jquery $代表选择器 使用jq必须要导入jq文件 <script src="http://libs.baidu.com/jquery/2.0.0/jquery.min.js&qu ...

  2. eclipse + python dev

    错误:Project interpreter not specified解决方法 http://blog.csdn.net/magictong/article/details/7288732 安装Py ...

  3. 一个通过网络转换Ico到Png图片的小小程序(Ico2Png)

    做软件界面需要用到ico文件, 结果皮肤库不支持ico格式的图标, 所以就想到了把ico转换成png. 网上ico转png的软件貌似并不多, 反倒是png转ico很大一片~~~~~~~~~ 要转换ic ...

  4. MVC 登录认证与授权及读取登录错误码

    最近悟出来一个道理,在这儿分享给大家:学历代表你的过去,能力代表你的现在,学习代表你的将来. 十年河东十年河西,莫欺少年穷 学无止境,精益求精    最近在自学MVC,遇到的问题很多,索性一点点总结下 ...

  5. vs2012+qt5.2.0环境搭建/vs2013 + qt5.3.2 环境搭建

    分类: Windows Qt2014-01-17 00:50 15434人阅读 评论(18) 收藏 举报 此文章已作废,请参考我的新文章: vs2013 + qt5.3.2 环境搭建 ( http:/ ...

  6. JavaScript浮点运算的问题 (乘法)

    <script type="text/javascript"> var get_b_val_final=accMul(get_b_val,100)+"%&qu ...

  7. 2.如何安装vmvare tools

    1.在主页点击虚拟机 重装vmvaretools,接着就会下载tar.gz包 2.cd 到解压包的地方,解压sudo tar zxf ... 3.解压之后会生成一个vmvare-toos-distri ...

  8. [Usaco2015 Jan]Grass Cownoisseur Tarjan缩点+SPFA

    考试的时候忘了缩点,人为dfs模拟缩点,没想到竟然跑了30分,RB爆发... 边是可以重复走的,所以在同一个强连通分量里,无论从那个点进入从哪个点出,所有的点一定能被一条路走到. 要使用缩点. 然后我 ...

  9. ES5继承

    原型继承 <script type="text/javascript"> function Father(){}//构造函数 //原型属性 Father.prototy ...

  10. Uncaught SyntaxError: Invalid shorthand property initializer报错

    出现这个错误一定是:把":"写成了"="号