假设你有一个拥有十亿用户的社交网络。在每个用户的页面上,您想显示该用户的朋友、朋友的朋友等等,一直到五度关系的数量。友谊是相互的。这些计数不需要立即更新,但它们应该是精确的。
我研究了图形,但没有找到任何建议可扩展解决此问题的方法。我所能想到的任何方法都需要太多的时间、太多的空间或两者兼而有之。这让我感到非常痛苦!
我研究了图形,但没有找到任何建议可扩展解决此问题的方法。我所能想到的任何方法都需要太多的时间、太多的空间或两者兼而有之。这让我感到非常痛苦!
O(n^3)
的?即使是一个朴素的 BFS 最多也不应该需要超过 O(E) = O(n^2)
。将其与 Strassen 的 O(n^2.8)
和 Coppersmith-Winograd 的 O(n^2.38)
进行比较。 - collapsar我认为问题实际上归结为如何对10亿用户进行哈希/跟踪,因为我们需要计算每一层的好友数量。(请注意,我们只需要计数,不需要存储)
如果我们假设对于每个人,他们的朋友以及他们的朋友的朋友都非常少(比如小于1000和小于100,000),那么在数据库表中存储这些信息似乎是可行的。整个数据库只需要两次可管理的遍历,然后在创建“新”关系时直接添加到表中。
如果我们在用户表中存储了第一和第二度朋友,我们可以利用它们扩展到需要的范围-
例如:要计算第三度朋友,我们需要哈希和跟踪所有二度朋友的一度朋友。(对于第四度,你要做所有二度的二度朋友,对于更高的程度,你需要创建第四度,然后适当地扩展到第五或第六度)。
因此,在那一点上(第五和第六度的朋友),您开始接近需要跟踪、哈希和计数的10亿人数。
我在考虑问题的本质是,当你“计算”更高层次关系中的朋友时,如何以最有效的方式拥有10亿条记录ID。
O(n)
。更好的是,当我们从当前节点访问一个未访问的节点并且degreeOfSeparation == 5
时,我们可以停止(与 Jason L 建议的相同,只是我不明白他如何跟踪分离度)。我没有任何确切的数字,但我想象中长度小于等于 5 的路径子图不会超过几百万个。在几百万个节点上进行 BFS 是非常快的...不是吗?我更加困惑的是为什么矩阵方法会更快。 - rliu