Pertanyaan Menemukan suka yang paling populer di jaringan teman saya


Saya sedang mencari cara untuk menemukan orang-orang yang paling populer di jaringan teman saya. "Paling populer di jaringan teman saya" didefinisikan sebagai "memiliki jumlah suka terbanyak oleh teman-teman saya".

Misalkan setiap teman memiliki id unik dan memiliki sejumlah halaman yang disukai. Jadi, mengingat sejumlah teman seperti itu, saya ingin menemukan suka yang disukai oleh sebagian besar teman, dan juga teman-teman yang menyukai hal ini. Pada dasarnya, saya ingin menunjukkan sesuatu seperti "Teman Anda X, Y & Z menyukai ini."

Solusi pertama saya adalah menggunakan Peta (untuk menyimpan pemetaan terbalik: seperti-> set) dan Antrean Prioritas (untuk menemukan N teratas). Berikut adalah algoritme saya (menggunakan 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();
}

Karena STL secara internal menggunakan Red Black Tree untuk mengimplementasikan peta dan min / max heap untuk antrean prioritas, pendekatan ini tampaknya cukup cepat bagi saya. Tetapi jika saya memiliki 100 teman dan masing-masing memiliki 100 suka, penggunaan memori akan sangat besar. Tentu saja, daripada menyimpan seluruh objek, saya harus menggunakan id teman dan id seperti untuk semua perhitungan yang akan mengurangi penggunaan memori banyak.

Apa algoritma atau struktur data lain yang dapat digunakan untuk meningkatkan efisiensi (meningkatkan kecepatan, mengurangi memori)? Untuk beberapa alasan, saya tidak dapat menyimpan daftar teman yang mirip, harus dihitung dalam waktu berjalan. Saya mengembangkan ini menggunakan C ++, jadi solusi menggunakan STL atau meningkatkan akan lebih baik.


5
2017-09-17 09:30


asal


Jawaban:


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]

Jika P adalah jumlah halaman, maka itu akan memiliki kompleksitas ruang O(P).

Jika F adalah jumlah teman dan L menjadi halaman rata-rata disukai oleh semua orang. Maka kompleksitas waktunya akan menjadi O(F*L). Jadi, bahkan jika Anda melintasi semua teman lagi untuk memeriksa siapa yang menyukai halaman itu, itu tidak akan menambah banyak kerumitan.

O(F*L) + O(F) would remain O(F*L)

Saya pikir lebih baik untuk beralih lagi daripada menyimpan teman-teman.

Atau Anda dapat menyimpan referensi terbalik itu sendiri untuk halaman. Itu untuk setiap halaman, menyimpan daftar teman yang disukai. Itu tidak akan memakan banyak ruang dan akan melakukan pekerjaan Anda dalam kompleksitas minimum.


1
2017-09-17 14:06



Saya gagal melihat mengapa Anda menggunakan priority_queue. Tentu, itu efisien melacak elemen maksimum saat wadah diubah. Tetapi Anda hanya perlu operasi single-shot, setelah langkah pertama. Kesimpulan:

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;
}

Tentu saja ini bekerja hanya untuk N = 1, tapi itu cukup untuk `teman-teman Anda X, Y, dan Z seperti ini" pilihan teratas.


0
2017-09-17 12:45



Karena Anda tertarik untuk menemukan "suka yang paling populer", apakah ini berarti Anda hanya tertarik pada 'beberapa teratas', misalnya, 5 besar, 10 teratas, dll.? Jika demikian, salah satu pendekatan yang mungkin adalah untuk mengatur ulang hal-hal sehingga Anda mengulangi per-seperti, menghitung N, jumlah teman yang terkait dengan suka, dan kemudian hanya melakukan pemrosesan lebih lanjut pada yang seperti jika itu membuatnya menjadi berjalan ' daftar X teratas. Bagian yang sulit adalah menghitung N secara efisien dengan struktur pengulangan seperti itu (penerapan naif akan melingkupi setiap teman. Seperti untuk setiap teman, per suka..yuk ..), tetapi manfaatnya adalah jika N cukup kecil, Anda dapat menjatuhkan semua data yang terkait dengan itu seperti dari memori dan tidak melakukan pemrosesan lebih lanjut di atasnya. Artinya, jika Anda memiliki 'daftar 10 teratas', dan Anda telah menambahkan 10 suka ke daftar itu, dan arus seperti N lebih kecil dari N terkecil di 'daftar 10 teratas', Anda tahu bahwa suka tidak relevan . Pada dasarnya, Anda membuat perdagangan di mana Anda melakukan beberapa pengulangan berlebihan dalam pertukaran untuk jejak memori yang berkurang secara drastis. Mereka loop juga bisa diparalelkan, jadi mungkin perulangan ekstra tidak begitu buruk. Sulit untuk mengatakan jika itu lebih efisien untuk kasus penggunaan khusus Anda tanpa mencobanya, tetapi mungkin perlu ditelusuri dalam arah ini jika keluaran '10 besar' memenuhi persyaratan Anda.


0
2017-10-11 23:50