我有一个相当大的 A* 寻路函数，它经常被调用，并且必须放入另一个线程中，否则它会让我的游戏卡顿。我有 Java 背景，最近阅读了一篇关于 HashMap（本质上相当于 NSDictionary）的速度以及可以使用的不同实现的讨论。我很好奇 NSDictionary 有多快，以及是否有人发现它是处理大量即时和临时对象分配的可行选择，或者它是否太慢了。
目前，我在 A* 算法中使用 NSMutableArray 作为打开和关闭列表 - 由于 O(1) setObject:forKey 和 removeObject:forKey，我将用 NSMutableDictionary 替换关闭列表，并且还创建一个 NSMutableDictionary “镜像”开放列表。路径数据存储在一个大的 NSMutableArray 中 - 我会保持原样，因为索引访问足够快（当然）。
所以我的问题是......这会是一个明显的速度改进还是我应该滚动自己的列表和/或地图？我只是不确定 NSDictionary 做什么，我想知道。
I've got a pretty big A* pathfinding function that gets called frequently and has to be put in another thread because otherwise it will make my game stutter. I come from a Java background, and recently read a discussion about the speed of HashMap's (essentially the equivalent of NSDictionary) and the different implementations you can use. I'm curious how fast NSDictionary is and whether anyone has found it to be viable option for dealing with lots of immediate and temporary object allocations, or whether it's too slow for that.
Currently I'm using an NSMutableArray for the open and closed lists in the A* algorithm - I would be replacing the closed list with NSMutableDictionary due to the O(1) setObject:forKey and removeObject:forKey, and also creating an NSMutableDictionary that "mirrors" the open list. The pathing data is stored in a big NSMutableArray - I would leave this as-is because index access is fast enough (of course).
So my question is... would this be a noticeable speed improvement or should I roll my own lists and/or maps? I'm just not sure what NSDictionary does and I'd like to know.
发布评论
评论（2）
如果您想知道如何优化
A*，我首先会问您是否使用与平台无关的扩展，例如迭代加深A*（又名>IDA*），您正在使用哪种启发式方法，以及您是否正在使用缓存（换位表、模式数据库）。目前，您提出的问题太接近实际情况了，因为您正在优化系统的某些部分，而这些部分可能不会阻碍您。看看这些课程幻灯片（尤其是讲座 10 和 讲座11）
If you're wondering how to optimize
A*, I'd first ask you if you're using platform-independent extensions, like Iterative DeepeningA*(akaIDA*), what kind of a heuristic you're using, and if you're using caching (transposition tables, pattern databases). The questions you're asking are too close to the metal for the moment, because you're optimizing parts of the system which are likely not holding you back.Have a look at these course slides (especially lecture 10 and lecture 11)
这绝对是有影响的 - 我最近使用 NSArray （列表中的某些内容？迭代找出...）更改了 A* 的简单实现，用于 NSDictionary 的列表和相邻项（列表中？objectForKey！）并提高了性能从不可接受到可以接受，不需要太多的工作。
Absolutely it makes a difference - I recently changed a naive implementation of A* using NSArray (is something in the list? iterate to find out...) for the lists and adjacents for NSDictionary (in the list? objectForKey!) and increased performance from not acceptable to acceptable with not too much work.