c++ - 具有变化值的固定节点集的最佳树/堆数据结构+需要前 20 个值？

Question

我正在用 C++ 编写类似游戏的东西，其中我有一个数据库表，其中包含每个用户的当前分数。我想在游戏开始时将该表读入内存，在游戏进行时根据每个用户的行为快速更改每个用户的分数，然后在游戏结束时将当前分数写回数据库。我还希望能够找到得分最高的 20 个左右的用户。在游戏进行的短时间内不会添加或删除任何用户。我还没有尝试过，但是在玩游戏期间更新数据库可能会花费太多时间。

• 一组固定的用户(可能是 10,000 到 50,000 名用户)
• 将用户 ID 映射到他们的分数和其他用户特定信息。
• 用户 ID 将是 auto_increment 值。
• 如果该结构具有高内存开销，那可能不是问题。
• 如果程序在游戏过程中崩溃，只需重新启动即可。
• 非常喜欢已经可用的东西，例如开源/公共(public)领域代码。
• 快速获取用户的当前分数。
• 快速添加到用户的当前分数(并返回他们的当前分数)
• 快速获得得分最高的 20 个用户。
• 没有删除。
• 除了第一次创建结构时没有插入，需要多长时间并不重要。
• 获取前 20 名用户只会每五到十秒发生一次，但获取/添加的频率会更高。

如果不是最后一次，我可以创建一个等于 sizeof(user) * max(user id) 的内存块，并将每个用户放在 user id * sizeof(user) 用于快速访问。我应该这样做加上 Top 20 特征的一些其他结构，还是有一个结构可以一起处理所有这些？

Answer 1

使用 std::map。万一它出现在您的个人资料中，这种情况极不可能发生，您可能会考虑更改为更具异国情调的内容。 50,000 个用户的内存开销大约为一两兆字节。

我怀疑每 5 到 10 秒迭代一个有 50k 个条目的 map 来找到最高分，会引入大量开销。但是，如果确实如此，要么使用 Boost 多索引容器，要么为高分维护一个单独的结构(一个堆，或者只是一个指向当前前 20 名的指针数组，按顺序排列)。仅使用 20 的数组/vector ，增加分数的代码可能看起来像这样(假设分数只上升，不下降):

player.score += points;
if (player.score > hiscores[19]->score) {
    hiscore_dirty = true;
}

以及获得高分的代码:

if (hiscore_dirty) {
    recalculate_hiscores();
    hiscore_dirty = false;
}
std::for_each(hiscores.begin(), hiscores.end(), do_something);

如果你的“自动递增”和“不删除”策略是永远固定的(即你永远不会从数据库中删除用户)，因此用户 ID 确实是从 0 到限制的连续范围，那么你应该只是使用 std::vector 而不是 std::map。