OC中的基礎(chǔ)集合類

基礎(chǔ)集合類是每一門(mén)語(yǔ)言的基礎(chǔ)家肯,下面我們一起來(lái)對(duì)OC的基礎(chǔ)集合類進(jìn)行一個(gè)總結(jié)闷沥。

NSArray

NSArray作為一個(gè)存儲(chǔ)對(duì)象的有序集合与殃,可能是被使用最多的集合類该酗。這也是為什么它有自己的比原來(lái)的[NSArray arrayWithObjects:..., nil]簡(jiǎn)短得多的快速語(yǔ)法糖符號(hào)@[...]。

NSArray實(shí)現(xiàn)了objectAtIndexedSubscript:具滴,所以我們可以使用類C的語(yǔ)法array[0]來(lái)代替原來(lái)的[array objectAtIndex:0]凹嘲。

性能特征

關(guān)于NSArray的內(nèi)容比你想象的要多的多」乖希基于存儲(chǔ)對(duì)象的多少周蹭,它使用各種內(nèi)部的變體趋艘。最有趣的部分是蘋(píng)果對(duì)于個(gè)別的對(duì)象訪問(wèn)并不保證O(1)的訪問(wèn)時(shí)間 — 正如你在CFArray.h CoreFoundation header中的關(guān)于算法復(fù)雜度的注解中可以讀到的:

The access time for a value in the array is guaranteed to be at worst O(lg N) for any implementation, current and future, but will often be O(1) (constant time). Linear search operations similarly have a worst case complexity of O(Nlg N), though typically the bounds will be tighter, and so on. Insertion or deletion operations will typically be linear in the number of values in the array, but may be O(Nlg N) clearly in the worst case in some implementations. There are no favored positions within the array for performance; that is, it is not necessarily faster to access values with low indices, or to insert or delete values with high indices, or whatever.

在測(cè)量的時(shí)候,NSArray產(chǎn)生了一些有趣的額外的性能特征凶朗。在數(shù)組的開(kāi)頭和結(jié)尾插入/刪除元素通常是一個(gè)O(1)操作瓷胧,而隨機(jī)的插入/刪除通常是 O(N)的。

有用的方法
NSArray的大多數(shù)方法使用isEqual:來(lái)檢查對(duì)象間的關(guān)系(例如containsObject:)棚愤。有一個(gè)特別的方法indexOfObjectIdenticalTo:用來(lái)檢查指針相等抖单,如果你確保在同一個(gè)集合中搜索,那么這個(gè)方法可以很大的提升搜索速度遇八。

在iOS 7中矛绘,我們最終得到了與lastObject對(duì)應(yīng)的公開(kāi)的firstObject方法,對(duì)于空數(shù)組刃永,這兩個(gè)方法都會(huì)返回nil — 而常規(guī)的訪問(wèn)方法會(huì)拋出一個(gè)NSRangeException異常货矮。

翻轉(zhuǎn)一個(gè)數(shù)組非常簡(jiǎn)單:array.reverseObjectEnumerator.allObjects。我們使用系統(tǒng)提供的reverseObjectEnumerator斯够,每一個(gè)NSEnumerator都實(shí)現(xiàn)了allObjects囚玫,該方法返回一個(gè)新數(shù)組。雖然沒(méi)有原生的randomObjectEnumerator方法读规,你可以寫(xiě)一個(gè)自定義的打亂數(shù)組順序的枚舉器或者使用一些出色的開(kāi)源代碼抓督。

數(shù)組排序
有很多各種各樣的方法來(lái)對(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)镹SNumber實(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; 

因?yàn)閎lock的引入碍遍,也出現(xiàn)了一些基于block的排序方法:

- (NSArray *)sortedArrayUsingComparator:(NSComparator)cmptr; 
- (NSArray *)sortedArrayWithOptions:(NSSortOptions)opts 
                    usingComparator:(NSComparator)cmptr; 

