NSArrayとNSDictionaryの検索速度

NSArrayとNSDictionaryを生成して検索速度を比較してみました。
結果、NSDictionaryの検索速度の方が速いようです。
ハッシュ（連想配列）なので当たり前と言えば当たり前ですが。。

---

// 計測用データ作成
NSMutableDictionary *dic = [[NSMutableDictionary alloc] init];
NSMutableArray *array = [[NSMutableArray alloc] init];
for (int i = 0 ; i < 500000; i++ ) {
NSString *val = [NSString stringWithFormat:@"%d", i];
[dic setValue:[NSString stringWithFormat:@"%ld", i] forKey:val];
[array addObject:val];
}

NSLog(@"辞書検索Start");
NSDate *startTime = [NSDate date];

NSString *strTest = @"400000";
NSString *num = [dic valueForKey:strTest]; // 辞書を検索

NSTimeInterval interval = [[NSDate date] timeIntervalSinceDate:startTime];
NSLog(@"辞書検索Stop at:%lf", interval);
if (num) {
NSLog(@"There is %@ in the dictionary", strTest);
} else {
NSLog(@"There is not %@ in the dictionary", strTest);
}


NSLog(@"配列検索Start");
startTime = [NSDate date];
unsigned long idx = [array indexOfObject:strTest];

interval = [[NSDate date] timeIntervalSinceDate:startTime];
NSLog(@"配列検索Stop at:%lf", interval);
if (idx != NSNotFound) {
NSLog(@"There is %@ in the dictionary", strTest);
} else {
NSLog(@"There is not %@ in the dictionary", strTest);
}


NSLog(@"配列検索2Start");
startTime = [NSDate date];
BOOL hasString = [array containsObject:strTest];

interval = [[NSDate date] timeIntervalSinceDate:startTime];
NSLog(@"配列検索2Stop at:%lf", interval);
if (hasString) {
NSLog(@"There is %@ in the dictionary", strTest);
} else {
NSLog(@"There is not %@ in the dictionary", strTest);
}

---

結果は以下のようになりました。(iPhoneでの計測ではなく、Mac上で計測しました。)

---

辞書検索Start
辞書検索Stop at:0.000017
here is 400000 in the dictionary
配列検索Start
配列検索Stop at:0.036717
here is 400000 in the dictionary
配列検索2Start
配列検索2Stop at:0.037023
here is 400000 in the dictionary

---

配列検索ではindexOfObjectによる検索とcontainsObjectによる検索を計測しましたが、どちらも大差は無さそうです。
ちなみに、検索する要素を"400000"から"250000"にすると以下のようになりました。

---

辞書検索Start
辞書検索Stop at:0.000050
There is 250000 in the dictionary
配列検索Start
配列検索Stop at:0.022836
There is 250000 in the dictionary
配列検索2Start
配列検索2Stop at:0.022718
There is 250000 in the dictionary

---

ハッシュの検索はほぼ大差ない速度（むしろ若干遅くなっている）ですが、配列の検索では要素位置が上のほうにある為か高速に検索が行えました。

結論としては、
・ハッシュ(NSDictionary)は要素の数や位置に関わらずほぼ同一速度で検索が行える。
・配列(NSArray)は要素数や要素位置に応じて検索速度が変わる
・indexOfObjectとcontainsObjectによる検索は速度に大差なし

というところでしょうか。