因此,这个问题使我们的用户与其他在线用户匹配。但是,这不仅仅是一对一的比赛。给一个用户5个其他用户的选择,然后将其标记为可见,并且当该用户请求再显示5个用户时,不应再显示。在此过程中,更多的人可以上网。
问题是,我希望使用Redis在每个用户的选择中显示其他用户的方法,但是算法主要是我正在寻找的。我正在尝试以最快的方式实现这一点,如果可能的话,使用redis,但是如果需要的话,我也可以调用数据库。
我当前的解决方案如下,希望有人能从O(N)调用中获得一些改进的技巧。
因此,每个用户都需要有一个 看到 一套user_id秒。我们可以有个redis列表(队列)onlineusers。在此位置,我们从左向右弹出用户,直到找到不在用户 可见 集中的用户,将其保存,添加到已看到的用户中,然后将其向右推。然后,一旦获得其中的5个,我们就向后推回我们已经看到的剩下的弹出窗口。
user_id
onlineusers
这是我能想到的最好的方法,但是每次我们要为该用户选择5个用户时,它都是O(N)。用户有可能(尽管不太可能)看到了巨大的数量,并跳出了整个列表。
为了更好地理解这一点。幼稚的方法是让每个用户以集合的形式包含所有在线用户的副本。因此,我们简单地弹出5个随机集合成员。但这是行不通的,因为空间不足,每次用户上线时,都必须将其添加到每个用户的在线用户中。或当它们脱机并且那些操作为O(N)时被删除,考虑到它们已针对O(1)的N个用户完成
有没有人有将用户与其他用户匹配的提示?
了解我们正在谈论的是哪种数据将是很好的。存在多少个用户?平均有多少人会在线?“可见用户”与所有用户的比例(稀疏与密集)相比如何?
修改算法 不要先弹出 算法 ,而是从在线用户集中选择随机元素。这将改善平衡,并可能有助于分摊复杂度,具体取决于这两套比率!
替代算法(结构更清晰;最坏的情况仍然很糟糕;如果稀疏 出现 ,应该会很好)
根据数据,这应该工作非常好,如果数据是巨大的, 看到的 是稀疏的!