你好,歡迎來到IOS教程網

 Ios教程網 >> IOS編程開發 >> IOS開發基礎 >> 一些NSArray,NSDictionary,NSSet相關的算法知識

一些NSArray,NSDictionary,NSSet相關的算法知識

編輯:IOS開發基礎

iOS編程當中的幾個集合類:NSArray,NSDictionary,NSSet以及對應的Mutable版本,應該所有人都用過。只是簡單使用的話,相信沒人會用錯,但要做到高效(時間復雜度)精確(業務准確性),還需要了解其中所隱藏的算法知識。

在項目當中使用集合類幾乎是不可避免的,集合類的使用場景其實可以進行抽象的歸類。大多數時候我們需要將若干個對象(object)暫時保存起來,以備後續的業務邏輯進行操作,「保存和操作」,或者說「存與取」,對應到計算機世界的術語就是讀和寫。最初保存的時候我們Insert,下次進行更新的時候我們再Get,不再需要的時候我們調用Delete,所以你看集合類的操作場景其實就那麼多,關鍵在於我們存的方式,和取的方式不同。

最初我們學習數據結構和算法的時候,知道數據的組織方式不同,比如Array, List, Stack, Heap, Tree,其對應的讀和取效率(時間復雜度)也不同。如果insert的效率高,下次get的時候效率就低,比如無序的Array,插入的時候O(1),查找的時候就變O(N)。如果想要查找的速度快,比如排序過的Array,查找的速度在O(logN),插入的時候就必須要保持Array有序這一特性O(N)。所以插入和查找是魚與熊掌,想要下次快速的找到一本書,就必須在整理書架的時候多花些心思分門別類。或者我們跳出時間的維度,用更多的空間來做彌補,使用哈希表或者Dictionary來存儲數據,查找的速度可以快至O(1),缺點是犧牲了更多的空間。

當我們預先存好Array之後,使用的時候大多是以下幾種場景:

場景一

for (NSObject* obj in self.arr) {
    //update each object
}

場景二

if ([self.arr containsObject:obj] == false) {
    [self.arr addObject:obj];
}

場景三

if ([self.arr containsObject:obj] == true) {
    [self.arr removeObject:obj];
}

第一種場景沒有多少可發掘的,一次干淨利索的遍歷費時O(N)。唯一需要注意的是切忌在遍歷的時候改變集合對象,比如:

for (NSObject* obj in self.arr) {
    if(obj.isInvalid){
        [self.arr removeObject:obj];
    }
}

如果要在遍歷的時候刪除可以換種寫法,比如:

for (int i = self.arr.count-1; i > 0; i --) {
    NSObject* obj = self.arr[i];
    if (obj.isInvalid) {
        [self.arr removeObject:obj];
    }
}

場景二和場景三需要特別留意,containsObject,removeObject都涉及到一個集合當中的重要概念,即相等性。

值的相等性很簡單,不用思索就能得出直觀的答案,比如1==1,2.0f==2.0f。

對象的相等性就不那麼簡單了。什麼時候我們認為兩個對象是相等的呢?我們可以從兩個維度去理解相等性。

同一對象相等:

理論上說兩個對象的指針如果是指向同一塊內存區域,那麼他們一定是相等的,一定是指向同一個對象。這種情況下我們判斷相等性是通過

if (obj1 == obj2)

業務屬性相等:

兩個對象即使不指向同一塊內存區域,但他們的所有(或者部分關鍵的)property是相等的,我們也可以認為這兩個對象是相等的,比如連個UserProfile對象,他們的name,gener,age屬性都相等,在業務層面,我們可以認為他們是相等的,此時我們不能用==來判斷相等性了,需要重載isEqual,或者自己實現isEqualToXXX:

@implementation MyObject
- (BOOL)isEqual:(id)object
{
    if (self == object) {
        return true;
    }
    if ([object isKindOfClass:[self class]] == false) {
        return false;
    }
    
    MyObject* myObject = object;
    if ([self.name isEqualToString:myObject.name]) {
        return true;
    }
    
    return false;
}
@end

所以當我們判斷兩個集合當中對象是否相等時,一定要心中明確是那種相等。當調用containsObject,removeObject的時候,如果我們重載了isEqual,系統就通過我們的isEqual方法來判斷相等性,如果沒有重載,那麼系統就會通過判斷內存地址來判斷相等性了。

有些架構model layer的設計會允許同一個業務對象在應用層存在多份拷貝,此時在Array當中使用相等性的時候尤其要注意重載isEqua方法。當然有些mode layer只允許一份拷貝,一個業務對象永遠只對應一個內存地址,isEqual方法就變得多余了。

和isEqual配套的另一個方法hash也經常被提起,官方文檔甚至規定isEqual和hash必須被同時實現。學習過hash表之後,我們知道如果兩個對象業務上相等,那麼他們的hash值一定是相等的,hash方法的用處還是在於判斷相等性,系統默認的hash方法實際上返回的就是對象的內存地址。問題是我們已經有isEqual方法來判斷相等性了,為什麼還需要一個hash呢?

答案是hash可以更加高效快速的判斷一個對象是否存在集合當中,在NSArray當中我們需要遍歷Array,調用N次isEqual才能知道對象是否存在集合當中,時間復雜度是O(N)。在調用isEqual之前,可以通過調用hash來判斷是否相等,如果hash值不等就沒有進一步調用isEqual的必要了,如果相等必須再調用一次isEqual來確認是否真正相等。但是hash為什麼會比isEqual的效率要高呢?看下hash的聲明就明白了。

- (NSUInteger)hash
{
    return [_name hash];
}

hash方法的返回值是一個NSUInteger,這個值往往和對象在內存當中的存儲位置直接相關,也就是說我們可以通過這個值以O(1)的復雜度快速讀取到某個對象來判斷相等性,和Array O(N)的復雜度相比快了太多了,Array顯然不具備這種特性,Array當中的元素是在一片內存空間當中連續排放的,和hash的返回值沒任何關系。

但這種使用hash的便捷性有一個前提:對象在集合當中是唯一的,也就是說集合當中不允許存在重復的元素,比如NSDictionary,NSSet。我們在使用下列方法的時候:

[dictionary objectForKey:key];
[set addObject:object];

為了保證唯一性,都需要先判斷對象是否存在集合當中,此時一個高效的判斷機制十分重要,這也就是hash發揮作用的地方,這也是為什麼使用NSArray的時候只會調用isEqual,而使用NSDictionary,NSSet的時候會頻繁調用hash的原因。

所以當我們使用NSDictionary,NSSet的時候,同時重載isEqual和hash方法對性能至關重要。hash方法的選擇並不需要過分挑剔,對關鍵的property做下運算,保證絕大部分場景下hash值不同即可,畢竟hash調用之後還是會調用isEqual做進一步判斷,並不會對我們業務的准確性產生影響。

Objective C當中的幾個關鍵集合類:NSArray,NSDictionary,NSSet要高效的使用並沒有看起來那麼簡單,當集合類中的元素到達一定量級之後,考慮下背後的算法效率很有必要,這也是為什麼一直強調算法對於程序員的重要性。


  1. 上一頁:
  2. 下一頁:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © Ios教程網 All Rights Reserved