实时更新每个用户好友之间的相对排行榜
我一直在开发应用程序的一个功能来实现排行榜 - 基本上根据用户的分数对用户进行排名。我目前正在跟踪个人的分数。我的想法是，这个排行榜应该是相对的而不是绝对的，即不是在整个网站上排名前 10 名得分最高的用户，而是在用户的朋友网络中排名前 10 名。这看起来更好，因为每个人都有机会成为他们网络中的第一名，并且对于那些对此类事情感兴趣的人来说，有一种友好的竞争形式。我已经存储了每个用户的分数，因此挑战是如何以有效的方式实时计算该分数的排名。我使用 Google App Engine，因此有一些好处和限制（例如，IN [array]）查询对数组的每个元素执行子查询，并且每个语句也限制为 30 个元素
例如
1st Jack 100
2nd John 50
Here是我想出的方法，但它们似乎都效率低下，我认为这个社区可以想出更优雅的方法。我的感觉是，任何解决方案都可能使用 cron 来完成，并且我将存储每日排名和列表顺序以优化读取操作，但如果有更轻量级和实时的东西，那就太酷了
- 拉取所有用户的列表网站按分数排序。 对于每个用户，从该列表中选择他们的朋友并创建新的排名。 存储排名和列表顺序。 每日更新。 缺点 - 如果我有很多用户，这将永远需要
2a。为每个用户选择他们的朋友并为每个朋友选择分数。 对该列表进行排序。 存储排名和列表顺序。 每日更新。 记录每个用户的最后位置，以便预先存在的列表可以用于下次更新的重新排序，以使其更加高效（可以节省排序时间）
2b。与上面相同，只是只计算最近一天查看过的个人资料的人员的排名和列表顺序 缺点 - 排名仅针对第二个查看个人资料的人而言是最新的
Ive been working on a feature of my application to implement a leaderboard - basically stack rank users according to their score. Im currently tracking the score on an individual basis. My thought is that this leaderboard should be relative instead of absolute i.e. instead of having the top 10 highest scoring users across the site, its a top 10 among a user's friend network. This seems better because everyone has a chance to be #1 in their network and there is a form of friendly competition for those that are interested in this sort of thing. Im already storing the score for each user so the challenge is how to compute the rank of that score in real time in an efficient way. Im using Google App Engine so there are some benefits and limitations (e.g., IN [array]) queries perform a sub-query for every element of the array and also are limited to 30 elements per statement
For example
1st Jack 100
2nd John 50
Here are the approaches I came up with but they all seem to be inefficient and I thought that this community could come up with something more elegant. My sense is that any solution will likely be done with a cron and that I will store a daily rank and list order to optimize read operations but it would be cool if there is something more lightweight and real time
- Pull the list of all users of the site ordered by score.
For each user pick their friends out of that list and create new rankings.
Store the rank and list order.
Update daily.
Cons - If I get a lot of users this will take forever
2a. For each user pick their friends and for each friend pick score.
Sort that list.
Store the rank and list order.
Update daily.
Record the last position of each user so that the pre-existing list can be used for re-ordering for the next update in order to make it more efficient (may save sorting time)
2b. Same as above except only compute the rank and list order for people who's profiles have been viewed in the last day
Cons - rank is only up to date for the 2nd person that views the profile
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果与读取相比，写入非常罕见（大多数键值存储中的一个关键假设，而不仅仅是这些；-），那么当您需要更新分数（写入）时，您可能更愿意花时间而不是获取相对排行榜（阅读）。具体来说，当用户的分数发生变化时，为他们的每个朋友排队任务以更新他们的“相对排行榜”，并将这些排行榜保留为列表属性（确实保持顺序！-）适当排序（是的，后者是非规范化 - 它是通常需要非规范化，即适当地复制信息，以充分利用键值存储！-)。
当然，当友谊（用户与用户的连接）消失或出现时，您也会更新相对排行榜，但这些应该（我想）比分数更新更罕见；-)。
如果写入非常频繁，因为您不需要完全精确的最新信息（即，它不是财务/会计信息；-），您仍然有许多可行的方法可以尝试。
例如，大的分数变化（较少见）可能会触发相对排行榜重新计算，而较小的分数（更频繁）会被隐藏起来，并且仅偶尔“当您有时间时”应用一次。如果没有关于各种幅度的更新频率、典型的网络友谊集群大小等的大概数字，很难更具体。我知道，像其他人一样，您想要一种完美的方法，无论大小和频率有多么不同，都适用有问题...但是，你就是找不到！-)
If writes are very rare compared to reads (a key assumption in most key-value stores, and not just in those;-), then you might prefer to take a time hit when you need to update scores (a write) rather than to get the relative leaderboards (a read). Specifically, when a user's score change, queue up tasks for each of their friends to update their "relative leaderboards" and keep those leaderboards as list attributes (which do keep order!-) suitably sorted (yep, the latter's a denormalization -- it's often necessary to denormalize, i.e., duplicate information appropriately, to exploit key-value stores at their best!-).
Of course you'll also update the relative leaderboards when a friendship (user to user connection) disappears or appears, but those should (I imagine) be even rarer than score updates;-).
If writes are pretty frequent, since you don't need perfectly precise up-to-the-second info (i.e., it's not financials/accounting stuff;-), you still have many viable approaches to try.
E.g., big score changes (rarer) might trigger the relative-leaderboards recomputes, while smaller ones (more frequent) get stashed away and only applied once in a while "when you get around to it". It's hard to be more specific without ballpark numbers about frequency of updates of various magnitude, typical network-friendship cluster sizes, etc, etc. I know, like everybody else, you want a perfect approach that applies no matter how different the sizes and frequencies in question... but, you just won't find one!-)
有一个可用于存储排名的 python 库：
http://code.google .com/p/google-app-engine-ranklist/
There is a python library available for storing rankings:
http://code.google.com/p/google-app-engine-ranklist/