NSSet的查找

LOADING

2013-04-13

看<Pro.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 <MyItem: 0x1001050d0> identifier 100000

2013-04-12 10:14:19.742 BlockTest[1088:903] for 耗费时间 : 0.010545 s

2013-04-12 10:14:19.743 BlockTest[1088:903] old item <MyItem: 0x1020406a0> identifier 100000

2013-04-12 10:14:19.744 BlockTest[1088:903] set 耗费时间 : 0.000009 s

2013-04-12 10:14:19.745 BlockTest[1088:903] old item <MyItem: 0x1020406a0> identifier 100000

100万(for查找时间正好10倍,说明就是O(n),而set查找几乎不变,O(1))

2013-04-12 10:23:55.652 BlockTest[1249:903] search for item <MyItem: 0x1001050d0> 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 <MyItem: 0x105c1d7e0> identifier 1000000

2013-04-12 10:23:55.754 BlockTest[1249:903] set 耗费时间 : 0.000006 s