Optimizando A * Pathfinding iPhone: ¿NSDictionary hará el truco?

Question

Tengo una función de búsqueda de caminos A * bastante grande que se llama con frecuencia y tiene que colocarse en otro hilo porque, de lo contrario, hará que mi juego se tambalee. Vengo de un entorno Java, y recientemente leí una discusión sobre la velocidad de HashMap (esencialmente el equivalente a NSDictionary) y las diferentes implementaciones que puede usar. Tengo curiosidad por lo rápido que es NSDictionary y si alguien ha encontrado que es una opción viable para manejar muchas asignaciones de objetos inmediatas y temporales, o si es demasiado lento para eso.

Actualmente estoy usando un NSMutableArray para las listas abiertas y cerradas en el algoritmo A *. Reemplazaría la lista cerrada con NSMutableDictionary debido al setObject: forKey y removeObject: forKey, y también crearía un NSMutableDictionary que " espejo " la lista abierta. Los datos de rastreo se almacenan en un gran NSMutableArray, dejaría esto como está porque el acceso al índice es lo suficientemente rápido (por supuesto).

Entonces, mi pregunta es ... ¿esto sería una mejora notable de la velocidad o debería rodar mis propias listas y / o mapas? Simplemente no estoy seguro de lo que hace NSDictionary y me gustaría saber.

Answer 1

Si se está preguntando cómo optimizar A * , primero le preguntaría si está usando extensiones independientes de la plataforma, como Iterative Deepening A * ( también conocido como IDA * ), qué tipo de heurística está utilizando y si está utilizando el almacenamiento en caché (tablas de transposición, bases de datos de patrones). Las preguntas que estás haciendo están demasiado cerca del metal por el momento, porque estás optimizando partes del sistema que probablemente no te frenen.

Eche un vistazo a estas diapositivas del curso ( especialmente clase 10 y < a href = "http://www.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf" rel = "nofollow noreferrer"> lecture 11 )

Answer 2

Absolutamente hace una diferencia: recientemente cambié una implementación ingenua de A * utilizando NSArray (hay algo en la lista? Es necesario averiguar ...) para las listas y los complementos de NSDictionary (en la lista? objectForKey!) y un mayor rendimiento de no aceptable a aceptable sin demasiado trabajo.