代码有多快

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比较(例如1000个密钥的10次比较),所以它取决于你的大小map.CRC也可能导致冲突,因此容易出错(您可以检测到相对容易检测到的冲突,甚至可能处理它们以获得正确的结果,但您必须非常小心才能正确).

如果您的C++环境提供了一个unordered_map<>(可能被称为hash_map),您可以尝试(可能被调用) - 它可能会或可能不会更快但如果您进行迭代则不会被排序.哈希映射是另一个妥协:

(傻点,但是如果你可以继续使用整数并且它们可以是连续的,那么请记住你可以用更快的数组替换查找.如果整数实际上不是连续的,但不是特别稀疏,你可以使用稀疏索引,例如10000个短整数的数组,它们是1000个打包记录的索引).

最重要的是,如果你足够关心,你应该实施这些替代方案并对它们进行基准测试,以确定哪种方法最适合您的特定应用,以及它们是否真正产生任何实际差异.在某些情况下,它们中的任何一个都是最好的,如果你不够认真地比较它们,那么它显然意味着它们中的任何一个都会做.