二分查找
NSArray竟然內(nèi)置了二分查找定铜,這個(gè)讓我比較詫異!NSArray從iOS 4/Snow Leopard開(kāi)始內(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索引開(kāi)始搜索每個(gè)對(duì)象直到找到目標(biāo) — 不需要數(shù)組被排序而且是O(n)的效率特性怕敬。換句話說(shuō)揣炕,二分查找需要數(shù)組事先被排序,但只需要O(log n)的時(shí)間东跪。因此畸陡,對(duì)于1,000,000的記錄,二分查找法最多只需要21次比較虽填,而傳統(tǒng)的線性查找則平均需要5000,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多倍卤唉。
記住排序的開(kāi)銷也是昂貴的涩惑。蘋(píng)果使用復(fù)雜度為O(n*log n)的歸并排序仁期,所以如果執(zhí)行過(guò)indexOfObject:一次桑驱,就沒(méi)有必要使用二分查找了竭恬。

通過(guò)指定NSBinarySearchingInsertionIndex,你可以獲得正確的插入索引熬的,以確保在插入元素后仍然可以保證數(shù)組的順序。

枚舉和高階消息

作為參照,我們來(lái)看一個(gè)普通的使用場(chǎng)景蚊俺。從一個(gè)數(shù)組中過(guò)濾出另一個(gè)數(shù)組尿背。測(cè)試了多個(gè)枚舉方法和API特性:

// First variant, using `indexesOfObjectsWithOptions:passingTest:`. 
NSIndexSet *indexes = [randomArray indexesOfObjectsWithOptions:NSEnumerationConcurrent 
                                                   passingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop) { 
    return testObj(obj); 
}]; 
NSArray *filteredArray = [randomArray objectsAtIndexes:indexes]; 
 
// Filtering using predicates (block-based or text)     
NSArray *filteredArray2 = [randomArray filteredArrayUsingPredicate:[NSPredicate predicateWithBlock:^BOOL(id obj, NSDictionary *bindings) { 
    return testObj(obj); 
}]]; 
 
// Block-based enumeration  
NSMutableArray *mutableArray = [NSMutableArray array]; 
[randomArray enumerateObjectsUsingBlock:^(id obj, NSUInteger idx, BOOL *stop) { 
    if (testObj(obj)) { 
        [mutableArray addObject:obj]; 
    } 
}]; 
 
// Classic enumeration 
NSMutableArray *mutableArray = [NSMutableArray array]; 
for (id obj in randomArray) { 
    if (testObj(obj)) { 
        [mutableArray addObject:obj]; 
    } 
} 
 
// Using NSEnumerator, old school. 
NSMutableArray *mutableArray = [NSMutableArray array]; 
NSEnumerator *enumerator = [randomArray objectEnumerator]; 
id obj = nil; 
while ((obj = [enumerator nextObject]) != nil) { 
    if (testObj(obj)) { 
        [mutableArray addObject:obj]; 
    } 
} 
 
// Using objectAtIndex: (via subscripting) 
NSMutableArray *mutableArray = [NSMutableArray array]; 
for (NSUInteger idx = 0; idx < randomArray.count; idx++) { 
    id obj = randomArray[idx]; 
    if (testObj(obj)) { 
        [mutableArray addObject:obj]; 
    } 
} 

為了更好的理解這里的效率測(cè)量,我們首先看一下數(shù)組是如何迭代的橡伞。

indexesOfObjectsWithOptions:passingTest:必須每次都執(zhí)行一次block因此比傳統(tǒng)的使用NSFastEnumeration技術(shù)的基于for循環(huán)的枚舉要稍微低效一些盒揉。然后如果開(kāi)啟了并發(fā)枚舉,那么前者的速度則會(huì)大大的超過(guò)后者幾乎2倍兑徘。iPhone 5s是雙核的刚盈,所以這說(shuō)得通。這里并沒(méi)有體現(xiàn)出來(lái)的是NSEnumerationConcurrent只對(duì)大量的對(duì)象有意義挂脑,如果你的集合中的對(duì)象數(shù)量很少藕漱,用哪個(gè)方法就真的無(wú)關(guān)緊要。甚至NSEnumerationConcurrent上額外的線程管理實(shí)際上會(huì)使結(jié)果變得更慢崭闲。

最大的輸家是filteredArrayUsingPredicate:肋联。NSPredicate需要在這里提及是因?yàn)椋藗兛梢詫?xiě)出非常復(fù)雜的表達(dá)式刁俭,尤其是用不基于block的變體橄仍。使用Core Data的用戶應(yīng)該會(huì)很熟悉。

為了比較的完整牍戚,我們也加入了NSEnumerator作為比較 — 雖然沒(méi)有任何理由再使用它了沙兰。然而它竟出人意料的快(比基于NSPredicate的查找要快),它的運(yùn)行時(shí)消耗無(wú)疑比快速枚舉更多 — 現(xiàn)在它只用于向后兼容翘魄。甚至沒(méi)有優(yōu)化過(guò)的objectAtIndex:都要更快些鼎天。

