为Facebook或Linkedln等大型社交网络设计数据结构-yiteyi-C++库

你会如何为Facebook或Linkedln这样的大型社交网络设计数据结构？描述你将如何设计一个算法来显示两个人之间的最短路径（例如，Me->Bob->Susan->Jason->you）。 问：谷歌采访

null

解决这个问题的一个好方法是移除一些约束，并首先解决这种情况。 案例1：简化问题（不考虑数百万人） 我们可以通过将每个人视为一个节点，并让两个节点之间的边表示两个用户是朋友来构造一个图。如果我们想找到两个人之间的道路，我们从一个人开始，做一个简单的步骤广度优先搜索 .或者，我们可以进行双向广度优先搜索。这意味着要进行两次广度优先搜索，一次来自源，一次来自目标。当搜索发生冲突时，我们知道我们找到了一条路径。为什么深度优先搜索不奏效？首先是深度优先搜索只会找到一条路。它不一定能找到最短的路径。第二，即使我们只需要任何路径，它也会非常低效。两个用户之间可能只有一个分离度，但它可以在找到这种相对直接的连接之前，在他们的“子树”中搜索数百万个节点。在实现中，我们将使用两个类来帮助我们。BFSData保存广度优先搜索所需的数据，例如isVisited哈希表和toVisit队列。PathNode表示我们正在搜索的路径，存储每个人和我们在此路径中访问的前一个节点。 Java中的主要逻辑如下所示

