C#各種集合操作的性能總結(jié)
更新時間：2012年12月27日 14:37:26 作者：
本文主要記錄的是C#各種集合操作的性能,下面的標(biāo)記說明描述標(biāo)記的時間,下面的表格對比各種集合各種操作的時間,需要了解的朋友可以參考下
本文主要記錄的是C#各種集合操作的性能,下面的標(biāo)記說明描述標(biāo)記的時間,下面的表格對比各種集合各種操作的時間.
標(biāo)記說明:
1.O(1) 表示無論集合中有多少項,這個操作需要的時間都不變,例如,ArraryLIst的Add()方法就O(1), 無論集合中有多少元素,在列表尾部添加一個新的元素的時間都是相同的.
2. O(n)表示對于集合中的每個元素,需要增加的時間量都是相同的,如果需要重新給集合分
配內(nèi)存,ArrayList的Add()方法就O(n),改變?nèi)萘?需要復(fù)制列表,復(fù)制的時間隨元素的增加和線性增加.
3. O(log n)表示操作需要的時間隨著集合中元素的增加和增加,但每個元素增加的時間不是
線性的.而是呈對數(shù)曲線,在集合中插入操作時,SortedDictionary<Tkey,Tvalue>就是
O(log n),而SortedList<Tkey,Tvalue> 就是O(n),這里SortedDictionary<Tkey,Tvalue>
要快的多.因為它在樹形結(jié)構(gòu)中插入元素的效率比列表高的多.
下表顯示各種集合的操作時間:
注:如果單元格中有多個大O值,表示集合需要重置大小,該操作需要一定的時間
如果單元格內(nèi)容是no,就表示不支持這種操作.
總結(jié):
數(shù)組的大小是固定的,但可以使用列表作為動態(tài)增長集合,列隊以先進(jìn)先出的方式訪問元素,棧以后進(jìn)先出的方式訪問元素, 鏈表可以快速的插入和刪除元素,但搜索比較慢,通過鍵和值可以使用字典,它的搜索和插入操作比較快,集(Hashset<T>) 是用于無序的唯一項.
代碼改變世界,記錄知識.
標(biāo)記說明:
1.O(1) 表示無論集合中有多少項,這個操作需要的時間都不變,例如,ArraryLIst的Add()方法就O(1), 無論集合中有多少元素,在列表尾部添加一個新的元素的時間都是相同的.
2. O(n)表示對于集合中的每個元素,需要增加的時間量都是相同的,如果需要重新給集合分
配內(nèi)存,ArrayList的Add()方法就O(n),改變?nèi)萘?需要復(fù)制列表,復(fù)制的時間隨元素的增加和線性增加.
3. O(log n)表示操作需要的時間隨著集合中元素的增加和增加,但每個元素增加的時間不是
線性的.而是呈對數(shù)曲線,在集合中插入操作時,SortedDictionary<Tkey,Tvalue>就是
O(log n),而SortedList<Tkey,Tvalue> 就是O(n),這里SortedDictionary<Tkey,Tvalue>
要快的多.因為它在樹形結(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>(列隊) | 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)增長集合,列隊以先進(jìn)先出的方式訪問元素,棧以后進(jìn)先出的方式訪問元素, 鏈表可以快速的插入和刪除元素,但搜索比較慢,通過鍵和值可以使用字典,它的搜索和插入操作比較快,集(Hashset<T>) 是用于無序的唯一項.
代碼改變世界,記錄知識.
相關(guān)文章
MVC4制作網(wǎng)站教程第三章 添加用戶組操作3.2
這篇文章主要為大家詳細(xì)介紹了MVC4制作網(wǎng)站教程，添加用戶組功能的實現(xiàn)代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2016-08-08
這篇文章主要介紹了ASP.NET中Global和URLReWrite用法,較為深入淺出的分析了Global.asax的功能及配置技巧,并實例分析了URLReWrite實現(xiàn)偽靜態(tài)的方法,需要的朋友可以參考下2015-06-06
asp.net下Request.QueryString取不到值的解決方法
2008-01-01
asp.net自帶的菜單控件采用的table和javascript，導(dǎo)致生成的大量的html,同時在很多瀏覽器中都無法顯示出子菜單，也只能在IE中能顯示出來。2009-11-11
這篇文章介紹了.NET Core單元測試的兩種方法，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-04-04
先裝了FRAMEWORK，后裝IIS導(dǎo)致asp.net頁面無法訪問的解決方法
如果先裝了FRAMEWORK，后裝IIS。有可能沒有在IIS中注冊，就會導(dǎo)致在頁面中無法訪問的情況2012-01-01
asp.net上傳Excel文件并讀取數(shù)據(jù)的實現(xiàn)方法
這篇文章主要給大家介紹了關(guān)于asp.net上傳Excel文件并讀取數(shù)據(jù)的實現(xiàn)方法，文中通過示例代碼以及圖文介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
SignalR Self Host+MVC等多端消息推送服務(wù)（一）
這篇文章主要為大家詳細(xì)介紹了SignalR Self Host+MVC等多端消息推送服務(wù)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-06-06
LINQ操作數(shù)組代碼（交集,并集,差集,最值,平均,去重復(fù)）
數(shù)組是大學(xué)里經(jīng)常拿來做算法練習(xí)的對象。一些經(jīng)典算法非常有價值，考試、裝逼、面試都十分有用。但現(xiàn)在是效率時代，編程講究生產(chǎn)效率，利用LINQ，可以讓程序猿避免寫一些基本算法，把精力花在業(yè)務(wù)處理上2012-02-02
asp.net(c#)ref,out ,params的區(qū)別
C#中有三個關(guān)鍵字-ref，out ，params，雖然本人不喜歡這三個關(guān)鍵字，因為它們疑似破壞面向?qū)ο筇匦?。但是既然m$把融入在c#體系中，那么我們就來認(rèn)識一下參數(shù)修飾符ref，out ，params吧，還有它們的區(qū)別。2009-12-12