NSFastEnumeration
在OSX 10.5和iOS的最初版本中,蘋(píng)果增加了NSFastEnumeration暑竟。在此之前斋射,只有每次返回一個(gè)元素的NSEnumeration,每次迭代都有運(yùn)行時(shí)開(kāi)銷但荤。而快速枚舉罗岖,蘋(píng)果通過(guò)countByEnumeratingWithState:objects:count:返回一個(gè)數(shù)據(jù)塊。該數(shù)據(jù)塊被解析成ids類型的C數(shù)組腹躁。這就是更快的速度的原因;迭代一個(gè)C數(shù)組更快桑包,而且可以被編譯器更深一步的優(yōu)化。手動(dòng)的實(shí)現(xiàn)快速枚舉是十分難辦的纺非,所以蘋(píng)果的FastEnumerationSample是一個(gè)不錯(cuò)的開(kāi)始哑了,還有一篇Mike Ash的文章也很不錯(cuò)赘方。

應(yīng)該用arrayWithCapacity:嗎?
初始化NSArray的時(shí)候,可以選擇指定數(shù)組的預(yù)期大小弱左。在檢測(cè)的時(shí)候窄陡,結(jié)果是在效率上沒(méi)有差別 — 測(cè)量的時(shí)間幾乎相等,且在統(tǒng)計(jì)不確定性的范圍內(nèi)拆火。有消息透漏說(shuō)實(shí)際上蘋(píng)果并沒(méi)有使用這個(gè)特性跳夭。然而使用arrayWithCapacity:仍然有用,在文檔不清晰的代碼中们镜,它可以幫助理解代碼:

Adding 10.000.000 elements to NSArray. no count 1067.35[ms] with count: 1083.13[ms]. 

NSDictionary

一個(gè)字典存儲(chǔ)任意的對(duì)象鍵值對(duì)币叹。 由于歷史原因,初始化方法使用相反的對(duì)象到值的方法模狭,[NSDictionary dictionaryWithObjectsAndKeys:object, key, nil]套硼,而新的快捷語(yǔ)法則從key開(kāi)始,@{key : value, ...}胞皱。

NSDictionary中的鍵是被拷貝的并且需要是恒定的邪意。如果在一個(gè)鍵在被用于在字典中放入一個(gè)值后被改變,那么這個(gè)值可能就會(huì)變得無(wú)法獲取了反砌。一個(gè)有趣的細(xì)節(jié)雾鬼,在NSDictionary中鍵是被拷貝的,而在使用一個(gè)toll-free橋接的CFDictionary時(shí)卻只被retain宴树。CoreFoundation類沒(méi)有通用對(duì)象的拷貝方法策菜,因此這時(shí)拷貝是不可能的(*)。這只適用于使用CFDictionarySetValue()的時(shí)候酒贬。如果通過(guò)setObject:forKey使用toll-free橋接的CFDictionary又憨,蘋(píng)果增加了額外處理邏輯來(lái)使鍵被拷貝。反過(guò)來(lái)這個(gè)結(jié)論則不成立 — 轉(zhuǎn)換為CFDictionary的NSDictionary對(duì)象锭吨,對(duì)其使用CFDictionarySetValue()方法會(huì)調(diào)用回setObject:forKey并拷貝鍵蠢莺。

(*)有一個(gè)現(xiàn)成的鍵的回調(diào)函數(shù)kCFCopyStringDictionaryKeyCallBacks會(huì)拷貝字符串,因?yàn)镃FStringCreateCopy()會(huì)調(diào)用[NSObject copy]零如,我們可以使用這個(gè)回調(diào)來(lái)創(chuàng)建一個(gè)拷貝鍵的CFDictionary躏将。

性能特征

蘋(píng)果在定義計(jì)算復(fù)雜度時(shí)顯得相當(dāng)安靜。關(guān)于它的唯一注釋可以在CFDictionary的頭文件中找到:

The access time for a value in the dictionary is guaranteed to be at worst O(N) for any implementation, current and future, but will often be O(1) (constant time). Insertion or deletion operations will typically be constant time as well, but are O(N*N) in the worst case in some implementations. Access of values through a key is faster than accessing values directly (if there are any such operations). Dictionaries will tend to use significantly more memory than a array with the same number of values.

跟數(shù)組相似的考蕾,字典根據(jù)尺寸的不同使用不同的實(shí)現(xiàn)祸憋,并在其中無(wú)縫切換。

枚舉和高階消息

過(guò)濾字典有幾個(gè)不同的方法:

  // Using keysOfEntriesWithOptions:passingTest:,optionally concurrent 
  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-based enumeration. 
  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-based array enumeration via 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; 
      } 
 } 

