在我的朋友圈中查找最受欢迎的点赞

Question

我正在研究一种方法来查找我朋友网络中最受欢迎的点赞。 "在我的朋友网络中最受欢迎"的定义是“被我的朋友们点赞最多”。

假设每个朋友都有一个唯一的ID和许多喜欢的页面。 因此，给定这样的朋友数组，我想找到最受多数朋友喜欢的内容，并且还要找出喜欢这个东西的朋友。 本质上，我想展示像“您的朋友X、Y和Z喜欢这个”的东西。

我的第一个解决方案是使用Map（用于存储反向映射：喜欢->集合）和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内部使用红黑树来实现map，使用优先队列的最小/最大堆，这种方法对我来说似乎非常快。但是如果我有数百个朋友，每个人都有数百个喜欢，那么内存使用量将会很大。当然，我应该只为所有计算使用朋友ID和喜欢ID，而不是存储整个对象，这将大大减少内存使用。

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

- Sourav

---

即使有一千个朋友，每个人都有一千个赞，总赞数也只有一百万。如今计算机可以处理数十亿的对象。 - MSalters

话虽如此，这通常是我会在SQL中完成的事情。数据库可以处理数十亿行数据，而这种分组是SQL的强项。 - MSalters

@MSalters，问题在于它可以并行运行约100个线程，因此减少内存占用是一个显著的好处。 - Sourav

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)

我认为重新迭代比存储朋友更好。

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

- Shashwat

---

虽然这解决了查找最受欢迎页面的问题，但我必须再次扫描所有朋友以找出哪些朋友喜欢它们。 - Sourav

Answer 2

我不明白为什么你要使用一个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喜欢这个”首选足够了。

- MSalters

---

我想找出N个最受欢迎的喜欢，所以我选择了优先队列。 - Sourav

Answer 3

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

- WeirdlyCheezy