C# Tech. interjú – Algoritmus javítása

Az előző részben átírtuk a tesztfeladat adatbázisát hierarchikus szerkezetűre – ez azonban újabb file-ok feldolgozási igényét hozta magával. Ennyi adattal az alkalmazásban használt algoritmus már nehezen boldogul. Erről a kódról van szó:

var counters = new List<PersonNameWithLikeCount>();

foreach (var person in persons)
{
    var counter = 0;

    foreach (var candidate in persons)
    {
        if (candidate.LikedPersons.Contains(person.Name))
        {
            counter++;
        } // if
    } // foreach

    counters.Add(
        new PersonNameWithLikeCount()
        { 
            Name = person.Name, 
            LikeCount = counter 
        });
} // foreach

Ha ránézünk a kódra azonnal látszik az egymásba ágyazott ciklus, mind a kettő a persons listán halad végig. Így ez egy négyzetes algoritmus a persons elemszámára nézve. A belső ciklus magjában ráadásul egy elég drága művelet van – egy lineáris keresés.

Ha valakinek eszébe jutna gyorsítási ötletként a feladatot párhuzamosítani – az nem jó irány. Egy négy magos gép legjobb esetben negyedére csökkenti a feldolgozási időt. Ugyanakkor ez az előny elveszik, ha megduplázódik a persons lista mérete. A probléma az, hogy amikor duplázódik a személyek száma, négyszerezni kellene a processzorok számát. Ha jól megy az üzlet, és félévente duplázódik a feldolgozandó személyek mennyisége, elég sokat kell majd gépekre költeni. És mivel a gépigény meredekebben növekszik, mint a feldolgozandó adatok száma, előbb-utóbb a folyamat fenntarthatatlanná válik.

Okosabb vagy, mint hiszed!

Az az érdekes ebben az algoritmusban, hogy mindenkiben benne van, hogy hogyan kellene megcsinálni jól. Nem ugrik be? Nézzünk egy ekvivalens példát!

Az iskola szépe

Szinte mindenki járt középiskolába, és szinte minden középiskolában voltak diáknapok, vagy hasonló rendezvény. Ezeken sokszor lehetett szavazni különböző dolgokra, például ki a legjobb nő a suliban. Mivel a suliban sok jó nő van, és nehéz dönteni, mindenki bejelölhet több lányt is. Az a lány a legszebb, akire legtöbben szavaztak.

A számlálóbizottság

Tegyük fel, hogy kiválasztottak a szavazatok összeszámlálására. Hogyan fogunk eljárni? Azt csináljuk, hogy magunk elé veszünk egy papírlapot a szavazatok számlálására, és elkezdjük egyesével elővenni a szavazatokat. Ha a kezünkben van egy szavazat egy lány nevével, két eset lehetséges:

  • a lányra még nem szavaztak. Ekkor felírjuk a nevét, és a neve mellé húzunk egy rovást.
  • a lányra már szavaztak. Ekkor megkeressük a nevét, és mellé húzunk egy rovást.

Ezt addig ismételjük, még el nem fogytak a szavazatok. Végül megkeressük a három legtöbb szavazatot kapott lányt, és ők állnak a dobogóra.

És most digitálisan

Meg tudjuk ezt csinálni a saját programunkban? Itt a szavazatok a like listák, annyi a dolgunk, hogy ezeket végigvegyük:

foreach (var person in persons)
{
  foreach (var vote in person.LikedPersons)
  {
    ...
  }
}

Ez ugyan szintén egy egymásba ágyazott ciklus, de nem minden egymásba ágyazott ciklus jelent négyzetes algoritmust. Vegyük észre, hogy a persons hosszának növekedésével csak a külső ciklus fut tovább, a belső nem, hiszen ő a like listán megy végig. Összességében minden egyes like-ot csak egyszer érintünk, akárcsak amikor a való életben a szavazatokat vettük sorra. Ez az algoritmus lineáris a személyek számára nézve. Persze, ha a like lista hossza összefügg az adatbázisban található emberek számával, akkor nem lineáris, de jellemzően a kedvelt emberek számának mindenki esetében vagy egy felső korlátja, ami korlát annyira nem is magas. Így a like lista hosszának szempontjából lényegében mindegy, hogy húszezer vagy egymilliárd person rekord van az adatbázisban.

A nevek gyors keresése