使用getObjects:andKeys:時(shí)需要注意肖卧。在上面的代碼例子中蚯窥,我們使用了可變長(zhǎng)度數(shù)組的C99特性(通常,數(shù)組的數(shù)量需要是一個(gè)固定值)。在棧上分配了內(nèi)存拦赠,雖然有限但是更方便一點(diǎn)巍沙。上面的代碼在有數(shù)量較大的元素的時(shí)候會(huì)崩潰掉,所以使用基于malloc/calloc的分配(和free)以確保安全矛紫。

為什么這次NSFastEnumeration這么慢?迭代字典通常需要鍵和值;快速枚舉只能枚舉鍵,我們必須每次都自己獲取值牌里。使用基于block的enumerateKeysAndObjectsUsingBlock:更高效颊咬,因?yàn)橹悼梢愿咝У谋惶崆矮@取。

這個(gè)測(cè)試的勝利者又是并發(fā)迭代keysOfEntriesWithOptions:passingTest:和objectsForKeys:notFoundMarker:牡辽。代碼稍微多了一點(diǎn)喳篇,但是可以用category進(jìn)行漂亮的封裝。

應(yīng)該用dictionaryWithCapacity:嗎?

到現(xiàn)在你應(yīng)該已經(jīng)知道該如何測(cè)試了态辛,簡(jiǎn)單的回答是不麸澜,count參數(shù)沒(méi)有改變?nèi)魏问虑?

 Adding 10000000 elements to NSDictionary. no count 10786.60[ms] with count: 10798.40[ms]. 

排序

關(guān)于字典排序沒(méi)有太多可說(shuō)的。你只能將鍵排序?yàn)橐粋€(gè)新對(duì)象奏黑,因此你可以使用任何正規(guī)的NSArray的排序方法:

1.   (NSArray *)keysSortedByValueUsingSelector:(SEL)comparator; 
2.   (NSArray *)keysSortedByValueUsingComparator:(NSComparator)cmptr; 
3.   (NSArray *)keysSortedByValueWithOptions:(NSSortOptions)opts 
4.   usingComparator:(NSComparator)cmptr; 

共享鍵

從iOS 6和OS X 10.8開(kāi)始炊邦,字典可以使用一個(gè)事先生成好的鍵集,使用sharedKeySetForKeys:從一個(gè)數(shù)組中創(chuàng)建鍵集熟史,用dictionaryWithSharedKeySet:創(chuàng)建字典馁害。共享鍵集會(huì)復(fù)用對(duì)象,以節(jié)省內(nèi)存蹂匹。根據(jù)Foundation Release Notes碘菜,sharedKeySetForKeys:中會(huì)計(jì)算一個(gè)最小最完美的哈希值,這個(gè)哈希值丟棄了字典查找過(guò)程中探索循環(huán)的需要限寞,因此使鍵的訪問(wèn)更快忍啸。

這在JSON解析的時(shí)候是完美的使用場(chǎng)景,雖然在我們有限的測(cè)試中無(wú)法看到蘋(píng)果在NSJSONSerialization中使用履植。(使用共享鍵集創(chuàng)建的字典是NSSharedKeyDictionary的子類;標(biāo)準(zhǔn)的字典是__NSDictionaryI/__NSDictionaryM计雌,I/M表明可變性;toll-free橋接的字典是_NSCFDictionary類,既是可變也是不可變的玫霎。)

NSSet

NSSet和它的可變變體NSMutableSet是無(wú)序?qū)ο蠹习追邸z查一個(gè)對(duì)象是否存在通常是一個(gè)O(1)的操作,使得比NSArray快很多鼠渺。NSSet只在被使用的哈希方法平衡的情況下能高效的工作;如果所有的對(duì)象都在同一個(gè)哈涎及停筐內(nèi),NSSet在查找對(duì)象是否存在時(shí)并不比NSArray快多少拦盹。

NSSet還有變體NSCountedSet鹃祖,non-toll-free計(jì)數(shù)變體CFBag/CFMutableBag。

NSSet會(huì)retain它其中的對(duì)象普舆,但是根據(jù)set的規(guī)定恬口,對(duì)象應(yīng)該是不可變的校读。添加一個(gè)對(duì)象到set中隨后改變它會(huì)導(dǎo)致一些奇怪的問(wèn)題并破壞set的狀態(tài)。

NSSet的方法比NSArray少的多祖能。沒(méi)有排序方法歉秫,但有一些方便的枚舉方法。重要的方法有allObjects养铸,將對(duì)象轉(zhuǎn)化為NSArray雁芙,anyObject則返回任意的對(duì)象,如果set為空钞螟,則返回nil兔甘。

Set操作

NSMutableSet有幾個(gè)很強(qiáng)大的方法,例如intersectSet:鳞滨,minusSet:和unionSet:洞焙。

