logo标签列表

用户匹配算法

algorithmredis
4
所以这个问题是我们让用户与其他在线用户匹配。然而它不仅仅是一对一的匹配。一个用户会选择5个其他用户，然后标记为已查看并在用户请求展示另外5个用户时不再显示。在此过程中可能会有更多的人上线。
问题是，我希望每个用户都能在其他用户的选择中显示，使用Redis但主要是要一个算法。我正在尝试以最快的方式实现这个，如果可能的话，使用Redis，但如果需要，我也可以调用数据库。
我的当前解决方案如下，希望有人能提供一些从O（N）调用中改进的提示。
所以每个用户都需要一个seen集合的user_ids。我们可以有一个Redis列表（队列）onlineusers，从左侧保持弹出用户，直到我们找到一个不在用户seen集合中的用户，保存它，添加到用户已看到的列表中，然后将其推到右侧。然后，一旦我们得到了其中的5个，我们就把那些已经看到的左边弹出的推回去。
这是我能想到的最好的方法，但每次我们想要找到5个用户供该用户选择时，它的时间复杂度都是O（N）。这可能（虽然不太可能）会导致用户已经看到了大量内容，并弹出了整个列表。
为了更好地理解这一点。一个天真的做法是让每个用户都包含在线用户集合的副本。然后我们只需随机弹出5个集合成员即可。但这行不通，因为空间不够，每次用户上线时，他们必须被添加到每个用户的在线用户列表中。或者在他们离线时删除，这些操作对于N个用户而言是O(N)。
有人有什么技巧可以将用户与其他用户匹配吗？
A. 如果经常浏览大量用户，则每次获取20个用户可能比5个更好（这可能会减少开销）。 B. 听起来你需要（最坏的情况下）检查所有在线用户列表，因此在任何情况下都将是O(n)。 C. 为了加快速度，您可以在查看当前5个用户时获取下一个5个用户。这在某些情况下可能是浪费的，但会提供更好的用户体验。 - shapiro yaacov
@shapiro.yaacov 我希望每次获取5个用户时，它不会是O(N)。我正在设计一种方式，使用按用户ID排序的所有用户ID的排序集合，其中每个用户保留其所在位置的索引。因此，在每次调用时，他们只需从那里恢复到一个新的人，直到他们循环回到起点。这将是一个初始的O(log N)，以在该索引处恢复。我放弃了这个想法，因为我想不出如何均匀分布它。我想让每个用户从一个随机索引开始，但我担心集合总是在结尾或中间过度访问。 - user5163183
@shapiro.yaacov 目前我会选择这个带有优化的选项，看看是否可以让它正常工作，直到我想到更好的方法为止，谢谢。 - user5163183
1个回答
1

希望了解我们所讨论的数据类型。有多少用户存在？平均有多少用户在线？“已见用户”与所有用户相比的比例如何（稀疏 vs. 密集）？

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

备选算法（更结构化；最坏情况仍然不好；如果稀疏已见，应该很好）

  • 将seen保持为平衡树（O(log n)插入）
  • 将online保持为平衡树。
  • 当选择的用户不足时：
    • 在seen中查找第一个间隙（例如[0,1,3,7] -> 2; 根据 SO-link，O(log n)）
    • 查找第一个用户>=间隙值（O(log n)）
    • 如果用户<下一个间隙邻居（在上面的示例中：3；选择间隙2后的下一个值）
    • ->选择
    • 否则
    • ->将所选间隙值暂时（此刻；模型决定多久更新online）添加到seen中，或以某种方式限制搜索到>所选间隙值（O(log n)）

根据数据，如果seen稀疏，这应该能很好地工作！

谢谢你的回答。平均每次会有5,000个用户在线，但如果数量增加到50,000甚至100,000，我真的希望能够处理扩展。在平均情况下，5,000个用户中的一个用户平均会看到200个数据，最多约为500个。因此，数据量很大，而且观察到的数据很少，我一定会仔细研究你写的要点。 - user5163183
我之所以问这个问题，是因为搜索树会增加一些开销，需要大量的数据才能使其值得。一个著名的例子是Fibonacci堆。稀疏性是分析随机算法的重要因素。在你的情况下，我认为没有什么比随机算法更简单和实用（只需选择一个随机用户；检查是否可行；继续）（会有更快的方法，但更难实现；例如，结合布隆过滤器）。 - sascha
如果我从onlineusers集合中弹出一个随机用户，那很好，因为在redis中这是一个O(1)操作。然而，与列表的情况不同，在列表中它会遍历每个用户并重复，我不确定每个用户是否会获得均匀的用户选择分布。每个用户都将有自己独立的“seen”集合，因此当我弹出随机用户时，比如说20个，然后删除用户已经看过的用户，我不知道在这些剩下的用户中，有些可能被多次选中，而有些则从未被选中。对于这里的分布有什么想法，或者使用随机是否值得冒险？ - user5163183
我不明白问题所在。每个用户都有他的“已看”数据。每个用户挑选的5个新用户是均匀分布的。如果所有用户一直在线->每个用户“已看”数据中挑选的用户将完全均匀分布。当然，这可能会改变，取决于“在线/离线”的动态性，但这种随机化方法总是比“先选”（和大多数静态策略）更好。问题：你想要什么？如果用户第一次查询（同时查询），你的旧方法将为每个用户选择相同的5个用户。 - sascha
我的旧方法会为第一个查询的用户选择5个，这些元素从Redis列表（队列）的左侧弹出并推到右侧。因此第二个用户不会再次选择它们。我的随机问题是，假设在线用户集合中有用户ID从“1”到“200”。也许用户“1”从未被选择，因为它是随机的，而用户“55”被选择了很多次。我想说的是，如果我按顺序重复迭代列表，第一次每个用户都会被选择一次。然后我不确定之后它有多均匀，但我猜它应该相当均匀。只是想知道关于随机性的问题。 - user5163183
“随机”方法实际上很好，因为它可以很好地适应“seen”稀疏和数据庞大的情况。我只是希望如果所有元素都被看到，不要重复调用太多次来查找随机元素。但在几乎所有实际情况下，这不应该成为问题。我想，如果一个用户从未被其他用户选择，那对我来说并不重要，因为他们正在选择自己，这是一个不相关的问题，提醒他们关注某个用户并给予他们更高的优先级。 - user5163183
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接