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 回答