1

在游戏中，我试图保留用户列表并按分数排序，以便我可以在任何给定时间查询列表并返回（例如）按分数排名前十的用户。这个列表应该是线程安全的。我设想使用 userName 字符串作为键，值将是实现 Comparable 并具有 displayName 和 score 等属性的 User 对象。因此，User 对象将具有一个 compareTo 方法，该方法将比较 score 属性以确定其位置。

我正在考虑为此使用 ConcurrentSkipListMap，但据我所知，Map（而不是 Set）使用 key 进行排序。我想让列表按 User 对象的 score 属性排序，但仍然使用 Map 因为我需要能够访问任何给定用户并从线程修改他们的 score 属性。

似乎使用我自己的 Comparator 作为密钥并不能解决我的问题，因为我怀疑我是否可以访问相关的值进行比较。我可以使用 ConcurrentSkipListSet 但访问列表以修改单个用户的分数将是（我想）一项昂贵的操作（由于每次都需要迭代）。

谁能建议如何做到这一点？

4

3 回答 3

3

不，我不认为你可以。用于排序的比较器与用于索引的比较器相同。您可能必须维护 2 个集合。一种用于保持用户分数的顺序，用于按名称引用用户。

于 2010-09-21T18:08:05.010 回答
1

迈克尔是对的，你不能一边吃蛋糕一边吃；）

我认为你有3个选择：

  1. 使用地图可以快速更新用户的分数，并且在排序以找到最高分数时要付出代价。
  2. 使用按分数排序的SortedSet，以便快速找到最高分数，但更新用户分数时必须付出代价
  3. 维护两个数据结构，这样您就可以拥有 1 和 2 中最好的一个。例如，您将真实数据放在按分数排序的集合中，但还要维护用户名到集合或类似索引的映射。这样你总是有排序的分数，更新用户的分数只是查找，而不是搜索。您为此付出的代价是现在您在两个地方维护一些重复的信息，特别是考虑到并发访问，确保两个地方始终同步更新可能会很棘手。

我不会对 1 和 2 之间哪个更快做出假设。我会根据您的预期使用情况对它们进行尝试，并测量以查看最坏的情况。

如果您真的只对前 n 个分数感兴趣，那么可以单独维护该列表。因此，让您的用户名地图为每个人评分，但也要保持一小部分最高分（及其用户）。每次添加/更新某人的分数时，只需对照最高分数列表检查分数，如果它大于那里的最小分数，只需添加它并剔除较低的分数。这与上面的建议 3 类似，但开销较小，并且可能更易于维护。

于 2010-09-21T19:17:18.333 回答
1

get(key)取决于比较器（能够找到密钥）。您提出了一个比较器，该比较器将依赖于get(key)（访问键的映射值并基于该键进行比较）。这必然会导致无限递归和堆栈溢出（从好的方面来说，您在正确的网站上发帖！！）

于 2010-09-21T18:32:10.260 回答