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

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› ASP.NET›ASP.NET编程经验

原作者: [db:作者] 来自: [db:来源] 收藏邀请

本文主要记录的是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