本文主要記錄的是C#各種集合操作的性能,下面的標(biāo)記說明描述標(biāo)記的時間,下面的表格對比各種集合各種操作的時間.
標(biāo)記說明
:
1.O(1) 表示無論集合中有多少項(xiàng),這個操作需要的時間都不變,例如,ArraryLIst的Add()方法就O(1), 無論集合中有多少元素,在列表尾部添加一個新的元素的時間都是相同的.
2. O(n)表示對于集合中的每個元素,需要增加的時間量都是相同的,如果需要重新給集合分
配內(nèi)存,ArrayList的Add()方法就O(n),改變?nèi)萘?需要復(fù)制列表,復(fù)制的時間隨元素的增加和線性增加.
3. O(log n)表示操作需要的時間隨著集合中元素的增加和增加,但每個元素增加的時間不是
線性的.而是呈對數(shù)曲線,在集合中插入操作時,SortedDictionary
O(log n),而SortedList
要快的多.因?yàn)樗跇湫谓Y(jié)構(gòu)中插入元素的效率比列表高的多.
下表顯示各種集合的操作時間
:
注:如果單元格中有多個大O值,表示集合需要重置大小,該操作需要一定的時間
如果單元格內(nèi)容是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>(列隊(duì)) | 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> |
無序數(shù)據(jù)為O(n),如果必選重置大小,到列表的尾部就是 O(log n) |
no | O(n) | 讀寫是O(log n),如果鍵在列表中,就是O(log n),如果鍵不在列表中就是O(n). | no | no |
總結(jié)
:
數(shù)組的大小是固定的,但可以使用列表作為動態(tài)增長集合,列隊(duì)以先進(jìn)先出的方式訪問元素,棧以后進(jìn)先出的方式訪問元素, 鏈表可以快速的插入和刪除元素,但搜索比較慢,通過鍵和值可以使用字典,它的搜索和插入操作比較快,集(Hashset
代碼改變世界,記錄知識.
