2

我有一个非常大的 A* 寻路函数，它经常被调用并且必须放在另一个线程中，否则它会使我的游戏卡顿。我来自 Java 背景，最近阅读了有关 HashMap（基本上相当于 NSDictionary）的速度以及您可以使用的不同实现的讨论。我很好奇 NSDictionary 有多快，以及是否有人发现它是处理大量即时和临时对象分配的可行选择，或者它是否太慢了。

目前，我在 A* 算法中使用 NSMutableArray 作为打开和关闭列表 - 由于 O(1) setObject:forKey 和 removeObject:forKey，我将用 NSMutableDictionary 替换关闭列表，并且还创建一个 NSMutableDictionary “镜像”打开列表。路径数据存储在一个大的 NSMutableArray 中——我会保持原样，因为索引访问速度足够快（当然）。

所以我的问题是......这是否会显着提高速度，或者我应该推出自己的列表和/或地图？我只是不确定 NSDictionary做了什么，我想知道。

4

2 回答 2

3

如果您想知道如何优化A*，我首先会问您是否使用了与平台无关的扩展，例如迭代深化A*（又名IDA*），您使用的是哪种启发式算法，以及您是否使用缓存（转置表、模式数据库）。目前，您提出的问题与金属太接近了，因为您正在优化系统中可能不会阻碍您的部分。

看看这些课程幻灯片（尤其是第10课和第 11 课）

于 2009-10-21T18:50:48.610 回答
0

绝对有区别 - 我最近使用 NSArray 更改了 A* 的幼稚实现（列表中有东西吗？迭代找出...）用于 NSDictionary 的列表和相邻项（在列表中？objectForKey！）并提高了性能从不接受到接受，不需要太多的工作。

于 2011-03-21T11:30:59.373 回答