Ottimizzare un iPhone * Pathfinding - NSDictionary farà il trucco?

Question

Ho una funzione di pathfinding A * piuttosto grande che viene chiamata frequentemente e deve essere inserita in un altro thread perché altrimenti farà balbettare il mio gioco. Vengo da un background Java e di recente ho letto una discussione sulla velocità di HashMap (essenzialmente l'equivalente di NSDictionary) e le diverse implementazioni che è possibile utilizzare. Sono curioso di sapere quanto sia veloce NSDictionary e se qualcuno lo abbia trovato un'opzione praticabile per gestire molte allocazioni di oggetti immediate e temporanee o se è troppo lento per quello.

Attualmente sto usando un NSMutableArray per le liste aperte e chiuse dell'algoritmo A * - Sostituirei la lista chiusa con NSMutableDictionary a causa di O (1) setObject: forKey e removeObject: forKey e anche la creazione di un NSMutableDictionary che "rispecchia" " l'elenco aperto. I dati di tracciamento sono archiviati in un grande NSMutableArray - lo lascerei così com'è perché l'accesso all'indice è abbastanza veloce (ovviamente).

Quindi la mia domanda è ... sarebbe un notevole miglioramento della velocità o dovrei rotolare i miei elenchi e / o mappe? Non sono sicuro di cosa NSDictionary faccia e vorrei saperlo.

Answer 1

Se ti stai chiedendo come ottimizzare A * , ti chiedo innanzitutto se stai utilizzando estensioni indipendenti dalla piattaforma, come Iterative Deepening A * ( aka IDA * ), che tipo di euristica stai usando e se stai usando la cache (tabelle di trasposizione, database di pattern). Le domande che stai ponendo sono troppo vicine al metallo per il momento, perché stai ottimizzando parti del sistema che probabilmente non ti trattengono.

Dai un'occhiata a queste slide del corso ( in particolare lezione 10 e < a href = "http://www.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf" rel = "nofollow noreferrer"> lezione 11 )

Answer 2

Assolutamente fa la differenza - Di recente ho cambiato un'implementazione ingenua di A * usando NSArray (è qualcosa nella lista? iterate per scoprirlo ...) per le liste e gli adiacenti per NSDictionary (nella lista? objectForKey!) e aumento delle prestazioni da non accettabile a accettabile senza troppo lavoro.