Most jön az a rész, hogy aki szavazatot kapott, megkeressük a papíron. A papír esetében, ha azt vesszük észre, hogy nem csak a három legformásabb fenekű/keblű nő kap szavazatokat, akkor ki kell találni valamit, hogy a neveket gyorsan megtaláljuk. Kézenfekvő ötlet, hogy inkább 26 papírt (vagy legalább 26 régiót a papírokon) használunk, mindegyik az angol ábc egy betűjével. A nevet oda írjuk, amilyen betűvel – vagy amihez legközelebb álló betűvel – kezdődik a név. A neveket tehát egy gyors algoritmussal csoportokba osztjuk, hogy ott könnyebben meg lehessen találni őket.

Erről beugorhat a hash tábla, mint adatszerkezet, ami kicsit hasonlóan működik. Itt is a tárolandó/keresendő adatból generálunk egy értéket (tipikusan egy számot), és az érték alapján az adat helye gyorsan meghatározható az adatszerkezetben. A hash tábla egyik megfelelője a .NET esetében a Dictionary. Amit tenni fogunk tehát egy név felbukkanásánál, az az, hogy megnézzük, szerepel-e a dictionary-ben. Ha igen, akkor a hozzá tartozó bejegyzésben növeljük a szavazatok számát. Ha nem, akkor beletesszük a dictionary-be, egy kapott szavazattal:

// Ez lesz a "régiókra osztott lap":
var counters = new Dictionary<string, PersonNameWithLikeCount>();

foreach (var person in persons)
{
    foreach (var vote in person.LikedPersons)
    {
        PersonNameWithLikeCount personWithCounter;

        // felíruk már valaha a nevet?
        if (!counters.TryGetValue(vote, out personWithCounter))
        {
            // Még nem, írjuk fel egy szavazattal
            personWithCounter =
                new PersonNameWithLikeCount()
                {
                    Name = vote,
                    LikeCount = 1
                };

            counters[vote] = personWithCounter;
        }
        else
        {
            // már szerepelt, +1 szavazat
            personWithCounter.LikeCount++;
        } // else
    } // foreach
} // foreach

Ezzel készen is vagyunk. A javulás pedig:

LikeStatSpeedTest

Itt a vége

Eljutottunk a technikai interjú feladat végére. A feladat 1-es lépésére (CSV parser) nem született blog bejegyzés, hiszen abban a feladatban a refactor volt a lényeg, amit pedig kitárgyaltunk. A CSV parser megépítése ezek után triviális, lényegében egy string.split() köré épül.

