Поиск самых популярных лайков в сети моего друга
Я работаю над тем, чтобы найти самые популярные лайки в сети моих друзей. «Самая популярная в сети моих друзей» определяется как «наибольшее количество лайков от моих друзей».
Предположим, что у каждого друга есть уникальный идентификатор и количество понравившихся страниц. Итак, учитывая множество таких друзей, я хочу найти лайки, которые нравятся большинству друзей, и также друзья, которым понравилась эта вещь. По сути, я хочу показать что-то вроде «Твой друг X, Y & Z любит это. «
Мое первое решение состоит в том, чтобы использовать карту (для хранения обратного отображения: like-> set) и приоритетную очередь (для поиска верхней 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 внутренне использует Red Black Tree для реализации карты и мин / макс кучи для приоритетной очереди, этот подход мне кажется довольно быстрым. Но если бы у меня были сотни друзей, а у каждого — сотни лайков, использование памяти было бы огромным. Конечно, вместо того, чтобы хранить целые объекты, я должен использовать идентификатор друга и идентификатор для всех вычислений, что значительно уменьшит использование памяти.
Какой другой алгоритм или структуру данных можно использовать для повышения эффективности (увеличения скорости, уменьшения памяти)? По какой-то причине я не могу сохранить список друзей для каждого лайка, он должен быть вычислен во время выполнения. Я разрабатываю это с использованием C ++, поэтому решения с использованием STL или boost будут еще лучше.
Решение
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)
Я думаю, что лучше повторить снова, чем хранить друзей.
Или вы можете сохранить саму обратную ссылку для страницы. То есть для каждой страницы хранится список друзей, которые понравились. Это не займет много места и сделает вашу работу минимальной сложности.
Другие решения
Я не понимаю, почему вы используете 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, как этот», выбирали сверху.
Поскольку вы заинтересованы в поиске «самых популярных лайков», означает ли это, что вы интересуетесь только «топ-несколькими», например, топ-5, топ-10 и т. Д.? Если это так, то одним из возможных подходов было бы изменить порядок вещей так, чтобы вы итерировали для каждого лайка, вычислили N, количество друзей, связанных с этим лайком, и затем выполняли дальнейшую обработку этого лайка только в том случае, если он превращается в запуск. ‘ топ X ‘список. Сложная часть заключается в эффективном вычислении N с такой циклической структурой (наивная реализация будет зацикливаться на каждом друге. Как для каждого друга, как на … спасибо …), но преимущество будет в том, что если N достаточно мало, вы можете отказаться все данные, связанные с этим, как из памяти и не делать никакой дальнейшей обработки на нем. То есть, если у вас есть «список 10 лучших», и вы уже добавили 10 лайков в этот список, а N текущего лайка меньше, чем наименьшее N в «списке 10 лучших», вы знаете, что лайк не имеет значения , По сути, вы совершаете сделку, в которой вы делаете несколько избыточных циклов в обмен на резко сокращенный объем памяти. Эти циклы также могут быть разумно распараллелены, так что, возможно, дополнительный цикл не так уж и плох. Трудно сказать, является ли он более эффективным для вашего конкретного случая использования, не пробуя его, но, возможно, стоит изучить его в этом направлении, если вывод в стиле «топ-10» отвечает вашим требованиям.