algorithm - 用户匹配算法

Question

所以这个问题我们有用户匹配到其他在线用户。然而，这不仅仅是一对一的比赛。为用户提供 5 个其他用户的选择，然后将其标记为已看到，并且当用户请求显示另外 5 个用户时不应再次显示。在此过程中可以有更多人上网。

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

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

因此每个用户都需要有一组已看到的user_id。我们可以有一个 onlineusers 的 redis 列表(队列)。我们一直从左侧弹出用户，直到我们找到一个不在用户的已见集中的用户，保存它，添加到已见用户，然后将其推到右侧。然后，一旦我们得到其中的 5 个，我们就将剩下的那些推回已经看到的那些。

这是我能想到的最好的，但是每次我们要为这个用户找到 5 个用户以供选择时，它是 O(N)。有可能(尽管不太可能)用户已经看到了大量内容并且正在从整个列表中弹出。

为了帮助更好地理解这一点。一种天真的方法是让每个用户都以集合的形式包含所有在线用户的副本。那么我们就简单地弹出 5 个随机集合成员。但这行不通，因为没有足够的空间，每次用户上线都必须将他们添加到每个用户的在线用户中。或者在他们离线时删除，考虑到他们是为 N 个用户在 O(1) 时完成的，这些操作是 O(N)

有没有人有任何提示可以将用户与其他用户匹配？

Answer 1

最好了解我们正在谈论的是哪种数据。有多少用户？平均有多少人在线？ “见过的用户”与所有用户的比例(稀疏与密集)如何？

修改您的算法不要弹出第一个，而是从在线用户集中选择一个随机元素。这应该会改善平衡，并可能有助于根据这两组的比率分摊复杂性!

替代算法(更结构化；最坏情况下仍然很糟糕；如果稀疏看到，应该不错)

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

根据数据，如果数据很大且seen 稀疏，这应该非常有效!