NSSet性能特征

蘋(píng)果在CFSet頭文件中沒(méi)有提供任何關(guān)于算法復(fù)雜度的注釋:

NSSet在每一個(gè)被添加的對(duì)象上執(zhí)行hash和isEqual:方法并管理一個(gè)哈希筐拯啦,所以在添加元素時(shí)耗費(fèi)了更多的時(shí)間澡匪。set的隨機(jī)訪問(wèn)比較難以測(cè)試,因?yàn)檫@里執(zhí)行的都是anyObject褒链。

這里沒(méi)有必要包含containsObject:的測(cè)試仙蛉,set要快幾個(gè)數(shù)量級(jí),畢竟這是它的特點(diǎn)碱蒙。

NSOrderedSet

NSOrderedSet在iOS 5和Mac OS X 10.7中第一次被引入荠瘪,除了CoreData,幾乎沒(méi)有直接使用它的API赛惩“梗看上去它綜合了NSArray和NSSet兩者的好處,對(duì)象查找喷兼,對(duì)象唯一性篮绰,和快速隨機(jī)訪問(wèn)。

NSOrderedSet有著優(yōu)秀的API方法季惯,使得它可以很便利的與其他set或者有序set對(duì)象合作吠各。合并,交集勉抓,差集贾漏,就像NSSet支持的那樣。它有NSArray中的大多數(shù)排序方法藕筋,除了比較陳舊的基于函數(shù)的排序方法和二分查找纵散。畢竟containsObject:非常快,所以沒(méi)有必要再用二分查找了伍掀。

array和set方法分別返回一個(gè)NSArray和NSSet掰茶,但是。這些對(duì)象表面上是對(duì)象蜜笤,像不可變對(duì)象那樣濒蒋,在有序set被更新的時(shí)候,它們會(huì)更新自己把兔。當(dāng)你打算在多個(gè)線程上迭代這些對(duì)象并發(fā)生了突變異常的時(shí)候沪伙,了解這一點(diǎn)是有好處的。本質(zhì)上垛贤,這些類使用的是__NSOrderedSetSetProxy和__NSOrderedSetArrayProxy焰坪。

附注:如果你想知道為什么NSOrderedSet不是NSSet的子類趣倾,NSHipster上有一篇非常好的文章解釋了可變/不可變類簇的缺點(diǎn)聘惦。

NSOrderedSet性能特征

NSOrderedSet代價(jià)高昂,天下沒(méi)有免費(fèi)的午餐儒恋。

NSOrderedSet比NSSet和NSArray占用更多的內(nèi)存善绎,因?yàn)樗枰黄鹁S護(hù)哈希值和索引。

NSHashTable

NSHashTable效仿了NSSet诫尽,但在對(duì)象/內(nèi)存處理時(shí)更加的靈活禀酱。可以通過(guò)自定義CFSet的回調(diào)獲得NSHashTable的一些特性牧嫉,哈希表可以保持對(duì)對(duì)象的弱引用并在對(duì)象被銷毀之后正確的將其移除 — 一些手動(dòng)添加到NSSet的時(shí)候非常惡心的事情剂跟。它是默認(rèn)可變的 — 沒(méi)有相應(yīng)的不可變類。

NSHashTable有ObjC和原始的C API酣藻,C API可以用來(lái)存儲(chǔ)任意對(duì)象曹洽。蘋(píng)果在10.5 Leopard系統(tǒng)中引入了這個(gè)類,但是直到最近的iOS 6中才被加入辽剧。足夠有趣的是它們只移植了 ObjC API;更多強(qiáng)大的C API沒(méi)有包括在iOS中送淆。

NSHashTable可以通過(guò)initWithPointerFunctions:capacity:進(jìn)行大量的設(shè)置 — 我們只選取使用hashTableWithOptions:最普遍的使用場(chǎng)景。最有用的選項(xiàng)有它自己的方便的構(gòu)造函數(shù)weakObjectsHashTable怕轿。

NSPointerFunctions
這些指針函數(shù)可以被用在NSHashTable偷崩,NSMapTable和NSPointerArray中,定義了對(duì)存儲(chǔ)在這個(gè)集合中的對(duì)象的獲取和保留行為撞羽。這里是最有用的選項(xiàng)阐斜。完整列表參見(jiàn)NSPointerFunctions.h。

有兩組選項(xiàng)诀紊。內(nèi)存選項(xiàng)決定了內(nèi)存管理智听,個(gè)性化定義了哈希和相等。

