Какой метод проверки, чтобы видеть, содержит ли NSDictionary определенный ключ, быстрее?

Question

Я могу проверить наличие ключа в NSDictionary двумя способами:

BOOL containsKey = [[dictionary allKeys] containsObject:foo];

BOOL containsKey = ([dictionary objectForKey:foo] != nil);

какой метод быстрее и почему?

Answer 1

Поиск хеша в целом должен быть быстрее, чем обходить все ключи словаря, создавать из них массив (выделение памяти относительно дорого), а затем искать в массиве (который даже не может быть двоичным поиском, поскольку массив не отсортировано).

Однако ради науки я создал два исполняемых файла, которые просто исполняют каждый стиль по миллиону раз и синхронизировали их.

со всеми клавишами:

real    0m4.185s
user    0m3.890s
sys     0m0.252s

С objectForKey:

real    0m0.396s
user    0m0.189s
sys     0m0.029s

Очевидно, что на это могут влиять различные факторы - размер словаря, кеширование возвращаемого значения allKeys и т. Д. Я не ожидаю, что будет случай, когда поиск в массиве будет быстрее, чем поиск по словарю.

Answer 2

Я не понимаю, как запрос массива allKeys мог бы быть быстрее, иначе NSDictionary по крайней мере сделал бы эквивалент внутри.

РЕДАКТИРОВАТЬ: Я полагаю, что вы могли бы создать случай, когда метод allKeys будет быстрее - принимая длительное время в методе hash вашего ключа, но не в вашем методе isEqual:, например. И вы также можете поменять местами сумасшедшую реализацию для NSDictionary, в которой они тоже поменялись местами (поскольку NSDictionary является абстрактным).

Answer 3

Обдумывая подобные вопросы производительности, имейте в виду, что классы данных Foundation меняют свои базовые структуры данных в зависимости от того, сколько объектов вы в них храните. Например, я думаю, что небольшой NSArray фактически использует хеш-таблицу для хранения, пока не достигнет определенного размера.