11.10 性能

许多集合类都提供了相同的功能，例如，SortedList类与SortedDictionary类的功能几乎完全相同。但是，其性能常常有很大区别。一个集合使用的内存少，另一个集合的元素检索速度快。在MSDN文档中，集合的方法常常有性能提示，给出了以大写O记号表示的操作时间：

● O(1)

● O(log n)

● O(n)

O(1)表示无论集合中有多少数据项，这个操作需要的时间都不变。例如，ArrayList类的Add()方法就具有O(1)行为。无论列表中有多少个元素，在列表末尾添加一个新元素的时间都相同。Count属性会给出元素个数，所以很容易找到列表末尾。

O(n)表示对于集合执行一个操作需要的时间在最坏情况时是N。如果需要重新给集合分配内存，ArrayList类的Add()方法就是一个O(n)操作。改变容量，需要复制列表，复制的时间随元素的增加而线性增加。

O(log n)表示操作需要的时间随集合中元素的增加而增加，但每个元素需要增加的时间不是线性的，而是呈对数曲线。在集合中执行插入操作时，SortedDictionary<TKey, TValue>集合类具有O(log n)行为，而SortedList<TKey, TValue>集合类具有O(n)行为。这里SortedDictionary <TKey, TValue>集合类要快得多，因为它在树型结构中插入元素的效率比列表高得多。

表11-4列出了集合类及其执行不同操作的性能，例如，添加、插入和删除元素。使用这个表可以选择性能最佳的集合类。左列是集合类，Add列给出了在集合中添加元素所需的时间。List<T>和HashSet<T>类把Add方法定义为在集合中添加元素。其他集合类用不同的方法把元素添加到集合中。例如，Stack<T>类定义了Push()方法，Queue<T>类定义了Enqueue()方法。这些信息也列在表中。

如果单元格中有多个大O值，表示若集合需要重置大小，该操作就需要一定的时间。例如，在List<T>类中，添加元素的时间是O(1)。如果集合的容量不够大，需要重置大小，则重置大小需要的时间长度就是O(n)。集合越大，重置大小操作的时间就越长。最好避免重置集合的大小，而应把集合的容量设置为一个可以包含所有元素的值。

如果表单元格的内容是n/a(代表not applicable)，就表示这个操作不能应用于这种集合类型。