Quale metodo di controllo per vedere se un NSDictionary contiene una chiave particolare è più veloce?

Question

Posso verificare la presenza di una chiave in un NSDictionary in due modi:

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

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

quale metodo è più veloce e perché?

Answer 1

Una ricerca di hash dovrebbe essere più veloce in generale che andare su tutte le chiavi del dizionario, creando una matrice da esse (l'allocazione della memoria è relativamente costosa) e quindi cercare la matrice (che non può nemmeno essere una ricerca binaria poiché la matrice è non ordinato).

Per motivi di scienza, però, ho creato due eseguibili che eseguono ogni stile 1 milione di volte e li cronometrano.

Con allKeys:

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

Con objectForKey:

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

Ovviamente, vari fattori possono influenzare questo - dimensioni del dizionario, memorizzazione nella cache del valore restituito da allKeys, ecc. Non mi aspetterei che ci sia un caso in cui la ricerca dell'array sia più veloce della ricerca del dizionario, comunque.

Answer 2

Non vedo come richiedere l'array allKeys potrebbe essere più veloce, altrimenti NSDictionary farebbe almeno l'equivalente internamente.

EDIT: suppongo che potresti costruire un caso in cui il metodo allKeys sarebbe più veloce - impiegando molto tempo nel metodo hash della tua chiave, ma non nel tuo Metodo isEqual: , ad esempio. E potresti anche scambiare un'implementazione folle con NSDictionary in cui vengono scambiati anche (poiché NSDictionary è astratto.)

Answer 3

Quando si considerano domande sul rendimento come questa, tenere presente che le classi di dati Foundation scambiano le loro strutture di dati sottostanti a seconda del numero di oggetti in esse memorizzati. Ad esempio, penso che un piccolo NSArray utilizzi effettivamente una tabella hash per l'archiviazione fino a quando non raggiunge una certa dimensione.