对于超大型的社交网站,展示两个人之间的“连接关系”或“社交路径”
对于超大型的社交网站,展示两个人之间的“连接关系”或“社交路径”
一贱书生 发表于1年前
对于超大型的社交网站,展示两个人之间的“连接关系”或“社交路径”
  • 发表于 1年前
  • 阅读 1
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

/**
 * 功能:

[java] view plain copy

 

  1. /** 
  2.  * 思路: 
  3.  * 1)针对每个朋友ID,找出所在机器的位置:int machine_index=getMachineIDForUser(personID); 
  4.  * 2)转到编号为#machine_index的机器。 
  5.  * 3)在那台机器上,执行:Person friend=getPersonWithID(person_id)。 
  6.  *  
  7.  * 定义一个Server类,包含一份所有机器的列表,还有一个Machine类,代表一台单独的机器。通过散列表,有效地查找数据。 
  8.  * 
  9.  */  
  10.   
  11. class Server{  
  12.     HashMap<Integer,Machine> machines=new HashMap<Integer, Machine>();  
  13.     HashMap<Integer,Integer> personToMachineMap=new HashMap<Integer, Integer>();  
  14.       
  15.     public Machine getMachineWithId(int machineID){  
  16.         return machines.get(machineID);  
  17.     }  
  18.       
  19.     public int getMachineIDForUser(int personID){  
  20.         return personToMachineMap.get(personID);  
  21.     }  
  22.       
  23.     public Person getPersonWithId(int personID){  
  24.         Integer machineID=getMachineIDForUser(personID);  
  25.         if(machineID==null)  
  26.             return null;  
  27.         Machine machine=getMachineWithId(machineID);  
  28.         if(machine==null)  
  29.             return null;  
  30.         return machine.getPersonWithId(personID);  
  31.     }  
  32.       
  33. }  
  34.   
  35. class Machine{  
  36.     public int machineID;  
  37.     public HashMap<Integer,Person> persons=new HashMap<Integer, Person>();  
  38.       
  39.     public Person getPersonWithId(int personID){  
  40.         return persons.get(personID);  
  41.     }  
  42.       
  43. }  
  44.   
  45. class Person{  
  46.     private int personID;  
  47.     private ArrayList<Integer> friendID;  
  48.       
  49.     public Person(int id){  
  50.         this.personID=id;  
  51.     }  
  52.       
  53.     public int getID(){  
  54.         return this.personID;  
  55.     }  
  56.       
  57.     public void addFriend(int id){  
  58.         this.friendID.add(id);  
  59.     }     
  60.       
  61. }  
  62.   
  63. /** 
  64.  * 优化:减少机器间跳转次数 
  65.  *      从一台机器跳转到另外一台机器的开销很昂贵,不要为了找到某个朋友就在机器之间任意跳转,而是试着批处理这些跳转动作。 
  66.  * 优化:智能划分用户和机器 
  67.  *      根据地域划分 
  68.  *  
  69.  * 问题:广度优先搜索要求标记访问过的节点,如何处理 
  70.  *      同一时间可能会执行很多搜索操作,因此直接编辑数据的做法并不妥当。可以利用散列表模仿节点的标记动作,以查询节点id,是否被访问过。 
  71.  */ 
共有 人打赏支持
粉丝 15
博文 722
码字总数 600072
×
一贱书生
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: