用户匹配算法 [英] User matching algorithm

问题描述

所以这个问题，我们有匹配的用户向其他在线用户。然而，它不只是一个一对一的匹配。甲用户被给予一个选择的其他5个用户从，然后将其标记为可见，不应该再次显示时要显示为另一个5个用户的用户请求选择。更多的人可以在此过程中联机。

So this problem we have users matching to other online users. However it is not just a one to one match. A user is given a selection of 5 other users to choose from, which are then marked as seen and should not be shown again when the user requests for another 5 users to be shown. More people can come online during the process.

现在的问题是，我想办法为每个用户显示在其他用户的选择，与Redis的，但一个算法主要是什么即时通讯寻找。我想实现这个最快可能的方式，使用Redis的如果可能的话，但我也可以对数据库的调用，如果它的需要。

The problem is, I want a way for each user to be shown in the selection for other users, with redis but an algorithm is mostly what im looking for. I'm trying to implement this in the fastest way possible, using redis if possible but I can also make calls to the database if it's needed.

我目前的解决方案如下，希望有人会有一些提示，从O（N）改善这一要求。

My current solution is as follows, hopefully someone will have some tips to improve this from O(N) calls.

所以，每个用户都需要有一个的设置 USER_ID 取值的看到。我们可以有 onlineusers 的Redis的列表（队列）。当我们不断poppping用户从左边，直到我们找到一个不在用户的见过的设置，将其保存，添加到用户看到的，然后将其推右侧。然后，一旦我们得到5那些我们留下逼退那些我们留下弹出那些已经看到了。

So each user needs to have a seen set of user_ids. We can have a redis list (queue) of onlineusers. Where we keep poppping users from the left until we find one that isn't in the user's seen set, save it, add to users seen, then push it on the right. Then once we get 5 of those we left push back the ones we left popped off that were already seen.

这是最好的，我能想到的不过是我们要找到5个用户为这一个用户从选择O（N）各一次。这是可能的（虽然不太可能），该用户已经看到了大量且突然离开整个列表。

This is the best I could think of however it is O(N) each time we want to find 5 users for this one user to select from. It's possible (though not likely) that the user has seen a huge amount and is popping off the whole list.

要帮助更好的理解。一个naiive方法是让每一个用户包含在一组的形式，所有在线用户的副本。那么接下来，我们简单地弹出5组随机成员。但是，这不能工作，因为孤单没有足够的空间，并且每个用户上线，他们不得不被添加到每个用户的在线用户的时间。或者当他们脱机和这些操作是O（N），考虑到他们是在澳做了N个用户删除（1）

To help understand this better. A naiive approach is to have every single user contain a copy of all online users in the form of a set. So then we simply pop 5 random set members. But this can't work because theres not enough space, and each time a user goes online they'd have to be added to each user's online users. Or deleted when they go offline and those operations are O(N) considering they are done for N users at O(1)

没有人有任何的提示来匹配用户与其他用户？

Does anyone have any tips to match users with other users?

推荐答案

这将是很好的知道哪些类型的数据，我们正在谈论。有多少用户存在吗？多少都会在网上平均水平？如何为相对于所有用户（稀疏与密集的）？

It would be good to know about which kind of data we are talking about. How many users exist? How many will be online at average? How is the ratio of "seen users" compared to all users (sparse vs. dense)?

修改你的算法 不要弹出第一，但可供选择的一组在线用户的随机元素。这应该提高平衡，并可能有助于摊余复杂性取决于这两套的比例！

Modification of your algorithm Don't pop the first but choose a random element from the set of online users. This should improve balancing and may help with amortized complexity depending on the ratio of these two sets!

替代算法（更有条理;还是坏的最坏情况，应该是一件好事，如果稀疏的见过的）

Alternative Algorithm (more structured; still bad worst-case; should be good if sparse seen)

• 在保留的见过的是一个平衡树（O（log n）的插入）
• 在保留的在线的是一个平衡树。
• 虽然没有足够多的用户选择：
  • 在看到搜索第一缝隙的（例如[0,1,3,7] - > 2; O（log n）的，根据<一href="http://stackoverflow.com/questions/11385896/find-the-first-missing-number-in-a-sorted-list">SO-link)
  • 搜索第一个用户> =间隙值（O（log n）的）
  • 如果用户的LT; next_gap_neighbor（例如在上面：3;下一个值后回升差距2）
  • - >接
  • 否则
  • - >添加选择隙值的暂时的（这一刻，模型的决定多久更新的在线的）来的见过的OR限制搜索莫名其妙地>选择隙值（O（log n）的）
  • Keep seen as a balanced tree (O(log n) insertion)
  • Keep online as a balanced tree.
  • While not enough users chosen:
    • Search for first gap in seen (e.g. [0,1,3,7] -> 2; O(log n) according to SO-link)
    • Search for first user >= gap-value (O(log n))
    • If user < next_gap_neighbor (in example above: 3; next value after picked gap 2)
    • -> pick
    • Else
    • -> add chosen-gap-value temporarily (for this moment; model-decision how often to update online) to seen OR limit search somehow to > chosen-gap-value (O(log n))

    根据数据，这应该工作非常好，如果数据是巨大的，见过的是稀疏的！

    Depending on the data, this should work very good if data is huge and seen is sparse!

    这篇关于用户匹配算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！