NSPointerFunctionsStrongMemory創(chuàng)建了一個(gè)retain/release對(duì)象的集合,非常像常規(guī)的NSSet或NSArray到推。

NSPointerFunctionsWeakMemory使用等價(jià)的__weak來(lái)存儲(chǔ)對(duì)象并自動(dòng)移除被銷毀的對(duì)象考赛。

NSPointerFunctionsCopyIn在對(duì)象被加入到集合前拷貝它們。

NSPointerFunctionsObjectPersonality使用對(duì)象的hash和isEqual:(默認(rèn))莉测。

NSPointerFunctionsObjectPointerPersonality對(duì)于isEqual:和hash使用直接的指針比較颜骤。

NSHashTable性能特征
如果你只是需要NSSet的特性,請(qǐng)堅(jiān)持使用NSSet捣卤。NSHashTable在添加對(duì)象時(shí)花費(fèi)了將近2倍的時(shí)間忍抽,但是其他方面的效率卻非常相近。

NSMapTable

NSMapTable和NSHashTable相似董朝,但是效仿的是NSDictionary鸠项。因此,我們可以通過(guò)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è)字典遥赚,它的鍵沒(méi)有實(shí)現(xiàn)NSCopying協(xié)議扬舒,比如UIView,的時(shí)候非常有用凫佛。

如果你好奇為什么蘋(píng)果”忘記”為NSMapTable增加下標(biāo)讲坎,你現(xiàn)在知道了。下標(biāo)訪問(wèn)需要一個(gè)id<NSCopying>作為key愧薛,對(duì)NSMapTable來(lái)說(shuō)這不是強(qiáng)制的晨炕。如果不通過(guò)一個(gè)非法的API協(xié)議或者移除NSCopying協(xié)議來(lái)削弱全局下標(biāo),是沒(méi)有辦法給它增加下標(biāo)的厚满。

你可以通過(guò)dictionaryRepresentation把內(nèi)容轉(zhuǎn)換為普通的NSDictionary府瞄。不像NSOrderedSet,這個(gè)方法返回一個(gè)常規(guī)的字典而不是一個(gè)代理碘箍。

NSMapTable性能特征

NSMapTable只比NSDictionary略微慢一點(diǎn)遵馆。如果你需要一個(gè)不retain鍵的字典,放棄CFDictionary使用它吧丰榴。

NSPointerArray

NSPointerArray類是一個(gè)稀疏數(shù)組货邓,工作起來(lái)與NSMutableArray相似,但可以存儲(chǔ)NULL值四濒,并且count方法會(huì)反應(yīng)這些空點(diǎn)换况≈氨妫可以用NSPointerFunctions對(duì)其進(jìn)行各種設(shè)置,也有應(yīng)對(duì)常見(jiàn)的使用場(chǎng)景的快捷構(gòu)造函數(shù)strongObjectsPointerArray和weakObjectsPointerArray戈二。

在能使用insertPointer:atIndex:之前舒裤,我們需要通過(guò)直接設(shè)置count屬性來(lái)申請(qǐng)空間,否則會(huì)產(chǎn)生一個(gè)異常觉吭。另一種選擇是使用addPointer:腾供,這個(gè)方法可以自動(dòng)根據(jù)需要增加數(shù)組的大小。

你可以通過(guò)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沒(méi)有受到太多歡迎须肆。description方法只是簡(jiǎn)單的返回了<NSConcretePointerArray: 0x17015ac50>。為了得到所有的對(duì)象需要執(zhí)行[pointerArray allObjects]脐往,當(dāng)然休吠,如果存在NULL的話會(huì)改變索引扳埂。

NSPointerArray性能特征

在性能方面业簿,NSPointerArray真的非常非常慢,所以當(dāng)你打算在一個(gè)很大的數(shù)據(jù)集合上使用它的時(shí)候一定要三思阳懂。在本測(cè)試中我們比較了使用NSNull作為空標(biāo)記的NSMutableArray和使用了NSPointerFunctionsStrongMemory設(shè)置的NSPointerArray(這樣對(duì)象會(huì)被適當(dāng)?shù)膔etain)梅尤。在一個(gè)有10,000個(gè)元素的數(shù)組中,我們每隔十個(gè)插入一個(gè)字符串”Entry %d”岩调。此測(cè)試包括了用NSNull作為null填充的NSMutableArray巷燥。對(duì)于NSPointerArray,我們使用setCount:來(lái)代替

NSCache

