问面试stumper:朋友的朋友的朋友

EN

一种有趣的方法是将朋友图转换为邻接矩阵，然后将矩阵提升到5次方。这为您提供了一个邻接矩阵，其中包含每个节点之间长度为5的路径数的计数。

请注意，您需要一个可以利用稀疏矩阵的矩阵乘法算法，因为朋友邻接矩阵在前两个级别可能是稀疏的。幸运的是，人们已经在如何高效地乘以大型矩阵(特别是稀疏矩阵)方面做了大量的工作。

这是一个video where Twitter's Oscar Boykin mentions this approach，用于计算推特上的追随者。

在我看来，问题真正归结为我们如何散列/跟踪10亿用户，因为我们在计算每个级别的朋友。(请注意，我们只需要对它们进行计数，而不是存储它们)

如果我们假设对于每个人，他们的朋友和朋友的朋友是非常小的顺序(比如<1000和<100,000)，那么将这些存储在每个用户的数据库表中似乎是可行的。它只需要对整个数据库进行两次可管理的遍历，然后在创建“新”关系时直接添加到表中。

例句:为了计算三度好友，我们需要对所有二度好友的一度好友进行散列和跟踪。(对于第四度，你做所有的第二秒，对于更高的度，你创建第四次，然后适当地扩展到第五次或第六次)。

因此，在这一点上(5度和6度好友)，你开始接近10亿，因为你需要跟踪，哈希和计数的人数。

我在想，问题就变成了，当你“计算”高阶关系中的朋友时，什么是拥有10亿个记录ID的最有效的方法。

你怎么做到的，我不知道-有什么想法吗？