C#各种集合操作的性能总结
2023-06-13 09:14:43 时间
本文主要记录的是C#各种集合操作的性能,下面的标记说明描述标记的时间,下面的表格对比各种集合各种操作的时间.
标记说明:
1.O(1)表示无论集合中有多少项,这个操作需要的时间都不变,例如,ArraryLIst的Add()方法就O(1),无论集合中有多少元素,在列表尾部添加一个新的元素的时间都是相同的.
2.O(n)表示对于集合中的每个元素,需要增加的时间量都是相同的,如果需要重新给集合分
配内存,ArrayList的Add()方法就O(n),改变容量,需要复制列表,复制的时间随元素的增加和线性增加.
3.O(logn)表示操作需要的时间随着集合中元素的增加和增加,但每个元素增加的时间不是
线性的.而是呈对数曲线,在集合中插入操作时,SortedDictionary<Tkey,Tvalue>就是
O(logn),而SortedList<Tkey,Tvalue>就是O(n),这里SortedDictionary<Tkey,Tvalue>
要快的多.因为它在树形结构中插入元素的效率比列表高的多.
下表显示各种集合的操作时间:
注:如果单元格中有多个大O值,表示集合需要重置大小,该操作需要一定的时间
如果单元格内容是no,就表示不支持这种操作.
集合
Add
Insert
Remove
Item
Sort
Find
List<T>
如果集合必须重置大小就是O(1)或O(n)
O(n)
O(n)
O(1)
O(nlogn)最坏情况O(n^2)
O(n)
Stack<T>(栈)
Push(),如果栈必须重置大小,就是O(1)或O(n)
no
Pop(),O(1)
no
no
no
Queue<T>(列队)
Enqueue(),如果栈必须重置大小,就是O(1)或O(n)
no
Dequeu(),O(1)
no
no
no
HastSet<T>(无序列表)
如果栈必须重置大小,就是O(1)或O(n)
O(1)
no
no
no
LinkedList<T>(链表)
AddLast(),O(1)
AddAfter(),O(1)
O(1)
no
no
O(n)
Dictionary<Tkey,TValue>
O(1)或O(n)
no
O(1)
O(1)
no
no
SortedDictionary<Tkey,Tvalue>
O(logn)
no
O(logn)
O(logn)
no
no
SortedList<Tkey,Tvalue>
no
O(n)
读写是O(logn),如果键在列表中,就是O(logn),如果键不在列表中就是O(n).
no
no
总结:
数组的大小是固定的,但可以使用列表作为动态增长集合,列队以先进先出的方式访问元素,栈以后进先出的方式访问元素,链表可以快速的插入和删除元素,但搜索比较慢,通过键和值可以使用字典,它的搜索和插入操作比较快,集(Hashset<T>)是用于无序的唯一项.
代码改变世界,记录知识.
标记说明:
1.O(1)表示无论集合中有多少项,这个操作需要的时间都不变,例如,ArraryLIst的Add()方法就O(1),无论集合中有多少元素,在列表尾部添加一个新的元素的时间都是相同的.
2.O(n)表示对于集合中的每个元素,需要增加的时间量都是相同的,如果需要重新给集合分
配内存,ArrayList的Add()方法就O(n),改变容量,需要复制列表,复制的时间随元素的增加和线性增加.
3.O(logn)表示操作需要的时间随着集合中元素的增加和增加,但每个元素增加的时间不是
线性的.而是呈对数曲线,在集合中插入操作时,SortedDictionary<Tkey,Tvalue>就是
O(logn),而SortedList<Tkey,Tvalue>就是O(n),这里SortedDictionary<Tkey,Tvalue>
要快的多.因为它在树形结构中插入元素的效率比列表高的多.
下表显示各种集合的操作时间:
注:如果单元格中有多个大O值,表示集合需要重置大小,该操作需要一定的时间
如果单元格内容是no,就表示不支持这种操作.
Add()
O(1)或O(n)
无序数据为O(n),如果必选重置大小,到列表的尾部就是
O(logn)
总结:
数组的大小是固定的,但可以使用列表作为动态增长集合,列队以先进先出的方式访问元素,栈以后进先出的方式访问元素,链表可以快速的插入和删除元素,但搜索比较慢,通过键和值可以使用字典,它的搜索和插入操作比较快,集(Hashset<T>)是用于无序的唯一项.
代码改变世界,记录知识.
相关文章
- C# winform DataGridView 常见属性
- c#数组赋初值_C#数组初始化
- c# 方法调用链System.Diagnostics.StackTrace[通俗易懂]
- C#之 对象数组
- 一个C#开发者学习SpringCloud搭建微服务的心路历程
- C#/.net程序调用python
- C#性能测试BenchmarkDotnet
- C#中检查null的语法糖,非常实用
- asp.net(c#)RSS功能实现代码
- c#读取文件内容存放到int数组array.txt
- choosesubjectc#switch
- C#中执行批处理文件(*.bat)的方法代码
- C#图片剪切与缩小的实例
- C#和asp.net中链接数据库中参数的几种传递方法实例代码
- 解析C#中的ref和out参数
- c#对xml增删改查操作示例
- Asp.Net(C#)自动执行计划任务的程序实例分析分享
- C#List中FindAll用法的一些简单示例
- c#反射表达式树模糊搜索示例
- c#调用vc写的ocx控件示例
- C#探秘系列(四)——GetHashCode,ExpandoObject
- C#特性-迭代器(上)及一些研究过程中的副产品
- C#关于类的只读只写属性实例分析
- C#实现的Socket服务器端、客户端代码分享
- c#中实现图片灰度化技术详解