JAVA

                         Linkedlist<Person> findPathBiBFS(HashMap<Integer, Person> people,                       
                                                 int                                     source,                                     int                                     destination)                       
                         {                       
                                                 BFSData sourceData =                                     new                                     BFSData(people.get(source));                       
                                                 BFSData destData =                                     new                                     BFSData(people.get(destination));                       
           
                                                 while                                     (!sourceData.isFinished() && !destData.isFinished())                       
                                                 {                       
           
                                                 /* Search out from source. */                       
                                                 Person collision = searchlevel(people, sourceData, destData);                       
                                                 if                                     (collision !=                                     null                                     )                       
                                                 return                                     mergePaths(sourceData, destData, collision.getID());                       
           
                                                 /* Search out from destination. */                       
                                                 collision = searchlevel(people, destData, sourceData);                       
                                                 if                                     (collision !=                                     null                                     )                       
                                                 return                                     mergePaths(sourceData, destData, collision.getID());                       
                                                 }                       
           
                                                 return                                     null                                     ;                       
                         }                       
           
           
                         /* Search one level and return collision, if any.*/                       
                         Person searchLevel(HashMap<Integer, Person> people,                       
                                                 BFSData primary, BFSData secondary)                       
                         {                       
           
                                                 /* We only want to search one level at a time. Count                       
                                                 how many nodes are currently                       
                                                 in the primary's level and only do that many nodes.                       
                                                 We continue to add nodes to the end. */                       
           
                                                 int                                     count = primary.toVisit.size();                       
                                                 for                                     (                                     int                                     i=                                     0                                     ; i < count; i++)                       
                                                 {                       
                                                 /* Pull out first node. */                       
                                                 PathNode pathNode = primary.toVisit.poll();                       
                                                 int                                     personid = pathNode.getPerson().getID();                       
           
                                                 /* Check if it's already been visited. */                       
                                                 if                                     (secondary.visited.containsKey(personid))                       
                                                 return                                     pathNode.getPerson();                       
           
                                                 /* Add friends to queue. */                       
                                                 Person person = pathNode. getPerson();                       
                                                 Arraylist<Integer> friends = person.getFriends();                       
                                                 for                                     (                                     int                                     friendid : friends)                       
                                                 {                       
                                                 if                                     (!primary.visited.containsKey(friendid))                       
                                                 {                       
                                                 Person friend= people.get(friendld);                       
                                                 PathNode next =                                     new                                     PathNode(friend, pathNode);                       
                                                 primary.visited.put(friendld, next);                       
                                                 primary.toVisit.add(next);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 return                                     null                                     ;                       
                         }                       
           
           
                         /* Merge paths where searches met at the connection. */                       
                         Linkedlist<Person> mergePaths(BFSData bfsl, BFSData bfs2,                       
                                                 int                                     connection)                       
                         {                       
                                                 // endl -> source, end2 -> dest                       
                                                 PathNode endl = bfsl.visited.get(connection);                       
                                                 PathNode end2 = bfs2.visited.get(connection);                       
           
                                                 Linkedlist<Person> pathOne = endl.collapse(                                     false                                     );                       
                                                 Linkedlist<Person> pathTwo = end2.collapse(                                     true                                     );                       
           
                                                 pathTwo.removeFirst();                                     // remove connection                       
                                                 pathOne.addAll(pathTwo);                                     // add second path                       
           
                                                 return                                     pathOne;                       
                         }                       
           
                         class                                     PathNode                       
                         {                       
                                                 private                                     Person person =                                     null                                     ;                       
                                                 private                                     PathNode previousNode =                                     null                                     ;                       
                                                 public                                     PathNode(Person p, PathNode previous)                       
                                                 {                       
                                                 person = p;                       
                                                 previousNode = previous;                       
                                                 }                       
           
                                                 public                                     Person getPerson()                       
                                                 {                       
                                                 return                                     person;                       
                                                 }                       
           
                                                 public                                     Linkedlist<Person> collapse(                                     boolean                                     startsWithRoot)                       
                                                 {                       
                                                 Linkedlist<Person> path=                                     new                                     Linkedlist<Person>();                       
                                                 PathNode node =                                     this                                     ;                       
                                                 while                                     (node !=                                     null                                     )                       
                                                 {                       
                                                 if                                     (startsWithRoot)                       
                                                 path.addlast(node.person);                       
                                                 else                       
                                                 path.addFirst(node.person);                       
                                                 node = node.previousNode;                       
                                                 }                       
           
                                                 return                                     path;                       
                                                 }                       
                         }                       
           
                         class                                     BFSData                       
                         {                       
                                                 public                                     Queue<PathNode> toVisit =                                     new                                     Linkedlist<PathNode>();                       
                                                 public                                     HashMap<Integer, PathNode> visited =                       
                                                 new                                     HashMap<Integer, PathNode>();                       
           
                                                 public                                     BFSData(Person root)                       
                                                 {                       
                                                 PathNode sourcePath =                                     new                                     PathNode(root,                                     null                                     );                       
                                                 toVisit.add(sourcePath);                       
                                                 visited.put(root.getID(), sourcePath);                       
                                                 }                       
                                                 public                                     boolean                                     isFinished()                       
                                                 {                       
                                                 return                                     toVisit.isEmpty();                       
                                                 }                       
                         }                       

以上基于BFS的解决方案有多快？ 假设每个人都有k个朋友，源S和目的地D有一个共同的朋友C。 1.从S到D的传统广度优先搜索：我们大致搜索k+k*k节点：每个S的k个朋友，然后是他们的k个朋友。 2.双向广度优先搜索：我们通过2k个节点：每个S的k个朋友和每个D的k个朋友。当然，2k远小于k+k*k。 3.将其推广到长度为q的路径，我们有： 3.1 BFS:O（k） ^Q ) 3.2双向BFS:0（k ^q/2 +k ^q/2 )，也就是0（k） ^q/2 ) 如果我们想象一条像a->B->C->D->E这样的路径，每个人都有100个朋友，这是一个很大的区别。BFS将需要1亿（100 ^4. )节点。双向BFS只需要查看20000个节点（2 x 100 ^2. ). 案例2：处理数百万用户 对于这么多用户，我们不可能将所有数据保存在一台机器上。这意味着我们上面简单的个人数据结构不起作用，我们的朋友可能不会像我们一样生活在同一台机器上。相反，我们可以将朋友列表替换为他们的ID列表，并按如下方式遍历： 1：对于每个好友ID:int machine index=getMachineIDForUser（person_ID）； 2：进入机器#机器#索引 3：在那台机器上，do:Person friend=getPersonWithID（Person_ID）；下面的代码概述了这个过程。我们定义了一个类服务器，它包含所有机器的列表，以及一个类机器，它代表一台机器。这两个类都有哈希表来高效地查找数据。 Java中的主要逻辑如下->