NSCache是一個(gè)非常奇怪的集合号枕。在iOS 4/Snow Leopard中加入缰揪,默認(rèn)為可變并且線程安全的。這使它很適合緩存那些創(chuàng)建起來(lái)代價(jià)高昂的對(duì)象葱淳。它自動(dòng)對(duì)內(nèi)存警告做出反應(yīng)并基于可設(shè)置的”成本”清理自己钝腺。與NSDictionary相比,鍵是被retain而不是被拷貝的赞厕。

NSCache的回收方法是不確定的艳狐,在文檔中也沒(méi)有說(shuō)明。向里面放一些類似圖片那樣比被回收更快填滿內(nèi)存的大對(duì)象不是個(gè)好主意皿桑。(這是在PSPDFKit中很多跟內(nèi)存有關(guān)的crash的原因毫目,在使用自定義的基于LRU的鏈表的緩存代碼之前蔬啡,我們起初使用NSCache存儲(chǔ)事先渲染的圖片。)

NSCache可以設(shè)置撐自動(dòng)回收實(shí)現(xiàn)了NSDiscardableContent協(xié)議的對(duì)象镀虐。實(shí)現(xiàn)該屬性的一個(gè)比較流行的類是同時(shí)間加入的NSPurgeableData箱蟆,但是在OS X 10.9之前,是非線程安全的(沒(méi)有信息表明這是否也影響到iOS或者是否在iOS 7中被修復(fù)了)刮便。

NSCache性能

那么NSCache如何承受NSMutableDictionary的考驗(yàn)?加入的線程安全必然會(huì)帶來(lái)一些消耗顽腾。處于好奇,我也加入了一個(gè)自定義的線程安全的字典的子類(PSPDFThreadSafeMutableDictionary)诺核,它通過(guò)OSSpinLock實(shí)現(xiàn)同步的訪問(wèn)抄肖。

NSCache表現(xiàn)的相當(dāng)好,隨機(jī)訪問(wèn)跟我們自定義的線程安全字典一樣快窖杀。如我們預(yù)料的漓摩,添加更慢一些,因?yàn)镹SCache維持著一個(gè)可選的決定何時(shí)回收對(duì)象的成本系數(shù)入客。就這一點(diǎn)來(lái)看這不是一個(gè)非常公平的比較管毙。有趣的是,在模擬器上運(yùn)行效率要慢了幾乎10倍桌硫。無(wú)論對(duì)32或64位的系統(tǒng)都是夭咬。而且看起來(lái)已經(jīng)在iOS 7中優(yōu)化過(guò)并且受益于64位運(yùn)行時(shí)環(huán)境。當(dāng)在老的設(shè)備上測(cè)試時(shí)铆隘,使用NSCache的性能消耗尤為明顯卓舵。

iOS 6(32 bit)和iOS 7(64 bit)的區(qū)別也很明顯,因?yàn)?4位運(yùn)行時(shí)使用標(biāo)簽指針膀钠,因此我們的@(idx)封裝要更為高效掏湾。

NSIndexSet

有些使用場(chǎng)景下NSIndexSet(和它的可變變體,NSMutableIndexSet)真的非常出色肿嘲,對(duì)它的使用貫穿在Foundation中融击。它可以用一種非常高效的方法存儲(chǔ)一組無(wú)符號(hào)整數(shù)的集合,尤其是如果只是一個(gè)或少量范圍的時(shí)候雳窟。正如set這個(gè)名字已經(jīng)暗示的那樣尊浪,每一個(gè)NSUInteger要么在索引set中要么不在。如果你需要存儲(chǔ)任意唯一的整數(shù)封救,最好使用NSArray拇涤。

如何把一個(gè)整數(shù)數(shù)組轉(zhuǎn)換偉NSIndexSet:

  NSIndexSet *PSPDFIndexSetFromArray(NSArray *array) { 
      NSMutableIndexSet *indexSet = [NSMutableIndexSet indexSet]; 
      for (NSNumber *number in array) { 
          [indexSet addIndex:[number unsignedIntegerValue]]; 
      } 
      return [indexSet copy]; 
 }

如果不使用block,從索引set中拿到所有的索引有點(diǎn)麻煩兴泥,getIndexes:maxCount:inIndexRange:是最快的方法工育,其次是使用firstIndex并迭代直到indexGreaterThanIndex:返回NSNotFound。隨著block的到來(lái)搓彻,使用NSIndexSet工作變得方便的多:

 NSArray *PSPDFArrayFromIndexSet(NSIndexSet *indexSet) { 
     NSMutableArray *indexesArray = [NSMutableArray arrayWithCapacity:indexSet.count]; 
     [indexSet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) { 
         [indexesArray addObject:@(idx)]; 
     }]; 
     return [indexesArray copy]; 
 } 

