A * Pathfinding iPhoneの最適化-NSDictionaryはトリックを行いますか？

Question

非常に大きなA *パスファインディング関数があります。これは頻繁に呼び出され、別のスレッドに配置する必要があります。そうしないと、ゲームが途切れてしまいます。私はJavaのバックグラウンドから来ました。最近、HashMapの速度（本質的にはNSDictionaryと同等）と使用できるさまざまな実装についての議論を読みました。 NSDictionaryの速さと、多くの即時および一時的なオブジェクト割り当てを処理するための実行可能なオプションであると誰かが見つけたのか、それとも遅すぎるのか、興味があります。

現在、A *アルゴリズムのオープンリストとクローズリストにNSMutableArrayを使用しています-O（1）setObject：forKeyおよびremoveObject：forKeyにより、クローズリストをNSMutableDictionaryに置き換え、さらに「ミラー」というNSMutableDictionary;オープンリスト。パスデータは大きなNSMutableArrayに格納されます-インデックスアクセスが十分に速いため（もちろん）、このままにします。

だから私の質問は...これは顕著な速度の改善でしょうか、それとも自分のリストやマップをロールするべきですか？ NSDictionaryが何をするのか わからないので、知りたいです。

Answer 1

A * を最適化する方法を知りたい場合は、まず、反復的な深化 A * などのプラットフォームに依存しない拡張機能を使用しているかどうかを尋ねます別名 IDA * ）、使用しているヒューリスティックの種類、およびキャッシュ（転置テーブル、パターンデータベース）を使用している場合。あなたがしていると思われないシステムの部分を最適化しているので、あなたが尋ねている質問は今のところ金属に近すぎます。

これらのコーススライド（特に講義10 および< a href = "http://www.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf" rel = "nofollow noreferrer">講義11 ）

Answer 2

絶対に違いがあります-最近、NSDictionaryのリストと隣接（リストにあるobjectForKey！）にNSArrayを使用してA *の素朴な実装を変更しました（リストに何かありますか？）あまり作業をせずに、許容できないレベルから許容可能なレベルにパフォーマンスを向上させました。