JAVA

                         // A server that holds list of all machines                       
                         class                                     Server                       
                         {                       
                                                 HashMap<Integer, Machine> machines =                       
                                                 new                                     HashMap<Integer, Machine>();                       
                                                 HashMap<Integer, Integer> personToMachineMap =                       
                                                 new                                     HashMap<Integer, Integer>();                       
           
                                                 public                                     Machine getMachineWithid(                                     int                                     machineID)                       
                                                 {                       
                                                 return                                     machines.get(machineID);                       
                                                 }                       
           
                                                 public                                     int                                     getMachineIDForUser(                                     int                                     personID)                       
                                                 {                       
                                                 Integer machineID = personToMachineMap.get(personID);                       
                                                 return                                     machineID ==                                     null                                     ? -                                     1                                     : machineID;                       
                                                 }                       
           
                                                 public                                     Person getPersonWithID(                                     int                                     personID)                       
                                                 {                       
                                                 Integer machineID = personToMachineMap.get(personID);                       
                                                 if                                     (machineID ==                                     null                                     )                                     return                                     null                                     ;                       
           
                                                 Machine machine = getMachineWithid(machineID);                       
                                                 if                                     (machine ==                                     null                                     )                                     return                                     null                                     ;                       
           
                                                 return                                     machine.getPersonWithID(personID);                       
                                                 }                       
                         }                       
           
                         // A person on social network has id, friends and other info                       
                         class                                     Person                       
                         {                       
                                                 private                                     Arraylist<Integer> friends =                       
                                                 new                                     Arraylist<Integer>();                       
                                                 private                                     int                                     personID;                       
                                                 private                                     String info;                       
           
                                                 public                                     Person(                                     int                                     id)                       
                                                 {                       
                                                 this                                     .personID =id;                       
                                                 }                       
                                                 public                                     String getinfo()                       
                                                 {                       
                                                 return                                     info;                       
                                                 }                       
                                                 public                                     void                                     setinfo(String info)                       
                                                 {                       
                                                 this                                     .info = info;                       
                                                 }                       
                                                 public                                     Arraylist<Integer> getFriends()                       
                                                 {                       
                                                 return                                     friends;                       
                                                 }                       
                                                 public                                     int                                     getID()                       
                                                 {                       
                                                 return                                     personID;                       
                                                 }                       
                                                 public                                     void                                     addFriend(                                     int                                     id)                       
                                                 {                       
                                                 friends.add(id);                       
                                                 }                       
                         }                       

下面是一些优化和后续问题。 优化：减少机器跳跃 从一台机器跳到另一台机器很昂贵。不要和每个朋友随机地从一台机器跳到另一台机器，而是尝试批量进行这种跳操作——例如，如果我的五个朋友住在一台机器上，我应该一次查找所有这些跳操作。 优化：人与机器的智能划分 人们更可能与生活在同一个国家的人成为朋友。不要在机器上随机划分人员，而是尝试按国家、城市、州等进行划分。这将减少跳跃的次数。 问题：广度优先搜索通常需要将节点“标记”为已访问。在这种情况下你是怎么做到的？ 通常，在BFS中，我们通过在节点类中设置已访问标志来将节点标记为已访问。在这里，我们不想这样做。可能会有多个搜索同时进行，所以只编辑我们的数据是个坏主意。相反，我们可以用哈希表模拟节点的标记，以查找节点id并确定它是否已被访问。 其他跟进问题： 1.在现实世界中，服务器出现故障。这对你有什么影响？ 2.如何利用缓存？ 3.你会一直搜索到图的末尾（无限）？你如何决定何时放弃？ 4.在现实生活中，有些人的朋友比其他人多，因此更有可能在你和其他人之间找到一条路。如何使用这些数据来选择开始遍历的位置？本文的参考资料本文的参考资料本文由 Somesh Awasthi先生 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章