假设每个朋友都有一个唯一的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的解决方案将更好。