在我的朋友网络中找到最受欢迎的喜欢

Question

我正在寻找一种在朋友网络中找到最受欢迎的喜欢的方法."在我的朋友网络中最受欢迎"被定义为"拥有我朋友最多的喜欢".

假设每个朋友都有一个唯一的ID,并且有许多喜欢的页面.因此,鉴于这样的朋友一个数组,我想找到它是由众多的朋友喜欢的喜欢,并且还谁喜欢这个东西的朋友们.从本质上讲,我想展示"你的朋友X,Y&Z喜欢这个".

我的第一个解决方案是使用Map(用于存储反向映射:like-> set)和Priority Queue(用于查找前N个).这是我的算法(使用C++ STL):

map< like, set<friend> > like2friendsMap;
for each friend {
  for each like {
    like2friendsMap[like].insert(friend); //populate the map
  }
}

priority_queue< pair<like, int> > pq;
for each like in like2friendsMap {
  int count = like2friendsMap[like].size(); //no. of friends who like this or "popularity"
  pq.push(like, count); //count is the priority
}

map< like, set<friend> > result
for i in 1 to N { //N is how many popular items I want
   result = pq.top();  //gives me the element with highest priority (most popular like)
   pq.pop();
}

由于STL内部使用红黑树实现优先级队列的映射和最小/最大堆,这种方法对我来说似乎相当快.但如果我有100个朋友,每个人都有100个喜欢,那么内存使用量就会很大.当然,我不应该存储整个对象,而是应该使用friend id和id作为所有计算,这会大大减少内存使用量.

还可以使用哪种其他算法或数据结构来提高效率(提高速度,减少内存)？出于某种原因,我无法存储每个朋友的列表,它必须在运行时计算.我正在使用C++开发它,因此使用STL或boost的解决方案会更好.

Answer 1

create an integer list allPages which can be referenced by page
initialize it with 0
for every friend f
{
    for every page p liked by f
    {
        allPages[p]++;
    }
}
get the maximum of the allPages[p]

如果P是页数，那么它的空间复杂度为O(P)。

如果F是朋友的数量，L是每个人喜欢的平均页面。那么它的时间复杂度就是O(F*L)。因此，即使您再次遍历所有朋友以检查谁都喜欢该页面，也不会增加太多复杂性。

O(F*L) + O(F) would remain O(F*L)

我认为最好再次迭代而不是存储朋友。

或者您可以存储页面的反向引用本身。即对于每个页面，存储喜欢的朋友列表。这不会占用太多空间，并且可以以最低的复杂性完成您的工作。