当前位置： 移动技术网 > IT编程>开发语言>.net > C#各种集合操作的性能总结

C#各种集合操作的性能总结

2017年12月12日  | 移动技术网IT编程  | 我要评论

jiouqu,黑道校园风云,林志玲学雷锋

本文主要记录的是c#各种集合操作的性能,下面的标记说明描述标记的时间,下面的表格对比各种集合各种操作的时间.

标记说明:
1.o(1) 表示无论集合中有多少项,这个操作需要的时间都不变,例如,arrarylist的add()方法就o(1), 无论集合中有多少元素,在列表尾部添加一个新的元素的时间都是相同的.
2. o(n)表示对于集合中的每个元素,需要增加的时间量都是相同的,如果需要重新给集合分
配内存,arraylist的add()方法就o(n),改变容量,需要复制列表,复制的时间随元素的增加和线性增加.
3. o(log n)表示操作需要的时间随着集合中元素的增加和增加,但每个元素增加的时间不是
线性的.而是呈对数曲线,在集合中插入操作时,sorteddictionary<tkey,tvalue>就是
o(log n),而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(n log n)最坏情况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)

add()

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(log n) no o(log n) o(log n) no no
sortedlist<tkey,tvalue>

无序数据为o(n),如果必选重置大小,到列表的尾部就是

o(log n)

 no o(n) 读写是o(log n),如果键在列表中,就是o(log n),如果键不在列表中就是o(n). no no

总结:
数组的大小是固定的,但可以使用列表作为动态增长集合,列队以先进先出的方式访问元素,栈以后进先出的方式访问元素, 链表可以快速的插入和删除元素,但搜索比较慢,通过键和值可以使用字典,它的搜索和插入操作比较快,集(hashset<t>) 是用于无序的唯一项.
代码改变世界,记录知识.

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网