Как быстро код

Question

Я занимаюсь разработкой игры. Я храню свои игровые объекты на этой карте:

std::map<std::string, Object*> mObjects;

std::string - это ключ / имя объекта, чтобы найти его в коде. На некоторые объекты очень просто указывать, например: mObjects["Player"] = .... Но я боюсь, что это замедляется из-за выделения std :: string в каждом поиске на этой карте. Поэтому я решил использовать int в качестве ключа на этой карте.

Первый вопрос: действительно ли это будет быстрее?

И второе, я не хочу удалять текущий доступ к объектам моего типа, поэтому я нашел способ: сохранить crc строку, вычисляемую как ключ. Например:

Object *getObject(std::string &key)
{
   int checksum = GetCrc32(key);
   return mObjects[checksum];
}

Object *temp = getOject("Player");

Или это плохая идея? Для расчета crc я бы использовал boost::crc. Или это плохая идея, и вычисление контрольной суммы намного медленнее, чем поиск по карте с типом ключа std::string?

Answer 1

Вычисление CRC наверняка будет медленнее, чем любое отдельное сравнение строк, но вы можете рассчитывать на сравнение log2N перед поиском ключа (например, 10 сравнений на 1000 ключей), поэтому это зависит от размера вашего map.CRC также может привести к коллизиям, поэтому он подвержен ошибкам (вы можете относительно легко обнаружить коллизии, и, возможно, даже обработать их, чтобы получить правильные результаты в любом случае, но вы должны быть очень осторожны, чтобы сделать их правильными).

Вы можете попробовать unordered_map<> (возможно, называется hash_map), если ваша среда C ++ предоставляет такую ​​возможность - она ​​может быть или не быть быстрее, но не будет отсортирована, если вы выполняете итерацию.Хеш-карты являются еще одним компромиссом:

• время хеширования, вероятно, аналогично времени для вашего CRC, но
• впоследствии они часто могут искать непосредственно значение, вместо того, чтобывыполнить бинарное дерево в карте нормалей
• , они разбивают немного логики для обработки коллизий.

(Глупо, но если вы можете продолжать использовать целые числа и они могут быть смежными, тогда помните, что вы можете заменить поиск массивом, который намного быстрее. Если целые числа на самом деле не являются смежными, но не очень разреженными, вы можете использовать разреженный индекс, например, массивиз 10000 коротких целых, которые являются индексами в 1000 упакованных записей).

Суть в том, что если вам нужно спросить, вы должны реализовать эти альтернативы и сравнить их спосмотрите, какие из них действительно лучше всего работают с вашим конкретным приложением, и действительно ли они имеют какое-либо ощутимое значение.Любой из них может быть лучшим в определенных обстоятельствах, и если вам недостаточно внимания, чтобы серьезно их сравнить, это однозначно означает, что подойдет любой из них.

Answer 2

Первый вопрос: действительно ли это будет быстрее?

да - вы сравниваете int несколько раз, а несколько раз сравниваете потенциально большую карту строк произвольной длины.

checksum: Or this is bad idea?

это точно не гарантированно быть уникальным.это ошибка, ожидающая укуса.

что я бы сделал:

используйте несколько коллекций и обеспечьте безопасность типов:

// perhaps this simplifies things enough that t_player_id can be an int?
std::map<t_player_id, t_player> d_players;
std::map<t_ghoul_id, t_ghoul> d_ghouls;
std::map<t_carrot_id, t_carrot> d_carrots;

более быстрый поиск, больше безопасности типов.меньшие коллекции.меньшие выделения / изменения размера .... и так далее ... если ваше приложение очень тривиально, то это не имеет значения.используйте этот подход в будущем и настройте после профилирования / по мере необходимости для существующих программ.

удачи

Answer 3

Для фактической производительности вам нужно профилировать код и посмотреть его. Но я хотел бы использовать hash_map . Хотя это не входит в стандартную библиотеку C ++, большинство популярных дополнений предоставляют его. Это обеспечивает очень быстрый поиск.

Answer 4

Если вы действительно хотите знать, что вам нужно профилировать свой код и посмотреть, сколько времени займет функция getObject.Лично я использую valgrind и KCachegrind для профилирования и рендеринга данных в системе UNIX.

Я думаю, что использование id было бы быстрее.Сравнение int быстрее, чем string, поэтому ...