La méthode de vérification pour voir si un NSDictionary contient une clé particulier est le plus rapide?

Question

Je peux tester la présence d'une clé dans un NSDictionary de deux façons:

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

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

quelle méthode est la plus rapide, et pourquoi?

Answer 1

Un hachage de recherche devrait être plus rapide en général que d'aller sur toutes les clés de dictionnaire, la création d'un tableau à partir d'eux (allocation de mémoire est relativement cher) et ensuite une recherche dans le tableau (qui ne peut même pas être une recherche binaire depuis le tableau n'est pas trié).

Pour l'amour de la science, si, j'ai fait deux exécutables qui vient d'exécuter chaque style 1 million de fois et datés entre eux.

Avec allKeys:

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

Avec objectForKey:

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

Évidemment, plusieurs facteurs peuvent influer sur ce de la taille du dictionnaire, la mise en cache de la allKeys valeur de retour, etc. Je ne m'attends pas à une affaire dans laquelle la matrice de la recherche est plus rapide que la recherche dans le dictionnaire, si.

Answer 2

Je ne vois pas comment demander le tableau allKeys pourrait être plus rapide, sinon NSDictionary serait au moins équivalent à l'interne.

EDIT: je suppose que vous pourriez construire une affaire où l' allKeys méthode serait plus rapide, en prenant un long temps dans votre clé, hash méthode, mais pas dans votre isEqual: méthode, par exemple. Et vous pouvez aussi le remplacer par un fou de la mise en œuvre de NSDictionary dans lequel ils sont échangés, trop (depuis NSDictionary abstrait.)

Answer 3

Lorsque l'on pense à propos de la performance à ce genre de questions, gardez à l'esprit que les données de la Fondation des classes d'échanger leurs données sous-jacentes des structures en fonction du nombre d'objets que vous stockez dans leur. Par exemple, je pense qu'une petite NSArray utilise une table de hachage pour le stockage jusqu'à ce qu'il atteint une certaine taille.