5

私は友達のネットワークで最も人気のあるいいねを見つける方法に取り組んでいます。「友達ネットワークで最も人気がある」とは、「友達のいいねが一番多い」と定義されています。

各友達が一意のIDを持ち、いいねされたページがいくつかあるとします。ですから、そのような友達がたくさんいるので、一番好きな友達、そしてこれが好きな友達を見つけたいと思います。基本的には、「友達の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は内部的に赤黒木を使用して優先キューのマップと最小/最大ヒープを実装しているため、このアプローチは私にはかなり速いように思われます。しかし、私に数百人の友達がいて、それぞれに数百人のいいねがあるとしたら、メモリ使用量は膨大になります。もちろん、オブジェクト全体を保存する代わりに、すべての計算にフレンドIDとライクIDを使用する必要があります。これにより、メモリ使用量が大幅に削減されます。

効率を改善する（速度を上げる、メモリを減らす）ために他にどのようなアルゴリズムまたはデータ構造を使用できますか？何らかの理由で、友達のリストをそれぞれのいいねに対して保存することはできません。実行時に計算する必要があります。私はこれをC++を使用して開発しているので、STLまたはブーストを使用するソリューションはさらに優れています。

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

なぜあなたがを使用しているのかわかりません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 に答える
0

「最も人気のあるいいね」を見つけることに興味があるので、これは「トップ数」、たとえばトップ5、トップ10などにのみ興味があることを意味しますか？もしそうなら、1つの可能なアプローチは、あなたがいいねごとに繰り返すように物事を並べ替え、N、そのようなものに関連付けられた友達の数を計算し、それが実行中の場合にのみそのようなものでさらに処理を行うことです'トップX'リスト。トリッキーな部分は、このようなループ構造を使用してNを効率的に計算することです（ナイーブな実装では、各フレンドをループします。各フレンドのように、各フレンドごとにループします。これに関連するすべてのデータはメモリからのものであり、それ以上の処理は行いません。つまり、「トップ10リスト」があり、そのリストにすでに10件のいいねを追加している場合は、そして、現在のlikeのNは、「トップ10リスト」の最小のNよりも小さいので、likeは無関係であることがわかります。基本的に、メモリフットプリントを大幅に削減する代わりに、冗長なループを実行するという取引を行います。これらのループは合理的に並列化することもできるので、余分なループはそれほど悪くないかもしれません。試さずに特定のユースケースでより効率的かどうかはわかりませんが、「トップ10」スタイルの出力が要件を満たしている場合は、この方向で検討する価値があるかもしれません。

于 2012-10-11T23:50:39.817 に答える