基礎(chǔ)集合類是每一個(gè) Mac/iOS 應(yīng)用的基本組成部分。在本文中,我們將對(duì)”老類” (NSArray
, NSSet
)和”新類” (NSMapTable
, NSHashTable
, NSPointerArray
) 進(jìn)行一個(gè)深入的研究,探索每一個(gè)的效率細(xì)節(jié),并討論其使用場(chǎng)景。
作者提示:本文包含一些參照結(jié)果,但它們并不意味著絕對(duì)精確,也沒有進(jìn)行均差分析及多次的測(cè)試。這些結(jié)果的目的是給出運(yùn)行時(shí)統(tǒng)計(jì),來幫助我們認(rèn)識(shí)到通常來說用什么會(huì)更快。所有的測(cè)試基于 iPhone 5s,使用 Xcode 5.1b1 和 iOS 7.1b1 的 64 位程序。編譯選項(xiàng)設(shè)置為 -Ofast 的發(fā)布構(gòu)建。Vectorize loops 和 unroll loops (默認(rèn)設(shè)置) 均設(shè)置為關(guān)閉。
首先,我們需要一些理論知識(shí)。效率通常用大 O 符號(hào)描述。它定義了一個(gè)函數(shù)的極限特征,通常被用于描繪其算法效率。O 定義了函數(shù)增長(zhǎng)率的上限。不同量級(jí)的差異非常巨大,可以看看通常使用的 O 符號(hào)的量級(jí)以及它們所對(duì)應(yīng)需要的操作數(shù)的關(guān)系。
http://wiki.jikexueyuan.com/project/objc/images/7-1.png" alt="" />
例如,如果用算法復(fù)雜度為 O(n^2)的算法對(duì)一個(gè)有 50 個(gè)元素的數(shù)組排序,需要 2,500 步的操作。而且,還有內(nèi)部的系統(tǒng)開銷和方法調(diào)用 — 所以是 250 0個(gè)操作的時(shí)間常量。 O(1)是理想的復(fù)雜度,代表著恒定的時(shí)間。好的排序算法通常需要 O(n*log n) 的時(shí)間。
大多數(shù)的集合類存在兩個(gè)版本:可變和不可變(默認(rèn))。這和其他大多數(shù)的框架有非常大的不同,一開始會(huì)讓人覺得有一點(diǎn)奇怪。然而其他的框架現(xiàn)在也應(yīng)用了這一特性:就在幾個(gè)月前,.NET公布了作為官方擴(kuò)展的不可變集合。
最大的好處是什么?線程安全。不可變的集合完全是線程安全的,可以同時(shí)在多個(gè)線程中迭代,避免各種轉(zhuǎn)變時(shí)出現(xiàn)異常的風(fēng)險(xiǎn)。你的 API 絕不應(yīng)該暴露一個(gè)可變的集合。
當(dāng)然從不可變到可變?nèi)缓笤倩貋硎菚?huì)有一定代價(jià)的 — 對(duì)象必須被拷貝兩次,所有集合內(nèi)的對(duì)象將被 retain/release。有時(shí)在內(nèi)部使用一個(gè)可變的集合,而在訪問時(shí)返回一個(gè)不可變的對(duì)象副本會(huì)更高效。
與其他框架不同的是,蘋果沒有提供一個(gè)線程安全的可變集合,NSCache
是例外,但它真的算不上是集合類,因?yàn)樗皇且粋€(gè)通用的容器。大多數(shù)時(shí)候,你不會(huì)需要在集合層級(jí)的同步特性。想象一段代碼,作用是檢查字典中一個(gè) key 是否存在,并根據(jù)檢查結(jié)果決定設(shè)置一個(gè)新的 key 或者返回某些值 — 你通常需要把多個(gè)操作歸類,這時(shí)線程安全的可變集合并不能對(duì)你有所幫助。
其實(shí)也有一些同步的,線程安全的可以使用的可變集合案例,它們往往只需要用幾行代碼,通過子類和組合的方法建立,比如這個(gè) NSDictionary
或這個(gè) NSArray
。
需要注意的是,一些較新的集合類,如 NSHashTable
,NSMapTable
和 NSPointerArray
默認(rèn)就是可變的,它們并沒有對(duì)應(yīng)的不可變的類。它們用于類的內(nèi)部使用,你基本應(yīng)該不會(huì)能找到需要它們的不可變版本的應(yīng)用場(chǎng)景。
NSArray
作為一個(gè)存儲(chǔ)對(duì)象的有序集合,可能是被使用最多的集合類。這也是為什么它有自己的比原來的 [NSArray arrayWithObjects:..., nil]
簡(jiǎn)短得多的快速語(yǔ)法糖符號(hào) @[...]
。
NSArray
實(shí)現(xiàn)了 objectAtIndexedSubscript:
,因?yàn)槲覀兛梢允褂妙?C 的語(yǔ)法 array[0]
來代替原來的 [array objectAtIndex:0]
。
關(guān)于 NSArray
的內(nèi)容比你想象的要多的多。基于存儲(chǔ)對(duì)象的多少,它使用各種內(nèi)部的變體。最有趣的部分是蘋果對(duì)于個(gè)別的對(duì)象訪問并不保證 O(1) 的訪問時(shí)間 — 正如你在 CFArray.h CoreFoundation 頭文件中的關(guān)于算法復(fù)雜度的注解中可以讀到的:
對(duì)于 array 中值的訪問時(shí)間,不管是在現(xiàn)在還是將來,我們保證在任何一種實(shí)現(xiàn)下最壞情況是 O(lg N)。但是通常來說它會(huì)是 O(1) (常數(shù)時(shí)間)。線性搜索操作很可能在最壞情況下的復(fù)雜度為 O(N*lg N),但通常來說上限會(huì)更小一些。插入和刪除操作耗時(shí)通常和數(shù)組中的值的數(shù)量成線性關(guān)系。但在某些實(shí)現(xiàn)的最壞情況下會(huì)是 O(N*lg N) 。在數(shù)組中,沒有對(duì)于性能上特別有優(yōu)勢(shì)的數(shù)據(jù)位置,也就是說,為了更快地訪問到元素而將其設(shè)為在較低的 index 上,或者在較高的 index 上進(jìn)行插入和刪除,或者類似的一些做法,是沒有必要的。
在測(cè)量的時(shí)候,NSArray
產(chǎn)生了一些有趣的額外的性能特征。在數(shù)組的開頭和結(jié)尾插入/刪除元素通常是一個(gè) O(1)操作,而隨機(jī)的插入/刪除通常是 O(N) 的。
NSArray
的大多數(shù)方法使用 isEqual:
來檢查對(duì)象間的關(guān)系(例如 containsObject:
中)。有一個(gè)特別的方法 indexOfObjectIdenticalTo:
用來檢查指針相等,如果你確保在同一個(gè)集合中搜索,那么這個(gè)方法可以很大的提升搜索速度。
在 iOS 7 中,我們最終得到了與 lastObject
對(duì)應(yīng)的公開的 firstObject
方法,對(duì)于空數(shù)組,這兩個(gè)方法都會(huì)返回 nil
— 而常規(guī)的訪問方法會(huì)拋出一個(gè) NSRangeException
異常。
關(guān)于構(gòu)造(可變)數(shù)組有一個(gè)漂亮的細(xì)節(jié)可以節(jié)省代碼量。如果你通過一個(gè)可能為 nil 的數(shù)組創(chuàng)建一個(gè)可變數(shù)組,通常會(huì)這么寫:
NSMutableArray *mutableObjects = [array mutableCopy];
if (!mutableObjects) {
mutableObjects = [NSMutableArray array];
}
或者通過更簡(jiǎn)潔的三元運(yùn)算符:
NSMutableArray *mutableObjects = [array mutableCopy] ?: [NSMutableArray array];
更好的解決方案是使用arrayWithArray:
,即使原數(shù)組為nil,該方法也會(huì)返回一個(gè)數(shù)組對(duì)象:
NSMutableArray *mutableObjects = [NSMutableArray arrayWithArray:array];
這兩個(gè)操作在效率上幾乎相等。使用 copy
會(huì)快一點(diǎn)點(diǎn),不過話說回來,這不太可能是你應(yīng)用的瓶頸所在。提醒:不要使用 [@[] mutableCopy]
。經(jīng)典的[NSMutableArray array]
可讀性更好。
逆序一個(gè)數(shù)組非常簡(jiǎn)單:array.reverseObjectEnumerator.allObjects
。我們使用系統(tǒng)提供的 reverseObjectEnumerator
,每一個(gè) NSEnumerator
都實(shí)現(xiàn)了 allObjects
,該方法返回一個(gè)新數(shù)組。雖然沒有原生的 randomObjectEnumerator
方法,你可以寫一個(gè)自定義的打亂數(shù)組順序的枚舉器或者使用一些出色的開源代碼。
有很多各種各樣的方法來對(duì)一個(gè)數(shù)組排序。如果數(shù)組存儲(chǔ)的是字符串對(duì)象,sortedArrayUsingSelector:
是第一選擇:
NSArray *array = @[@"John Appleseed", @"Tim Cook", @"Hair Force One", @"Michael Jurewitz"];
NSArray *sortedArray = [array sortedArrayUsingSelector:@selector(localizedCaseInsensitiveCompare:)];
下面的代碼對(duì)存儲(chǔ)數(shù)字的內(nèi)容同樣很好,因?yàn)?NSNumber
實(shí)現(xiàn)了 compare:
:
NSArray *numbers = @[@9, @5, @11, @3, @1];
NSArray *sortedNumbers = [numbers sortedArrayUsingSelector:@selector(compare:)];
如果想更可控,可以使用基于函數(shù)指針的排序方法:
- (NSData *)sortedArrayHint;
- (NSArray *)sortedArrayUsingFunction:(NSInteger (*)(id, id, void *))comparator
context:(void *)context;
- (NSArray *)sortedArrayUsingFunction:(NSInteger (*)(id, id, void *))comparator
context:(void *)context hint:(NSData *)hint;
蘋果增加了一個(gè)方法來加速使用 sortedArrayHint
的排序。
hinted sort 方式在你有一個(gè)已排序的大數(shù)組 (N 個(gè)元素) 并且只改變其中一小部分(P 個(gè)添加和刪除,這里 P遠(yuǎn)小于 N)時(shí),會(huì)非常有效。你可以重用原來的排序結(jié)果,然后在 N 個(gè)老項(xiàng)目和 P 個(gè)新項(xiàng)目進(jìn)行一個(gè)概念上的歸并排序。為了得到合適的 hint,你應(yīng)該在原來的數(shù)組排序后使用 sortedArrayHint 來在你需要的時(shí)候(比如在數(shù)組改變后想重新排序時(shí))保證持有它。
因?yàn)閎lock的引入,也出現(xiàn)了一些基于block的排序方法:
- (NSArray *)sortedArrayUsingComparator:(NSComparator)cmptr;
- (NSArray *)sortedArrayWithOptions:(NSSortOptions)opts
usingComparator:(NSComparator)cmptr;
性能上來說,不同的方法間并沒有太多的不同。有趣的是,基于 selector 的方式是最快的。你可以在 GitHub 上找到測(cè)試用的源代碼:
Sorting 1000000 elements. selector: 4947.90[ms] function: 5618.93[ms] block: 5082.98[ms].
NSArray
從 iOS 4 / Snow Leopard 開始內(nèi)置了二分查找
typedef NS_OPTIONS(NSUInteger, NSBinarySearchingOptions) {
NSBinarySearchingFirstEqual = (1UL << 8),
NSBinarySearchingLastEqual = (1UL << 9),
NSBinarySearchingInsertionIndex = (1UL << 10),
};
- (NSUInteger)indexOfObject:(id)obj
inSortedRange:(NSRange)r
options:(NSBinarySearchingOptions)opts
usingComparator:(NSComparator)cmp;
為什么要使用這個(gè)方法?類似 containsObject:
和 indexOfObject:
這樣的方法從 0 索引開始搜索每個(gè)對(duì)象直到找到目標(biāo) — 這樣不需要數(shù)組被排序,但是卻是 O(n)的效率特性。如果使用二分查找的話,需要數(shù)組事先被排序,但在查找時(shí)只需要 O(log n) 的時(shí)間。因此,對(duì)于 一百萬(wàn)條記錄,二分查找法最多只需要 21 次比較,而傳統(tǒng)的線性查找則平均需要 500,000 次的比較。
這是個(gè)簡(jiǎn)單的衡量二分查找有多快的數(shù)據(jù):
Time to search for 1000 entries within 1000000 objects. Linear: 54130.38[ms]. Binary: 7.62[ms]
作為比較,查找 NSOrderedSet
中的指定索引花費(fèi) 0.23 毫秒 — 就算和二分查找相比也又快了 30 多倍。
記住排序的開銷也是昂貴的。蘋果使用復(fù)雜度為 O(n*log n) 的歸并排序,所以如果你執(zhí)行一次 indexOfObject:
的話,就沒有必要使用二分查找了。
通過指定 NSBinarySearchingInsertionIndex
,你可以獲得正確的插入索引,以確保在插入元素后仍然可以保證數(shù)組的順序。
作為測(cè)試,我們來看一個(gè)普通的使用場(chǎng)景。從一個(gè)數(shù)組中過濾出一些元素組成另一個(gè)數(shù)組。這些測(cè)試都包括了枚舉的方法以及使用 API 進(jìn)行過濾的方式:
// 第一種方式,使用 `indexesOfObjectsWithOptions:passingTest:`.
NSIndexSet *indexes = [randomArray indexesOfObjectsWithOptions:NSEnumerationConcurrent
passingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) {
return testObj(obj);
}];
NSArray *filteredArray = [randomArray objectsAtIndexes:indexes];
// 使用 predicate 過濾,包括 block 的方式和文本 predicate 的方式
NSArray *filteredArray2 = [randomArray filteredArrayUsingPredicate:[NSPredicate predicateWithBlock:^BOOL(id obj, NSDictionary *bindings) {
return testObj(obj);
}]];
// 基于 block 的枚舉
NSMutableArray *mutableArray = [NSMutableArray array];
[randomArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) {
if (testObj(obj)) {
[mutableArray addObject:obj];
}
}];
// 傳統(tǒng)的枚舉
NSMutableArray *mutableArray = [NSMutableArray array];
for (id obj in randomArray) {
if (testObj(obj)) {
[mutableArray addObject:obj];
}
}
// 使用 NSEnumerator,傳統(tǒng)學(xué)院派
NSMutableArray *mutableArray = [NSMutableArray array];
NSEnumerator *enumerator = [randomArray objectEnumerator];
id obj = nil;
while ((obj = [enumerator nextObject]) != nil) {
if (testObj(obj)) {
[mutableArray addObject:obj];
}
}
// 通過下標(biāo)使用 objectAtIndex:
NSMutableArray *mutableArray = [NSMutableArray array];
for (NSUInteger idx = 0; idx < randomArray.count; idx++) {
id obj = randomArray[idx];
if (testObj(obj)) {
[mutableArray addObject:obj];
}
}
枚舉方法 / 時(shí)間 [ms] | 10.000.000 elements | 10.000 elements |
---|---|---|
indexesOfObjects: , concurrent |
1844.73 | 2.25 |
NSFastEnumeration (for in ) |
3223.45 | 3.21 |
indexesOfObjects: |
4221.23 | 3.36 |
enumerateObjectsUsingBlock: |
5459.43 | 5.43 |
objectAtIndex: |
5282.67 | 5.53 |
NSEnumerator |
5566.92 | 5.75 |
filteredArrayUsingPredicate: |
6466.95 | 6.31 |
為了更好的理解這里的效率測(cè)量,我們首先看一下數(shù)組是如何迭代的。
indexesOfObjectsWithOptions:passingTest:
必須每次都執(zhí)行一次 block 因此比傳統(tǒng)的使用 NSFastEnumeration
技術(shù)的基于 for 循環(huán)的枚舉要稍微低效一些。但是如果開啟了并發(fā)枚舉,那么前者的速度則會(huì)大大的超過后者幾乎 2 倍。iPhone 5s 是雙核的,所以這說得通。這里并沒有體現(xiàn)出來的是 NSEnumerationConcurrent
只對(duì)大量的對(duì)象有意義,如果你的集合中的對(duì)象數(shù)量很少,用哪個(gè)方法就真的無關(guān)緊要。甚至 NSEnumerationConcurrent
上額外的線程管理實(shí)際上會(huì)使結(jié)果變得更慢。
最大的輸家是 filteredArrayUsingPredicate:
。NSPredicate
需要在這里提及是因?yàn)?,人們可以寫?a rel="nofollow" >非常復(fù)雜的表達(dá)式,尤其是用不基于 block 的變體。使用 Core Data 的用戶應(yīng)該會(huì)很熟悉。
為了比較的完整,我們也加入了 NSEnumerator
作為比較 — 雖然沒有任何理由再使用它了。然而它竟出人意料的快(至少還是比基于 NSPredicate
的過濾要快),它的運(yùn)行時(shí)消耗無疑比快速枚舉更多 — 現(xiàn)在它只用于向后兼容。甚至沒有優(yōu)化過的 objectAtIndex:
都要更快些。
在OSX 10.5和iOS的最初版本中,蘋果增加了 NSFastEnumeration
。在此之前,只有每次返回一個(gè)元素的 NSEnumeration
,每次迭代都有運(yùn)行時(shí)開銷。而快速枚舉,蘋果通過 countByEnumeratingWithState:objects:count:
返回一個(gè)數(shù)據(jù)塊。該數(shù)據(jù)塊被解析成 id
類型的 C 數(shù)組。這就是更快的速度的原因;迭代一個(gè) C 數(shù)組要快得多,而且可以被編譯器更深一步的優(yōu)化。手動(dòng)的實(shí)現(xiàn)快速枚舉是十分難辦的,所以蘋果的 FastEnumerationSample 是一個(gè)不錯(cuò)的開始,還有一篇 Mike Ash 的文章也很不錯(cuò)。
初始化NSArray
的時(shí)候,可以選擇指定數(shù)組的預(yù)期大小。在檢測(cè)的時(shí)候,結(jié)果是在效率上沒有差別 — 至少在統(tǒng)計(jì)誤差范圍內(nèi)的測(cè)量的時(shí)間幾乎相等。有消息透漏說實(shí)際上蘋果根本沒有使用這個(gè)參數(shù)。然而使用 arrayWithCapacity:
仍然好處,它可以作為一種隱性的文檔來幫助你理解代碼:
Adding 10.000.000 elements to NSArray. no count 1067.35[ms] with count: 1083.13[ms].
很少有理由去子類化基礎(chǔ)集合類。大多數(shù)時(shí)候,使用 CoreFoundation 級(jí)別的類并且自定義回調(diào)函數(shù)定制自定義行為是更好的解決方案。
創(chuàng)建一個(gè)大小寫不敏感的字典,一種方法是子類化 NSDictionary
并且自定義訪問方法,使其將字符串始終變?yōu)樾?或大寫),并對(duì)排序也做類似的修改。更快更好的解決方案是提供一組不同的 CFDictionaryKeyCallBacks
集,你可以提供自定義的 hash
和 isEqual:
回調(diào)。你可以在這里找到一個(gè)例子。這種方法的優(yōu)美之處應(yīng)該歸功于 toll-free 橋接),它仍然是一個(gè)簡(jiǎn)單的字典,因此可以被任何使用 NSDictionary
作為參數(shù)的API接受。
子類作用的一個(gè)例子是有序字典的用例。.NET 提供了一個(gè) SortedDictionary
,Java 有 TreeMap
,C++ 有 std::map
。雖然你可以使用 C++ 的 STL 容器,但卻無法使它自動(dòng)的 retain/release
,這會(huì)讓使用起來笨拙得多。因?yàn)?NSDictionary
是一個(gè)類簇,所以子類化跟人們想象的相比非常不同。這已經(jīng)超過了本文的討論范疇,這里有一個(gè)真實(shí)的有序字典的例子。
一個(gè)字典存儲(chǔ)任意的對(duì)象鍵值對(duì)。 由于歷史原因,初始化方法 [NSDictionary dictionaryWithObjectsAndKeys:object, key, nil]
使用了相反的值到鍵的順序,而新的快捷語(yǔ)法則從 key 開始,@{key : value, ...}
。
NSDictionary
中的鍵是被拷貝的并且需要是不變的。如果在一個(gè)鍵在被用于在字典中放入一個(gè)值后被改變的話,那么這個(gè)值就會(huì)變得無法獲取了。一個(gè)有趣的細(xì)節(jié)是,在 NSDictionary
中鍵是被 copy 的,但是在使用一個(gè) toll-free 橋接的 CFDictionary
時(shí)卻只會(huì)被 retain。CoreFoundation 類沒有通用的拷貝對(duì)象的方法,因此這時(shí)拷貝是不可能的(*)。這只適用于你使用 CFDictionarySetValue()
的時(shí)候。如果你是通過 setObject:forKey
來使用一個(gè) toll-free 橋接的 CFDictionary
的話,蘋果會(huì)為其增加額外處理邏輯,使得鍵被拷貝。但是反過來這個(gè)結(jié)論則不成立 — 使用已經(jīng)轉(zhuǎn)換為 CFDictionary
的 NSDictionary
對(duì)象,并用對(duì)其使用 CFDictionarySetValue()
方法,還是會(huì)導(dǎo)致調(diào)用回 setObject:forKey
并對(duì)鍵進(jìn)行拷貝。
(*)其實(shí)有一個(gè)現(xiàn)成的鍵的回調(diào)函數(shù)
kCFCopyStringDictionaryKeyCallBacks
可以拷貝字符串,因?yàn)閷?duì)于 ObjC對(duì)象來說,CFStringCreateCopy()
會(huì)調(diào)用[NSObject copy]
,我們可以巧妙使用這個(gè)回調(diào)來創(chuàng)建一個(gè)能進(jìn)行鍵拷貝的CFDictionary
。
蘋果在定義字典的計(jì)算復(fù)雜度時(shí)顯得相當(dāng)?shù)驼{(diào)。唯一的信息可以在 CFDictionary
的頭文件中找到:
對(duì)于字典中值的訪問時(shí)間,不管是在現(xiàn)在還是將來,我們保證在任何一種實(shí)現(xiàn)下最壞情況是 O(N)。但通常來說它會(huì)是 O(1) (常數(shù)時(shí)間)。插入和刪除操作一般來說也會(huì)是常數(shù)時(shí)間,但是在某些實(shí)現(xiàn)中最壞情況將為 O(N*N)。通過鍵來訪問值將比直接訪問值要快(如果你有這樣的操作要做的話)。對(duì)于同樣數(shù)目的值,字典需要花費(fèi)比數(shù)組多得多的內(nèi)存空間。
跟數(shù)組相似的,字典根據(jù)尺寸的不同使用不同的實(shí)現(xiàn),并在其中無縫切換。
過濾字典有幾個(gè)不同的方法:
// 使用 keysOfEntriesWithOptions:passingTest:,可并行
NSSet *matchingKeys = [randomDict keysOfEntriesWithOptions:NSEnumerationConcurrent
passingTest:^BOOL(id key, id obj, BOOL *stop)
{
return testObj(obj);
}];
NSArray *keys = matchingKeys.allObjects;
NSArray *values = [randomDict objectsForKeys:keys notFoundMarker:NSNull.null];
__unused NSDictionary *filteredDictionary = [NSDictionary dictionaryWithObjects:values
forKeys:keys];
// 基于 block 的枚舉
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
[randomDict enumerateKeysAndObjectsUsingBlock:^(id key, id obj, BOOL *stop) {
if (testObj(obj)) {
mutableDictionary[key] = obj;
}
}];
// NSFastEnumeration
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
for (id key in randomDict) {
id obj = randomDict[key];
if (testObj(obj)) {
mutableDictionary[key] = obj;
}
}
// NSEnumeration
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
NSEnumerator *enumerator = [randomDict keyEnumerator];
id key = nil;
while ((key = [enumerator nextObject]) != nil) {
id obj = randomDict[key];
if (testObj(obj)) {
mutableDictionary[key] = obj;
}
}
// 基于 C 數(shù)組,通過 getObjects:andKeys: 枚舉
NSMutableDictionary *mutableDictionary = [NSMutableDictionary dictionary];
id __unsafe_unretained objects[numberOfEntries];
id __unsafe_unretained keys[numberOfEntries];
[randomDict getObjects:objects andKeys:keys];
for (int i = 0; i < numberOfEntries; i++) {
id obj = objects[i];
id key = keys[i];
if (testObj(obj)) {
mutableDictionary[key] = obj;
}
}
過濾/枚舉方法 | Time [ms], 50.000 elements | 1.000.000 elements |
---|---|---|
keysOfEntriesWithOptions: , concurrent |
16.65 | 425.24 |
getObjects:andKeys: |
30.33 | 798.49* |
keysOfEntriesWithOptions: |
30.59 | 856.93 |
enumerateKeysAndObjectsUsingBlock: |
36.33 | 882.93 |
NSFastEnumeration |
41.20 | 1043.42 |
NSEnumeration |
42.21 | 1113.08 |
(*)使用 getObjects:andKeys:
時(shí)需要注意。在上面的代碼例子中,我們使用了可變長(zhǎng)度數(shù)組這一 C99 特性(通常,數(shù)組的數(shù)量需要是一個(gè)固定值)。這將在棧上分配內(nèi)存,雖然更方便一點(diǎn),但卻有其限制。上面的代碼在元素?cái)?shù)量很多的時(shí)候會(huì)崩潰掉,所以我們使用基于 malloc/calloc
的分配 (和 free
) 以確保安全。
為什么這次 NSFastEnumeration
這么慢?迭代字典通常需要鍵和值兩者,快速枚舉只能枚舉鍵,我們必須每次都自己獲取值。使用基于 block 的 enumerateKeysAndObjectsUsingBlock:
更高效,因?yàn)閮烧叨伎梢愿咝У谋惶崆矮@取。
這次測(cè)試的勝利者又是通過 keysOfEntriesWithOptions:passingTest:
和 objectsForKeys:notFoundMarker:
的并發(fā)迭代。代碼稍微多了一點(diǎn),但是可以用 category 進(jìn)行漂亮的封裝。
到現(xiàn)在你應(yīng)該已經(jīng)知道該如何測(cè)試了,簡(jiǎn)單的回答是不,count
參數(shù)沒有改變?nèi)魏问虑?
Adding 10000000 elements to NSDictionary. no count 10786.60[ms] with count: 10798.40[ms].
關(guān)于字典排序沒有太多可說的。你只能將鍵數(shù)組排序?yàn)橐粋€(gè)新對(duì)象,因此你可以使用任何正規(guī)的 NSArray
的排序方法:
- (NSArray *)keysSortedByValueUsingSelector:(SEL)comparator;
- (NSArray *)keysSortedByValueUsingComparator:(NSComparator)cmptr;
- (NSArray *)keysSortedByValueWithOptions:(NSSortOptions)opts
usingComparator:(NSComparator)cmptr;
從 iOS 6 和 OS X 10.8 開始,新建的字典可以使用一個(gè)預(yù)先生成好的鍵集,使用 sharedKeySetForKeys:
從一個(gè)數(shù)組中創(chuàng)建鍵集,然后用 dictionaryWithSharedKeySet:
創(chuàng)建字典。共享鍵集會(huì)復(fù)用對(duì)象,以節(jié)省內(nèi)存。根據(jù) Foundation Release Notes,sharedKeySetForKeys:
中會(huì)計(jì)算一個(gè)最小完美哈希,這個(gè)哈希值可以取代字典查找過程中探索循環(huán)的需要,因此使鍵的訪問更快。
雖然在我們有限的測(cè)試中沒有法線蘋果在 NSJSONSerialization
中使用這個(gè)特性,但毫無疑問,在處理 JSON 的解析工作時(shí)這個(gè)特性可以發(fā)揮得淋漓盡致。(使用共享鍵集創(chuàng)建的字典是 NSSharedKeyDictionary
的子類;通常的字典是 __NSDictionaryI
/ __NSDictionaryM
,I / M 表明可變性;可變和不可變的的字典在 toll-free 橋接后對(duì)應(yīng)的都是 _NSCFDictionary
類。)
有趣的細(xì)節(jié):共享鍵字典始終是可變的,即使對(duì)它們執(zhí)行了”copy”命令后也是。這個(gè)行為文檔中并沒有說明,但很容易被測(cè)試:
id sharedKeySet = [NSDictionary sharedKeySetForKeys:@[@1, @2, @3]]; // 返回 NSSharedKeySet
NSMutableDictionary *test = [NSMutableDictionary dictionaryWithSharedKeySet:sharedKeySet];
test[@4] = @"First element (not in the shared key set, but will work as well)";
NSDictionary *immutable = [test copy];
NSParameterAssert(immutable.count == 1);
((NSMutableDictionary *)immutable)[@5] = @"Adding objects to an immutable collection should throw an exception.";
NSParameterAssert(immutable.count == 2);
NSSet
和它的可變變體 NSMutableSet
是無序?qū)ο蠹稀z查一個(gè)對(duì)象是否存在通常是一個(gè) O(1) 的操作,使得比 NSArray
快很多。NSSet
只在被使用的哈希方法平衡的情況下能高效的工作;如果所有的對(duì)象都在同一個(gè)哈??饍?nèi),NSSet
在查找對(duì)象是否存在時(shí)并不比 NSArray
快多少。
NSSet
還有變體 NSCountedSet
,以及非 toll-free 計(jì)數(shù)變體 CFBag
/ CFMutableBag
。
NSSet
會(huì) retain 它其中的對(duì)象,但是根據(jù) set 的規(guī)定,對(duì)象應(yīng)該是不可變的。添加一個(gè)對(duì)象到 set 中隨后改變它會(huì)導(dǎo)致一些奇怪的問題并破壞 set 的狀態(tài)。
NSSet
的方法比 NSArray
少的多。沒有排序方法,但有一些方便的枚舉方法。重要的方法有 allObjects
,將對(duì)象轉(zhuǎn)化為 NSArray
,anyObject
則返回任意的對(duì)象,如果 set 為空,則返回 nil。
NSMutableSet
有幾個(gè)很強(qiáng)大的方法,例如 intersectSet:
,minusSet:
和 unionSet:
。
http://wiki.jikexueyuan.com/project/objc/images/7-2.png" alt="" />
我們?cè)僖淮螠y(cè)試當(dāng)創(chuàng)建 set 時(shí)給定容量大小是否會(huì)有顯著的速度差異:
Adding 1.000.000 elements to NSSet. no count 2928.49[ms] with count: 2947.52[ms].
在統(tǒng)計(jì)誤差范圍內(nèi),結(jié)果沒有顯著差異。有一份證據(jù)表明至少在上一個(gè) runtime 版本中,有很多的性能上的影響。
蘋果在 CFSet 頭文件中沒有提供任何關(guān)于算法復(fù)雜度的注釋。
類 / 時(shí)間 [ms] | 1.000.000 elements |
---|---|
NSMutableSet , adding |
2504.38 |
NSMutableArray , adding |
1413.38 |
NSMutableSet , random access |
4.40 |
NSMutableArray , random access |
7.95 |
這個(gè)檢測(cè)非常符合我們的預(yù)期:NSSet
在每一個(gè)被添加的對(duì)象上執(zhí)行 hash
和 isEqual:
方法并管理一系列哈希值,所以在添加元素時(shí)耗費(fèi)了更多的時(shí)間。set的隨機(jī)訪問比較難以測(cè)試,因?yàn)檫@里執(zhí)行的都是 anyObject
。
這里沒有必要包含 containsObject:
的測(cè)試,set 要快幾個(gè)數(shù)量級(jí),畢竟這是它的特點(diǎn)。
NSOrderedSet
在 iOS 5 和 Mac OS X 10.7 中第一次被引入,除了 Core Data,幾乎沒有直接使用它的 API??瓷先ニC合了 NSArray
和 NSSet
兩者的好處,對(duì)象查找,對(duì)象唯一性,和快速隨機(jī)訪問。
NSOrderedSet
有著優(yōu)秀的 API 方法,使得它可以很便利的與其他 set 或者有序 set 對(duì)象合作。合并,交集,差集,就像 NSSet
支持的那樣。它有 NSArray
中除了比較陳舊的基于函數(shù)的排序方法和二分查找以外的大多數(shù)排序方法。畢竟 containsObject:
非???,所以沒有必要再用二分查找了。
NSOrderedSet
的 array
和 set
方法分別返回一個(gè) NSArray
和 NSSet
,這些對(duì)象表面上是不可變的對(duì)象,但實(shí)際上在 NSOrderedSet 更新的時(shí)候,它們也會(huì)更新自己。如果你在不同線程上使用這些對(duì)象并發(fā)生了詭異異常的時(shí)候,知道這一點(diǎn)是非常有好處的。本質(zhì)上,這些類使用的是 __NSOrderedSetSetProxy
和 __NSOrderedSetArrayProxy
。
附注:如果你想知道為什么 NSOrderedSet
不是 NSSet
的子類,NSHipster 上有一篇非常好的文章解釋了可變/不可變類簇的缺點(diǎn)。
如果你看到這份測(cè)試,你就會(huì)知道 NSOrderedSet
代價(jià)高昂了,畢竟天下沒有免費(fèi)的午餐:
類 / 時(shí)間 [ms] | 1.000.000 elements |
---|---|
NSMutableOrderedSet , adding |
3190.52 |
NSMutableSet , adding |
2511.96 |
NSMutableArray , adding |
1423.26 |
NSMutableOrderedSet , random access |
10.74 |
NSMutableSet , random access |
4.47 |
NSMutableArray , random access |
8.08 |
這個(gè)測(cè)試在每一個(gè)集合類中添加自定義字符串,隨后隨機(jī)訪問它們。
NSOrderedSet
比 NSSet
和 NSArray
占用更多的內(nèi)存,因?yàn)樗枰瑫r(shí)維護(hù)哈希值和索引。
NSHashTable
效仿了 NSSet
,但在對(duì)象/內(nèi)存處理時(shí)更加的靈活。可以通過自定義 CFSet
的回調(diào)獲得 NSHashTable
的一些特性,哈希表可以保持對(duì)對(duì)象的弱引用并在對(duì)象被銷毀之后正確的將其移除,有時(shí)候如果手動(dòng)在 NSSet 中添加的話,想做到這個(gè)是挺惡心的一件事。它是默認(rèn)可變的 — 并且這個(gè)類沒有相應(yīng)的不可變版本。
NSHashTable
有 ObjC 和原始的 C API,C API 可以用來存儲(chǔ)任意對(duì)象。蘋果在 10.5 Leopard 系統(tǒng)中引入了這個(gè)類,但是 iOS 的話直到最近的 iOS 6 中才被加入。足夠有趣的是它們只移植了 ObjC API;更多強(qiáng)大的 C API 沒有包括在 iOS 中。
NSHashTable
可以通過 initWithPointerFunctions:capacity:
進(jìn)行大量的設(shè)置 — 我們只選取使用預(yù)先定義的 hashTableWithOptions:
這一最普遍的使用場(chǎng)景。其中最有用的選項(xiàng)有利用 weakObjectsHashTable
來使用其自身的構(gòu)造函數(shù)。
這些指針函數(shù)可以被用在 NSHashTable
,NSMapTable
和 NSPointerArray
中,定義了對(duì)存儲(chǔ)在這個(gè)集合中的對(duì)象的獲取和保留行為。這里只介紹最有用的選項(xiàng)。完整列表參見 NSPointerFunctions.h
。
有兩組選項(xiàng)。內(nèi)存選項(xiàng)決定了內(nèi)存管理,個(gè)性化定義了哈希和相等。
NSPointerFunctionsStrongMemory
創(chuàng)建了一個(gè)r etain/release 對(duì)象的集合,非常像常規(guī)的 NSSet
或 NSArray
。
NSPointerFunctionsWeakMemory
使用和 __weak
等價(jià)的方式來存儲(chǔ)對(duì)象并自動(dòng)移除被銷毀的對(duì)象。
NSPointerFunctionsCopyIn
在對(duì)象被加入到集合前拷貝它們。
NSPointerFunctionsObjectPersonality
使用對(duì)象的 hash
和 isEqual:
(默認(rèn))。
NSPointerFunctionsObjectPointerPersonality
對(duì)于 isEqual:
和 hash
使用直接的指針比較。
類 / 時(shí)間 [ms] | 1.000.000 elements |
---|---|
NSHashTable , adding |
2511.96 |
NSMutableSet , adding |
1423.26 |
NSHashTable , random access |
3.13 |
NSMutableSet , random access |
4.39 |
NSHashTable , containsObject |
6.56 |
NSMutableSet , containsObject |
6.77 |
NSHashTable , NSFastEnumeration |
39.03 |
NSMutableSet , NSFastEnumeration |
30.43 |
如果你只是需要 NSSet
的特性,請(qǐng)堅(jiān)持使用 NSSet
。NSHashTable
在添加對(duì)象時(shí)花費(fèi)了將近2倍的時(shí)間,但是其他方面的效率卻非常相近。
NSMapTable
和 NSHashTable
相似,但是效仿的是 NSDictionary
。因此,我們可以通過 mapTableWithKeyOptions:valueOptions:
分別控制鍵和值的對(duì)象獲取/保留行為。存儲(chǔ)弱引用是 NSMapTable
最有用的特性,這里有4個(gè)方便的構(gòu)造函數(shù):
strongToStrongObjectsMapTable
weakToStrongObjectsMapTable
strongToWeakObjectsMapTable
weakToWeakObjectsMapTable
注意,除了使用 NSPointerFunctionsCopyIn
,任何的默認(rèn)行為都會(huì) retain (或弱引用)鍵對(duì)象而不會(huì)拷貝它,這與 CFDictionary
的行為相同而與 NSDictionary
不同。當(dāng)你需要一個(gè)字典,它的鍵沒有實(shí)現(xiàn) NSCopying
協(xié)議的時(shí)候(比如像 UIView
),這會(huì)非常有用。
如果你好奇為什么蘋果”忘記”為 NSMapTable
增加下標(biāo),你現(xiàn)在知道了。下標(biāo)訪問需要一個(gè) id<NSCopying>
作為 key,對(duì) NSMapTable
來說這不是強(qiáng)制的。如果不通過一個(gè)非法的 API 協(xié)議或者移除 NSCopying
協(xié)議來削弱全局下標(biāo),是沒有辦法給它增加下標(biāo)的。
你可以通過 dictionaryRepresentation
把內(nèi)容轉(zhuǎn)換為普通的 NSDictionary
。不像 NSOrderedSet
,這個(gè)方法返回的是一個(gè)常規(guī)的字典而不是一個(gè)代理。
類 / 時(shí)間 [ms] | 1.000.000 elements |
---|---|
NSMapTable , adding |
2958.48 |
NSMutableDictionary , adding |
2522.47 |
NSMapTable , random access |
13.25 |
NSMutableDictionary , random access |
9.18 |
NSMapTable
只比 NSDictionary
略微慢一點(diǎn)。如果你需要一個(gè)不 retain 鍵的字典,放棄 CFDictionary
而使用它吧。
NSPointerArray
類是一個(gè)稀疏數(shù)組,工作起來與 NSMutableArray
相似,但可以存儲(chǔ) NULL
值,并且 count
方法會(huì)反應(yīng)這些空點(diǎn)??梢杂?NSPointerFunctions
對(duì)其進(jìn)行各種設(shè)置,也有應(yīng)對(duì)常見的使用場(chǎng)景的快捷構(gòu)造函數(shù) strongObjectsPointerArray
和 weakObjectsPointerArray
。
在能使用 insertPointer:atIndex:
之前,我們需要通過直接設(shè)置 count
屬性來申請(qǐng)空間,否則會(huì)產(chǎn)生一個(gè)異常。另一種選擇是使用 addPointer:
,這個(gè)方法可以自動(dòng)根據(jù)需要增加數(shù)組的大小。
你可以通過 allObjects
將一個(gè) NSPointerArray
轉(zhuǎn)換成常規(guī)的 NSArray
。這時(shí)所有的 NULL
值會(huì)被去掉,只有真正存在的對(duì)象被加入到數(shù)組 — 因此數(shù)組的對(duì)象索引很有可能會(huì)跟指針數(shù)組的不同。注意:如果向指針數(shù)組中存入任何非對(duì)象的東西,試圖執(zhí)行 allObjects
都會(huì)造成 EXC_BAD_ACCESS
崩潰,因?yàn)樗鼤?huì)一個(gè)一個(gè)地去 retain ”對(duì)象”。
從調(diào)試的角度講,NSPointerArray
沒有受到太多歡迎。description
方法只是簡(jiǎn)單的返回了<NSConcretePointerArray: 0x17015ac50>
。為了得到所有的對(duì)象需要執(zhí)行[pointerArray allObjects]
,當(dāng)然,如果存在NULL
的話會(huì)改變索引。
在性能方面, NSPointerArray
真的非常非常慢,所以當(dāng)你打算在一個(gè)很大的數(shù)據(jù)集合上使用它的時(shí)候一定要三思。在本測(cè)試中我們比較了使用 NSNull
作為空標(biāo)記的 NSMutableArray
,而對(duì) NSPointerArray
我們用 NSPointerFunctionsStrongMemory
來進(jìn)行設(shè)置 (這樣對(duì)象會(huì)被適當(dāng)?shù)?retain)。在一個(gè)有 10,000 個(gè)元素的數(shù)組中,我們每隔十個(gè)插入一個(gè)字符串 ”Entry %d”。此測(cè)試包括了用 NSNull.null
填充 NSMutableArray
的總時(shí)間。對(duì)于 NSPointerArray
,我們使用 setCount:
來代替:
類 / 時(shí)間 [ms] | 10.000 elements |
---|---|
NSMutableArray , adding |
15.28 |
NSPointerArray , adding |
3851.51 |
NSMutableArray , random access |
0.23 |
NSPointerArray , random access |
0.34 |
注意 NSPointerArray
需要的時(shí)間比 NSMutableArray
多了超過 250 倍(!) 。這非常奇怪和意外。跟蹤內(nèi)存是比較困難的,所以按理說 NSPointerArray
會(huì)更高效才對(duì)。不過由于我們使用的是同一個(gè) NSNull
來標(biāo)記空對(duì)象,所以除了指針也沒有什么更多的消耗。
NSCache
是一個(gè)非常奇怪的集合。在 iOS 4 / Snow Leopa