puedo comprobar la presencia de una llave en un NSDictionary de dos maneras:¿Qué método de comprobación para ver si un NSDictionary contiene una clave particular es más rápido?
BOOL containsKey = [[dictionary allKeys] containsObject:foo];
BOOL containsKey = ([dictionary objectForKey:foo] != nil);
cuál es el método más rápido, y por qué?
Una búsqueda de hash debe ser más rápido en general, que va sobre todas las claves del diccionario, la creación de una serie de ellos (la asignación de memoria es relativamente costosa) y luego buscar en la matriz (que ni siquiera puede ser una búsqueda binaria ya que la matriz no está ordenada).
Por el bien de la ciencia, sin embargo, hice dos ejecutables que solo ejecutan cada estilo 1 millón de veces y los sincronicé.
Con AllKeys:
real 0m4.185s
user 0m3.890s
sys 0m0.252s
Con objectForKey:
real 0m0.396s
user 0m0.189s
sys 0m0.029s
Obviamente, varios factores pueden influir en esto - tamaño del diccionario, el almacenamiento en caché los AllKeys valor de retorno, etc. Yo no esperaría no obstante, hay un caso en el que la búsqueda en el array es más rápida que la búsqueda en el diccionario.
No veo cómo pedir la matriz allKeys podría ser más rápido, de lo contrario, NSDictionary haría al menos el equivalente internamente.
EDIT: supongamos que usted podría construir un caso en el que el método allKeys sería más rápido - tomando mucho tiempo en el método de su clave hash, pero no en su método isEqual:, por ejemplo. Y también se puede intercambiar en una implementación loco por NSDictionary en el que se intercambian, también (desde NSDictionary es abstracta.)
De acuerdo. Pedir todas las Llaves te dará un NSArray que contiene Objeto debe buscar iterativamente buscando foo.objectForKey, por otro lado, usará un hash para calcular la ubicación de foo en el diccionario para que la existencia de foo se pueda determinar directamente. –
Cuando piense en preguntas de rendimiento como esta, tenga en cuenta que las clases de datos de Foundation intercambian sus estructuras de datos subyacentes según la cantidad de objetos que almacene en ellas. Por ejemplo, creo que un pequeño NSArray realmente usa una tabla hash para almacenamiento hasta que alcanza un cierto tamaño.
¿No es más probable que sea al revés donde una tabla hash se vuelve más beneficiosa? Probar unos 10 objetos para la igualdad es trivial. Sin embargo, tiene varios miles de objetos y una tabla hash se convierte en una clara victoria. –
Podrías tener razón, recuerdo que alguien escribió un artículo (junto con puntos de referencia) sobre esto hace algún tiempo, pero no lo he pensado mucho desde entonces. –
http://ridiculousfish.com/blog/posts/array.html sería la publicación en la que estás pensando –
"¿Muestra su trabajo?" Tienes las mismas herramientas que nosotros. Debe intentar perfilar el código diferente si quiere saber la respuesta a algo como esto. – danielpunkass
Daniel tiene toda la razón, esta era una forma muy perezosa de obtener la respuesta a una pregunta fácil de probar. Pero obtuve una muy buena respuesta y algunos resultados de rendimiento real, así que gracias a todos por dejarme ser un poco flojo. – alfwatt
Me da la impresión de que la línea "Por favor, muestre su trabajo" desagrada a la gente en la pregunta anterior, pero pensé que el objetivo del desbordamiento de la pila es tener respuestas a todo tipo de preguntas básicas, ¿no? Entonces, para aclarar, no pregunté esto porque no sé la respuesta, no pude averiguarlo o ser un imbécil grosero. Más bien, debido a que la respuesta no es inmediatamente obvia a menos que esté familiarizado con las colecciones de la Fundación, parecía una buena pregunta y respuesta para tener disponible. – alfwatt