Esileht > Alustus > Koondfunktsioonid ja pudelikael

Koondfunktsioonid ja pudelikael


LINQ koos oma koondfunktsioonidega on suurepärane asi. Rööpes on sama asi saadaval nime all PLINQ (Parallel LINQ). See kattub suuremas osas jada-LINQiga, seega on see asjaga tuttavale väga lihtne kasutada.

Ainuke küsimus, mis tekib, on see, kuhu kirjutada AsParallel(). Tooksin ühe keerulisema praktilise näite, millega saate katsetada.

Oletame, et meil on sotsiaalvõrgustik, kus igal inimesel võib olla sõpru, ja sul on vaja soovitada kasutajale uusi sõpru, pakkudes neid inimesi, kellega tal juba on ühiseid sõpru. Mida rohkem ühiseid sõpru, seda eespool pakutav nimekirjas on.

Nii, lihtne… aga et asja keerulisemaks teha, ei ole meie objekti struktuur kõige paremate killast. Teeme iga inimese kohta järgmise objekti:

class Person
{
public int Id;
public Person[] Friends;
}

Kasutame tavalist jadaprogrammi, et koostada 10 000 liikmega sotsiaalvõrgustik, kus igal liikmel on kuni 300 sõpra:

//tekitame 10000 isikut
Person[] persons = new Person[10000];
Random r = new Random(); 

//paneme neist igaühele 0 kuni 300 sõpra
for (int i = 0; i < persons.Length; i++)
persons[i] = new Person { Id = i + 1, Friends = new Person[r.Next(300)] };

//valime sõpradeks juhuslikud inimesed
foreach (Person person in persons)
for (int i = 0; i < person.Friends.Length; i++)
while (person.Friends[i] == null)
{
Person friend = persons[r.Next(persons.Length)];
//kontrollime, et sõber ei oleks mina ise ja et sõpru ei satuks topelt
if (friend != person && !person.Friends.Contains(friend))
person.Friends[i] = friend;
}

Jadaprogrammi kasutasin seepärast, et Random objekt ei ole lõimeturvaline. Muidu võiks seda ka rööbelda.

Võtame juhusliku inimese, kellele hakkame uusi sõpru soovitama:

//valime seltskonnast juhusliku isiku
Person me = persons[r.Next(persons.Length)];
Console.WriteLine(“Me: “ + me.Id + ” having “ + me.Friends.Count() + ” friends”);
int maxcount = 10;

Sain sellise, kellel oli 254 sõpra.

Tegin nüüd lähteviiteks jadaprogrammi, millega soovitused leida:

//siia salvestame potentsiaalsed sõbrad
Dictionary<Person, int> potential = new Dictionary<Person, int>(); 

//käime läbi kõik minu sõbrad
foreach (Person friend in me.Friends)
//käime läbi kõik inimesed
foreach (Person person in persons)
//kontrollime, et see ei oleks mina ise ega minu sõbrad
if (person != me && !me.Friends.Contains(person))
//kas minu sõber on tema sõber?
if (me.Friends.Contains(friend))
//lisame potentsiaalsete sõprade hulka
if (potential.ContainsKey(person))
potential[person]++;
else
potential[person] = 1;

//sorteerime ühiste sõprade kogused
List<int> quantities = new List<int>();
foreach (int quantity in potential.Values)
if (!quantities.Contains(quantity))
quantities.Add(quantity);
quantities.Sort();

//käime ühiste sõpradega inimesed läbi, alustades suurima ühisarvuga
int count = 0;
for (int i = quantities.Count – 1; i >= 0 && count < maxcount; i–)
foreach (Person person in potential.Keys)
if (potential[person] == quantities[i])
{
Console.WriteLine(person.Id + ” (“ + quantities[i] + ” mutual friends)”);
if (++count > maxcount)
break;
}

Uhh, päris pikk sai. Selle programmi läbimise ajaks võtame 100%.

Teeme sama asja LINQiga:

foreach
(
var person in
//käime läbi kõik minu sõbrad
me.Friends
//valime kõigi isikute hulgast need, kel on minuga ühiseid sõpru
.SelectMany(s => persons.Where(p => p != me && p.Friends.Contains(s)))
//välistame need, kes on juba minu sõbrad
.Where(w => !me.Friends.Contains(w))
//grupeerime isiku järgi
.GroupBy(g => g)
//tekitame uue grupeeritud objekti
.Select(p => new
{
Person = p.Key,
Count = p.Count()
})
//järjestame kahanevalt
.OrderByDescending(o => o.Count)
//võtame lubatud arvu
.Take(maxcount)
) Console.WriteLine(person.Person.Id + ” (“ + person.Count + ” mutual friends)”);

See jada-LINQ-programm võttis samade tulemustega 53% ajast (mis näitab, et minu jadaprogrammi saaks veel oluliselt optimeerida).

Ja kogu see krempel rööpes nägi välja sama, ainult et AsParallel() oli pandud sellisesse kohta: s => persons.AsParallel().Where.

Rööplemine võttis aega ainult 10% algsest jadaprogrammist.

Pane tähele, et AsParallel() on ainult ühes kohas, esimese filtri ees. Siin seisnebki rööplemise kunst: leida see õige koht, kuhu see maagiline sõna sisse kirjutada. Kirjuta see valesse kohta ja kogu protsess võib minna nii pikaks, et isegi pärast lõunat ei ole veel valmis.

Kui sa nüüd mõtlesid, et ma olen vana kala ja mul oli õige koha leidmine käkitegu, siis sa eksid. Ma katsetasin ikka kümneid variante, enne kui leidsin selle, mis on parim. See koht on loogiline, sest põhiline on leida inimesed, kellega on ühised sõbrad. Kuna neid inimesi on suhteliselt vähe, ei tasu rööplemine hiljem end enam ära.

Kas AsParallel() võiks olla mitmes kohas? Proovige ja katsetage, mina ei saanud ajavõitu, tegelikult hoopis kaotasin ajas. Põhjus on ilmselt selles, et lõimesid tuleb siis jagada mitme rööpe vahel ja see piirab pudelikaelale kättesaadavate ressursside arvu. Aga pudelikael peaks saama maksimaalse võimaliku.

Aga proovige, kas suudate seda värki veelgi optimeerida. Ja andke oma avastustest häbenemata teada.

Õpetus

Õpetus on ilmne: leia koodist üks pudelikael ja kasuta rööbet selles kohas ning efekt võib olla tohutu.

  1. Kommentaare veel pole.
  1. No trackbacks yet.

Lisa kommentaar

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Muuda )

Twitter picture

You are commenting using your Twitter account. Log Out / Muuda )

Facebook photo

You are commenting using your Facebook account. Log Out / Muuda )

Google+ photo

You are commenting using your Google+ account. Log Out / Muuda )

Connecting to %s

%d bloggers like this: