5

我正在努力寻找在我的朋友网络中最受欢迎的点赞。“在我的朋友网络中最受欢迎”被定义为“被我的朋友点赞最多的人”。

假设每个朋友都有一个唯一的 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 个喜欢，那么内存使用量会很大。当然，我应该使用朋友 id 和点赞 id 来进行所有计算，而不是存储整个对象，这会大大减少内存使用量。

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

4

3 回答 3

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)

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

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

于 2012-09-17T14:06:36.503 回答
0

既然您对寻找“最受欢迎的赞”感兴趣，这是否意味着您只对“前几名”感兴趣，例如前 5 名、前 10 名等？如果是这样，一种可能的方法是重新排序事物，以便您迭代每个喜欢，计算 N，与该喜欢相关联的朋友的数量，然后仅在该喜欢进入运行时对其进行进一步处理顶部 X' 列表。棘手的部分是使用这样的循环结构有效地计算 N（天真的实现将遍历每个朋友。喜欢每个朋友，每个喜欢..yuck..），但好处是如果 N 足够小，你可以放弃所有与此相关的数据都来自内存，并且不会对其进行任何进一步处理。也就是说，如果您有一个“前 10 名列表”，并且您已经在该列表中添加了 10 个喜欢，而当前点赞的 N 小于“top 10 list”中最小的 N，你知道点赞是无关紧要的。基本上，你做一个交易，你做一些冗余循环以换取显着减少的内存占用。这些循环也可以合理地并行化，所以额外的循环可能不是那么糟糕。很难说如果不尝试它是否对您的特定用例更有效，但如果“前 10 名”风格的输出满足您的要求，则可能值得朝这个方向探索。

于 2012-10-11T23:50:39.817 回答
0

我不明白你为什么使用priority_queue. 当然，它在容器更改时有效地跟踪最大元素。但是你只需要单次操作，在第一步之后。总之：

priority_queue< pair<like, int> > pq;
std::priority_queue< pair<like, int> >::const_iterator max_friends = pq.begin()
for(i = like2friendsMap.begin() to .end())  {
  if (max_friends->size() < i->size()) max_friends = i;
}

当然，这只适用于 N=1，但这对于“你的朋友 X、Y 和 Z 喜欢这样”的首选来说已经足够了。

于 2012-09-17T12:45:59.067 回答