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

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?

  • "S'il vous plaît montrer votre travail?" Vous avez les mêmes outils que nous faisons. Vous devriez essayer de profilage le code différent si vous voulez connaître la réponse à quelque chose comme cela.
  • Daniel est tout à fait exact, c'était une très paresseux façon d'obtenir la réponse facile à la question du test. Mais j'ai eu une très bonne réponse et quelques vrais résultats de performance, donc merci à tous de me permettre de faire un peu paresseux.
  • Je reçois que les gens sont un peu mis par le "s'il vous Plaît montrer votre travail" ligne de la question ci-dessus, mais j'ai pensé que le point de débordement de pile est d'avoir des réponses à toutes sortes de questions de base, non? Donc, pour clarifier, je n'ai pas demandé cela parce que je ne connais pas la réponse, ne pouvait pas trouver moi-même, ou d'être une rude secousse. Plutôt, parce que la réponse n'est pas immédiatement évident, sauf si vous êtes familier avec la Fondation des collections que c'était une bonne question et la réponse disponibles.
  • Cette question a été la cause de plus de plusieurs drapeaux de notre communauté. J'ai fait une modification mineure à votre question, veuillez envisager de garder (ou de la révision de mon montage à rien de ce qu'il était à l'origine).
  • Je suis totalement ne savais pas que je pouvais modifier la question après le fait. /facepalm
  • Est-il une différence entre le fait d'avoir une clé = nil et de ne pas avoir la clé à tous?
  • Pour info vous pouvez gagner un peu de vitesse à l'aide de CFDictionaryContainsKey ((__bridge CFDictionaryRef) (dictionary), foo);

InformationsquelleAutor alfwatt | 2009-05-06
  1. 68

    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é).

    Au nom de la science, si, j'ai fait deux exécutables qui vient d'exécuter chaque style 1 million de fois et chronométré les.

    Avec allKeys:

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

    Avec objectForKey:

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

    Évidemment, divers facteurs peuvent influencer cette 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.

    • +1 pour l'élégance, la production de chapitre et le verset
    • Comment avez-vous fait le test?
    • Chuck, pouvez-vous tester à l'aide de valueForKey avec un dictionnaire dans un dictionnaire? Je pense que ce serait plus utile, en plus de savoir que objectForKey effectue plus rapidement. Merci à l'avance.
    InformationsquelleAutor Chuck
  2. 6

    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ù le 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 est abstraite.)

    • D'accord. Demander allKeys va vous donner un NSArray qui containsObject doit ensuite itérativement de recherche à la recherche pour les foo. objectForKey, d'autre part, l'utilisation d'un algorithme de hachage pour calculer l'emplacement de foo dans le dictionnaire de sorte que foo est l'existence peut être déterminée directement.
    InformationsquelleAutor Jesse Rusak
  3. 2

    Lors de la réflexion sur 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.

    • N'est-il pas plus susceptibles d'être dans l'autre sens, où une table de hachage devient de plus en plus bénéfique? Test 10 ou si des objets pour l'égalité est trivial. Plusieurs milliers d'objets bien, et d'une table de hachage devient une victoire éclatante.
    • Vous pourriez très bien être raison, je me souviens que quelqu'un a écrit un article (avec les critères de référence) à ce sujet il y a quelques temps, mais je n'ai pas beaucoup réfléchi depuis.
    • ridiculousfish.com/blog/posts/array.html serait le message que vous envisagez de
    InformationsquelleAutor Marc Charbonneau