NSIndexSet性能

Core Foundation中沒(méi)有和NSIndexSet相當(dāng)?shù)念惾绯瘢O(píng)果也沒(méi)有對(duì)性能做出任何承諾嘱朽。NSIndexSet和NSSet之間的比較也相對(duì)的不公平,因?yàn)槌R?guī)的set需要對(duì)數(shù)字進(jìn)行包裝怔接。

我們看到在一百萬(wàn)左右對(duì)象的時(shí)候搪泳,NSIndexSet開(kāi)始變得比NSSet慢,但只是因?yàn)樾碌倪\(yùn)行時(shí)和標(biāo)簽指針扼脐。在iOS 6上運(yùn)行相同的測(cè)試表明岸军,甚至在更高數(shù)量級(jí)實(shí)體的條件下,NSIndexSet更快瓦侮。實(shí)際上艰赞,在大多數(shù)應(yīng)用中,你不會(huì)添加太多的整數(shù)到索引set中肚吏。還有一點(diǎn)這里沒(méi)有測(cè)試方妖,就是NSIndexSet跟NSSet比無(wú)疑有更好的內(nèi)存優(yōu)化。

結(jié)論

本文主要詳細(xì)介紹了OC的各種集合基礎(chǔ)類罚攀,之后大家在使用基礎(chǔ)集合類的時(shí)候做出更好的選擇党觅。除了上面討論的類,還有一些不常用但是有用的類斋泄,尤其是NSCountedSet杯瞻,CFBagCFTree炫掐,CFBitVectorCFBinaryHeap

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末魁莉,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子卒废,更是在濱河造成了極大的恐慌沛厨,老刑警劉巖宙地,帶你破解...
    沈念sama閱讀 216,324評(píng)論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件摔认,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡宅粥,警方通過(guò)查閱死者的電腦和手機(jī)参袱,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,356評(píng)論 3 392
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)秽梅,“玉大人抹蚀,你說(shuō)我怎么就攤上這事∑罂眩” “怎么了环壤?”我有些...
    開(kāi)封第一講書(shū)人閱讀 162,328評(píng)論 0 353
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)钞诡。 經(jīng)常有香客問(wèn)我郑现,道長(zhǎng)湃崩,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 58,147評(píng)論 1 292
  • 正文 為了忘掉前任接箫,我火速辦了婚禮攒读,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘辛友。我一直安慰自己薄扁,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,160評(píng)論 6 388
  • 文/花漫 我一把揭開(kāi)白布废累。 她就那樣靜靜地躺著邓梅,像睡著了一般。 火紅的嫁衣襯著肌膚如雪邑滨。 梳的紋絲不亂的頭發(fā)上震放,一...
    開(kāi)封第一講書(shū)人閱讀 51,115評(píng)論 1 296
  • 那天,我揣著相機(jī)與錄音驼修,去河邊找鬼殿遂。 笑死,一個(gè)胖子當(dāng)著我的面吹牛乙各,可吹牛的內(nèi)容都是我干的墨礁。 我是一名探鬼主播,決...
    沈念sama閱讀 40,025評(píng)論 3 417
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼耳峦,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼恩静!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起蹲坷,我...
    開(kāi)封第一講書(shū)人閱讀 38,867評(píng)論 0 274
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤驶乾,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后循签,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體级乐,經(jīng)...
    沈念sama閱讀 45,307評(píng)論 1 310
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,528評(píng)論 2 332
  • 正文 我和宋清朗相戀三年县匠,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了风科。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,688評(píng)論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡乞旦,死狀恐怖贼穆,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情兰粉,我是刑警寧澤故痊,帶...
    沈念sama閱讀 35,409評(píng)論 5 343
  • 正文 年R本政府宣布,位于F島的核電站玖姑,受9級(jí)特大地震影響愕秫,放射性物質(zhì)發(fā)生泄漏浊仆。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,001評(píng)論 3 325
  • 文/蒙蒙 一豫领、第九天 我趴在偏房一處隱蔽的房頂上張望抡柿。 院中可真熱鬧,春花似錦等恐、人聲如沸洲劣。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 31,657評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)囱稽。三九已至,卻和暖如春二跋,著一層夾襖步出監(jiān)牢的瞬間战惊,已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,811評(píng)論 1 268
  • 我被黑心中介騙來(lái)泰國(guó)打工扎即, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留吞获,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 47,685評(píng)論 2 368
  • 正文 我出身青樓谚鄙,卻偏偏與公主長(zhǎng)得像各拷,于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子闷营,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,573評(píng)論 2 353

推薦閱讀更多精彩內(nèi)容