Оптимизация iPhone * Pathfinding - поможет ли NSDictionary?

Question

У меня есть довольно большая функция поиска пути A *, которая часто вызывается и должна быть помещена в другой поток, потому что в противном случае моя игра будет зависать. Я пришел из Java-фона и недавно прочитал обсуждение скорости работы HashMap (по сути, эквивалент NSDictionary) и различных реализаций, которые вы можете использовать. Мне любопытно, насколько быстрым является NSDictionary и нашел ли кто-либо его жизнеспособным вариантом для работы со множеством немедленного и временного выделения объектов, или он слишком медленный для этого.

В настоящее время я использую NSMutableArray для открытых и закрытых списков в алгоритме A * - я бы заменил закрытый список на NSMutableDictionary из-за O (1) setObject: forKey и removeObject: forKey, а также создал NSMutableDictionary, который "отражает" открытый список. Данные пути хранятся в большом NSMutableArray - я бы оставил это как есть, потому что доступ к индексу достаточно быстрый (конечно).

Итак, мой вопрос ... будет ли это заметным улучшением скорости, или я должен свернуть свои собственные списки и / или карты? Я просто не уверен, что NSDictionary делает , и я хотел бы знать.

Answer 1

Если вам интересно, как оптимизировать A * , сначала я бы спросил, используете ли вы независимые от платформы расширения, такие как Итеративное углубление A * ( aka IDA * ), какую эвристику вы используете, и если вы используете кеширование (таблицы транспонирования, базы данных шаблонов). Вопросы, которые вы задаете, на данный момент слишком близки к цели, потому что вы оптимизируете части системы, которые, вероятно, не будут вас сдерживать.

Посмотрите эти слайды курса ( особенно лекция 10 и < a href = "http://www.cs.ualberta.ca/~jonathan/Courses/657/Notes/11.Evaluations.pdf" rel = "nofollow noreferrer"> лекция 11 )

Answer 2

Абсолютно это имеет значение - я недавно изменил наивную реализацию A *, используя NSArray (есть что-то в списке? повторять, чтобы узнать ...) для списков и смежных областей для NSDictionary (в списке? objectForKey!) и увеличение производительности от неприемлемого до приемлемого при не слишком большой работе.