小编典典

用户匹配算法

redis

因此,这个问题使我们的用户与其他在线用户匹配。但是,这不仅仅是一对一的比赛。给一个用户5个其他用户的选择,然后将其标记为可见,并且当该用户请求再显示5个用户时,不应再显示。在此过程中,更多的人可以上网。

问题是,我希望使用Redis在每个用户的选择中显示其他用户的方法,但是算法主要是我正在寻找的。我正在尝试以最快的方式实现这一点,如果可能的话,使用redis,但是如果需要的话,我也可以调用数据库。

我当前的解决方案如下,希望有人能从O(N)调用中获得一些改进的技巧。

因此,每个用户都需要有一个 看到
一套user_id秒。我们可以有个redis列表(队列)onlineusers。在此位置,我们从左向右弹出用户,直到找到不在用户 可见
集中的用户,将其保存,添加到已看到的用户中,然后将其向右推。然后,一旦获得其中的5个,我们就向后推回我们已经看到的剩下的弹出窗口。

这是我能想到的最好的方法,但是每次我们要为该用户选择5个用户时,它都是O(N)。用户有可能(尽管不太可能)看到了巨大的数量,并跳出了整个列表。

为了更好地理解这一点。幼稚的方法是让每个用户以集合的形式包含所有在线用户的副本。因此,我们简单地弹出5个随机集合成员。但这是行不通的,因为空间不足,每次用户上线时,都必须将其添加到每个用户的在线用户中。或当它们脱机并且那些操作为O(N)时被删除,考虑到它们已针对O(1)的N个用户完成

有没有人有将用户与其他用户匹配的提示?


阅读 1196

收藏
2020-06-20

共1个答案

小编典典

了解我们正在谈论的是哪种数据将是很好的。存在多少个用户?平均有多少人会在线?“可见用户”与所有用户的比例(稀疏与密集)相比如何?

修改算法 不要先弹出 算法 ,而是从在线用户集中选择随机元素。这将改善平衡,并可能有助于分摊复杂度,具体取决于这两套比率!

替代算法(结构更清晰;最坏的情况仍然很糟糕;如果稀疏 出现 ,应该会很好)

  • 始终 视为 平衡树(插入O(log n))
  • 保持 在线 平衡状态。
  • 虽然没有足够的用户选择:
    • 搜索 可见的 第一个间隙(例如[0,1,3,7]-> 2;根据SO-link的 O(log n))
    • 搜索> =差距值(O(log n))的第一个用户
    • 如果用户<next_gap_neighbor(在上面的示例中:3;在选择间隙2之后的下一个值)
    • ->选择
    • 其他
    • -> 暂时 添加选择间隙值(此刻;模型决定 在线 更新的频率)以 查看 或以某种方式将搜索限制为>选择间隙值(O(log n))

根据数据,这应该工作非常好,如果数据是巨大的, 看到的 是稀疏的!

2020-06-20