Remélem, akik letöltötték és végigcsinálták a feladatokat, szórakoztatónak és hasznosnak találták.

  1. #1 by Dexx on 2013. April 19. - 13:09

    Köszönjük a cikksorozatot, sok tanulsággal szolgált, főleg azzal, hogy milyen komoly érvek tudnak szólni egyszerűnek tűnő dolgok ellen/mellett még egy ilyen egyszerű alkalmazásnál is. Szívesen olvasnék még ilyeneket🙂 Grat.

  2. #2 by luviktor on 2013. April 19. - 20:34

    Maximálisan egyetértek Dexx kommentjével, mind a tapasztalatokról, mind arról, hogy én is szívesen olvasnék még hasonlókat! Rengeteget tanulhat belőle egy kezdő, de még egy haladó(bb) fejlesztő is. Köszönet a sorozatért!

  3. #3 by kazatkazdothu on 2013. April 20. - 08:03

    Linq nem játszik?
    var firstTen =
    persons.SelectMany(d => d.LikedPersons, (person, s) => new { LikedPerson = s, person.Name })
    .GroupBy(d => d.LikedPerson)
    .Select(d => new PersonNameWithLikeCount { Name = d.Key, LikeCount = d.Count() })
    .OrderByDescending(d => d.LikeCount)
    .Take(10);

    • #4 by Tóth Viktor on 2013. April 20. - 16:00

      de, jó ötlet. Mondjuk én kicsit másképp írnám fel, a közbenső anonymous típus nélkül:

      var firstTen =
      persons.SelectMany(p => p.LikedPersons)
      .GroupBy(p => p)
      .OrderByDescending(p => p.Count())
      .Select(g => new PersonNameWithLikeCount
      {
      Name = p.Key,
      LikeCount = p.Count()
      })
      .Take(10);

      vagy hogy még linq-sabb legyen:

      var counters =
      from p in persons
      from l in p.LikedPersons
      group l by l into g
      orderby g.Count() descending
      select new PersonNameWithLikeCount
      {
      Name = g.Key, LikeCount = g.Count()
      };

      var firstTen = counters.Take(10);

      • #5 by kazatkazdothu on 2013. April 20. - 19:39

        Jogos, az nem kell, hogy ki kit like-ol, csak az, hogy kit hányan like-olnak, viszont a kétszeres Count() hívás teljesen felesleges. Azaz inkább :
        var firstTen =
        persons.SelectMany(p => p.LikedPersons)
        .GroupBy(p => p)
        .Select(g => new PersonNameWithLikeCount
        {
        Name = p.Key,
        LikeCount = p.Count()
        })
        .OrderByDescending(p => p.LikeCount)
        .Take(10);

        UI: A linq-ból az integrated query szintakszist ritkán használom, mivel túl sokszor kell az extension methodra átváltani, szinte csak join esetén látom célszerűnek, mivel egyéb esetben elég ronda tud lenni.

      • #6 by Tóth Viktor on 2013. April 20. - 21:04

        Helló,
        Azért gondolnám jobbnak a select-et az orderby után venni ebben az esetben, mert az orderby kénytelen “letekerni” azt az enumerable-t, amin dolgozik, azaz a kiértékelés ő előtte nem lesz deferred. Nem tudná ugyanis megcsinálni a rendezést, ha nem ismeri az összes elemet.
        Mivel végigveszi az összes elemet, ezért a példádban a select létrehoz sok PersonNameWithLikeCount példányt. Nálam csak 10-et hoz létre, mivel a select a rendezés után van. Persze időben ez gondolom néhány milisec plusz még több ezer példánynál is, inkább csak elvi szempontból érdekes, hogy nem hoz létre felesleges példányokat.
        Másik oldalról, a GroupBy() Grouping class példányokat hoz létre (Reflectorban nézem). Ez a Grouping viszont karbantart egy számlálót, azaz olcsó művelettel vissza tudja adni, hogy például “Kiss Pista” kulcs alá hány elem lett már csoportosítva. Emiatt a példámban a select-ben szereplő Count() hivás nem drága, implementációját tekintve csak egy return this.count hívás.

        Az integrated query szintaxisról alkotott véleményeddel teljes mértékben egyetértek. Szerintem amúgy is tisztább és jobban érthetőbb közvetlenül az extension methodokat látni (nekem legalábbis), főleg egy összetettebb lekérdezésnél.

  4. #7 by olhptr on 2013. June 25. - 19:51

    Kedves Tóth Viktor!

    Nem rég akadtam az Ön blogjára, rendkívül precíz, alapos és nem utolsó sorban érthető tartalmak kerültek posztolásra.
    Elengedhetetlenül fontos ismeret azoknak, akik C# nyelven illetve a .NET keretrendszerben akarnak programozni.
    Viszont én C++ -ban töltöm a legtöbb időmet.

    A kérdésem a következő lenne: először is elnézést, ugyanis a hozzászólásom lényegi része semmi pluszt nem tud hozzáadni a blogjához.
    Azt szeretném kérdezni, hogy ismer-e az Ön blogjának a minőségével rendelkező olyan blogot ahol C++ -al kapcsolatos tartalmak vannak.
    Tehát ugyanilyen blog érdekelne, csak C++ -ban, az sem gond ha nem magyar nyelvű.

    Válaszát előre is köszönöm,
    Péter

    • #8 by Tóth Viktor on 2013. June 25. - 23:08

      Kedves Péter,

      Köszönöm a dícsérő szavakat. C++ ban már évek óta nem fejlesztek, emiatt nem is olvasgatok a témában blogokat. Így sajnos ajánlani sem tudok semmit.

      • #9 by olhptr on 2013. June 25. - 23:10

        Értem.
        Köszönöm szépen a visszajelzést, további sok jó tartalmat kívánok a blogra🙂

  5. #10 by Anonymous on 2014. August 14. - 11:35

    Csatlakoznék pár előttem szólóhoz:
    Szerintem nagyon hasznosak és színvonalasak az írásaid, szívesen olvasnék még többet!
    Várható folytatás?

    • #11 by Peller Viktor on 2014. August 14. - 21:22

      sajnos nagyon keves idom/energiam van/volt az elmult 2 evben erre (kisgyerek). Szeretnem folytatni majd, vannak is felkesz dolgok, de inkabb video anyagokban gondolkodom, mert az anyagok terjedelme sokakat elrettent, hogy vegigolvassa🙂 Hogy mikor, azt nem tudom, de az elkovetkezo fel evben meg valoszinuleg nem.

      • #12 by Anonymous on 2014. September 29. - 10:32

        Azért időnként visszanézek, hátha 🙂

        Köszi a választ és kellemes gyermeknevelést🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

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

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: