NSSetの検索

見てiOS.Apps.Performance.Optimization>その本は偶然発見^^NSSet検索アルゴリズムがO(1)であることを発見した.
   
まずもちろんNSSetにデータを読み込み(時間は関係なく)、setでもカスタムdataを入れることができます(テスト用のMyItemにはidentifierとname属性が含まれています)
次にMyItemのisEqualとhashを書き換えます.検索時にisEqualが呼び出されるため、hashについてはhashのドキュメントの説明を参照してください.
If two objects are equal (as determined by the isEqual: method), they must have the same hash value. This last point is particularly important if you define hash in a subclass and intend to put instances of that subclass into a collection.
 
どのpropertyで検索するかに応じて書き換えます(これはidentifierを使用します)

- (BOOL)isEqual:(id)anObject {
    if (anObject == self) {
        return YES;
    }
    
    if (![anObject isKindOfClass:[self class]]) {
        return NO;
    }
    
    MyItem *item = (MyItem *)anObject;
    if ([self.identifier isEqual:item.identifier]) {
        return YES;
    }
    
    return NO;
}


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

 
テストコード:

NSMutableArray *itemArray = [NSMutableArray array];
    long itemCount = 100000;
    for (int i = 0; i < itemCount; i ++) {
        @autoreleasepool {
            MyItem *item = [[[MyItem alloc] initWithIdentifier:[NSString stringWithFormat:@"%d",i + 1]] autorelease];
            [itemArray addObject:item];
        }
    }

    NSMutableSet *set = [NSMutableSet setWithArray:itemArray];
    
    MyItem *newItem = [[MyItem alloc] initWithIdentifier:[NSString stringWithFormat:@"%d",100000]];
    NSLog(@"search for item %@ identifier %@",newItem,newItem.identifier);

    MyItem *oldItem = nil;
    NSDate *date = [NSDate date];
    
    for (MyItem *item in itemArray) {
        if ([item isEqual:newItem]) {
            oldItem = item;
            break;
        }
    }
    
    NSLog(@"for   : %f s",[[NSDate date] timeIntervalSinceDate:date]);
    NSLog(@"old item %@ identifier %@",oldItem,oldItem.identifier);

    oldItem = nil;
    date = [NSDate date];
    
    oldItem = [set member:newItem];
    
    NSLog(@"set   : %f s",[[NSDate date] timeIntervalSinceDate:date]);
    NSLog(@"old item %@ identifier %@",oldItem,oldItem.identifier);

 
出力:
 
10万、スピード的には絶対秒殺^^
2013-04-12 10:14:19.730 BlockTest[1088:903] search for item identifier 100000
2013-04-12 10:14:19.742 BlockTest[088:903]for消費時間:0.010545 s
2013-04-12 10:14:19.743 BlockTest[1088:903] old item identifier 100000
2013-04-12 10:14:19.744 BlockTest[088:903]set消費時間:0.00009 s
2013-04-12 10:14:19.745 BlockTest[1088:903] old item identifier 100000
 
100万(for検索時間はちょうど10倍で、説明はO(n)ですが、set検索はほとんど変わりません.O(1))
2013-04-12 10:23:55.652 BlockTest[1249:903] search for item identifier 1000000
2013-04-12 10:23:55.753 BlockTest[1249:903]for消費時間:0.100014 s
2013-04-12 10:23:55.754 BlockTest[1249:903] old item identifier 1000000
2013-04-12 10:23:55.754 BlockTest[1249:903]set消費時間:0.00006 s
2013-04-12 10:23:55.755 BlockTest[1249:903] old item identifier 1000000