Otimizando Um iPhone * Pathfinding - Will NSDictionary fazer o truque?

Question

Eu tenho um muito grande A * função pathfinding que é chamado com freqüência e tem que ser colocado em outro segmento, porque caso contrário ele irá fazer o meu gaguejar jogo. Eu venho de um fundo de Java, e li recentemente uma discussão sobre a velocidade do HashMap do (essencialmente o equivalente a NSDictionary) e as diferentes implementações que você pode usar. Estou curioso para saber o quão rápido NSDictionary é e se alguém tem encontrado para ser opção viável para lidar com lotes de alocações de objetos imediatos e temporários, ou se é demasiado lento para isso.

Atualmente estou usando um NSMutableArray para as listas abertas e fechadas no algoritmo A * - eu estaria substituindo a lista fechada com NSMutableDictionary devido ao O (1) setObject: forKey e removeObject: forKey, e também a criação de um NSMutableDictionary que "espelhos" lista aberta. Os dados pathing é armazenado em um grande NSMutableArray -. Gostaria de deixar isso como-é porque o acesso índice é rápido o suficiente (é claro)

Assim, a minha pergunta é ... isso seria uma melhoria de velocidade perceptível ou devo fazer a minha própria lista e / ou mapas? Eu não sou apenas certo o que NSDictionary faz e eu gostaria de saber.

Answer 1

Se você está querendo saber como A* otimizar, eu primeiro perguntar se você estiver usando extensões independentes de plataforma, como iterativo aprofundamento A* (aka IDA*), que tipo de heurística que você está usando, e se você está usando o cache (quadros de transposição, bancos de dados padrão). As perguntas que você está pedindo é demasiado próximo ao metal para o momento, porque você está otimizando partes do sistema que provavelmente não são exploração de volta.

Tenha um olhar em esses slides curso ( especialmente palestra 10 e < a href = "http://www.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf" rel = "nofollow noreferrer"> lecture 11 )

Answer 2

Absolutamente ele faz a diferença - (?! Na lista objectForKey) Eu mudei recentemente uma implementação ingênua da A * usando NSArray (? É algo na lista iterate para descobrir ...) para as listas e adjacentes para NSDictionary e aumento do desempenho de não aceitável aceitável com não muito trabalho.