4

我正在开发游戏。我将我的游戏对象存储在这张地图中:

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

4

4 回答 4

6

计算 CRC 肯定比任何单一的字符串比较都要慢,但您可以期望在找到键之前进行 log2N 比较(例如 1000 个键的 10 次比较),因此这取决于您的map. CRC 也可能导致冲突,因此很容易出错(您可以相对容易地检测到冲突,甚至可能处理它们以获得正确的结果,但您必须非常小心才能正确处理)。

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

  • 散列的时间可能与您的 CRC 的时间相似,但是
  • 之后,他们通常可以直接寻找该值,而不必在法线贴图中进行二叉树遍历
  • 他们预先捆绑了一些逻辑来处理冲突。

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

底线是,如果您足够关心询问,您应该实施这些替代方案并对它们进行基准测试,以查看哪些方案最适合您的特定应用程序,以及它们是否真的产生了任何明显的差异。在某些情况下,它们中的任何一个都可能是最好的,如果你不关心认真比较它们,那么这显然意味着它们中的任何一个都可以。

于 2011-04-08T09:58:09.337 回答
3

第一个问题:真的会更快吗?

是的-您正在比较一个 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;

更快的搜索,更多的类型安全。较小的收藏。较小的分配/调整大小......等等......如果您的应用程序非常简单,那么这无关紧要。继续使用这种方法,并在分析后/根据现有程序的需要进行调整。

祝你好运

于 2011-04-08T10:01:58.927 回答
3

对于实际性能,您需要分析代码并查看它。但我很想使用hash_map。尽管它不是 C++ 标准库的一部分,但大多数流行的实现都提供了它。它提供了非常快速的查找。

于 2011-04-08T09:55:15.797 回答
1

如果您真的想知道,您必须分析您的代码并查看函数 getObject 需要多长时间。我个人使用 valgrind 和 KCachegrind 在 UNIX 系统上分析和呈现数据。

我认为使用 id 会更快。比较 int 比比较 string 更快,所以...

于 2011-04-08T10:01:25.323 回答