C# Tech. interjú – nem-rekurzív könyvtárbejárás

Korábban adtunk egy rekurzív megvalósítást a könyvtárbejárás problémájára. Az a megoldás rendben van, azonban felvetettünk egy elvi problémát: mi van akkor, ha valamilyen oknál fogva az algoritmust szakaszosan kell végrehajtani. Az önmagát hívó metódusokkal az a baj, hogy az algoritmus munkaállapota a hívási vermen van szétterítve metódus paraméterek és lokális változók formájában. Emiatt nem megy az, hogy a munkaállapotot elmentjük, és egy későbbi időpontban folytatjuk a munkát.

Hogy másképpen közelítsük meg könyvtárbejárás problémáját, mint rekurzív fabejárást, végezzünk el egy gondolatkísérletet.

Hamupipőke és a matrjoska babák

Tegyük fel, hogy a Hamupipőke történetének egy betegesen sznob feldolgozásába kerültünk, mint főszereplő. Ebben a történetben van egy nagy matrjoska baba. Ha a babát kinyitjuk, akkor nem szimplán egy kisebb matrjoska baba van benne. Ebben az esetben egy babán belül lehet több kisebb baba egymás mellett, ezen kívül lehetnek benne kisegerek.

A gonosz mostoha, mielőtt elment a lányaival a bálba, megparancsolta, hogy etessük a macskát egerekkel, amikor csak kéri. Ha kinyitunk egy babát, akkor a benne levő egerek persze el akarnak szaladni, emiatt egy kis ládikát használhatunk ideiglenes tárolónak, amiből az egerek egyesével kiemelhetők. Ha elfogyott az egér, de a macska kér még, akkor fel kell bontanunk egy újabb babát – amit közvetve vagy közvetlenül az eredeti nagy baba tartalmazott.

Gondot okoz Hamupipőkének, hogy hogyan járjon el a macska etetése közben? Nem, mindannyian azonnal tudjuk mit fog csinálni. Algoritmizálva körülbelül ezt:

  1. kezdetben Hamupipőke asztalán van az egyetlen nagy matrjoska baba.
  2. várakozni a macskára, hogy enni kérjen.
  3. (a macska enni kér)
  4. ha van egér a kis dobozban, folytasd a 7-es pontban.
  5. ha nincs több baba az asztalon, akkor odébb rúgni a macskát, algoritmus vége.
  6. venni egy tetszőleges babát az asztalról, és kinyitni.
  7. a babában levő többi babát az asztalra tenni.
  8. a babában levő egereket a kis dobozba tenni.
  9. (a szétnyitott babát eldobni)
  10. egy egeret adni a dobozból a macskának.
  11. vissza 1-re

Érdekes, hogy ez az algoritmus a való életben (már amennyire a fenti gondolatjáték valószerű) triviálisan adódik és gondolkodás nélkül így cselekednénk. Mégis, akivel eddig szóba került, a könyvtárbejárásnál szinte mindenki a rekurzív metódushívással való bejárást mondta. Pedig a fenti elv egy az egyben átfordítható a könyvtárbejárásra.

Valószínű mindenki rájött, hogy a matrjoska baba a könyvtárakat, az egerek pedig a file-okat képviselik. A programban asztal és dobozka helyett most két queue adatszerkezetünk lesz, az egyikbe a könyvtárakat, a másikba a file-okat tesszük. Ebből kiindulva:

  1. A root könyvtár elhelyezése a könyvtár queue-ba.
  2. várni, hogy file-t kérjenek.
  3. ha van file a file queue-ban, akkor folytasd a 7-es pontban.
  4. ha nincs több könyvtár a könyvtár queue-ban, algoritmus vége.
  5. venni egy könyvtárat a könyvtár queue-ból, és beolvasni a könyvtár tartalmát.
  6. a talált könyvtárakat a könyvtár queue-ba tölteni.
  7. a talált file-okat a file queue-ba tölteni.
  8. adni egy file-t a file queue-ból.
  9. vissza 1-re

Van tehát egy jó könyvtárbejáró algoritmusunk, rekurzív metódushívás nélkül, már csak implementálni kell.

Enumerátorok II.

Az interjú feladatban egyszer már találkoztunk az enumerátorokkal, amikor az volt a szándékunk, hogy eszközt adjunk ahhoz, hogy a Person-ok gyűjteményének egy file alapú ábrázolásán egyesével végighaladjunk. A feladat most is hasonló, csak itt egy file rendszerben található file-ok nevein kell egyesével végighaladni. Az enumerátor most is használható eszköz lehet.

A Person-ok esetén az Enumerable osztály kicsit szokatlan volt a hagyományos helyzetekhez képest abban, hogy egy paraméter alapján más és más enumerátor osztályt gyártott egy Factory osztály segítségével, illetve kihasználtuk az IDisposable() interfészt. Az esetek többségében azonban az Enumerable és az Enumerator kapcsolata sokkal tisztább és a megvalósítás egyszerűbb. Az IEnumerable megvalósítás képviseli valamilyen elemek sorozatát, az IEnumerator megvalósítás pedig ezt egyszerűen leszámolja.

C# generált enumerátorok

Az egyszerű helyzetekben az a jó, hogy ekkor a C# fordító ad egy nagy segítséget számunkra. Miért kell a segítség? Azért, mert az iterátorok implementációja kifordított a programozói logikához képest. Amikor valamilyen elemeken végig szeretnénk haladni, akkor a gondolkodásunkban természetesen jelenik meg egy ciklus. Viszont ha éppen egy iterátort implementálunk, akkor ezt a ciklust szét kell szabdalni, és úgy tenni az IEnumerator interfész MoveNext()metódusába, hogy minden forduló közben visszatérjen a hívóhoz. Ehhez azt kell elérnünk, hogy a ciklus közepéből adjuk vissza a vezérlést a MoveNext() hívójának, és amikor a MoveNext()-et újra hívják, akkor találjunk vissza a ciklus közepére, ugyanazzal a ciklusállapottal, ahogy korábban a ciklusból kiléptünk. Ez néha könnyebb, néha nehezebb feladat. Mit segít a C# fordító?

Nézzük például a fenti könyvtárbejáró algoritmust, ha nem egy iterátor MoveNext() metódusába kell belekódolni, hanem egyszerűen csak ki akarjuk írni az eredményt a képernyőre. Ekkor valami ilyesmit írnánk fel:

public void DumpFiles(string root, string fileType)
{       
    Queue<string> fileQueue = new Queue<string>(); // a "doboz"
    Queue<string> dirQueue = new Queue<string>();  // és az "asztal"

    dirQueue.Enqueue(root);     // a nagy "matrjoska baba" az asztalra

    // addig dolgozunk, amíg van valami az asztalon vagy a dobozban
    while (dirQueue.Count > 0 || fileQueue.Count > 0)
    {
        // van egér a dobozban?
        if (fileQueue.Count > 0)
        {
            // akkor a dobozból kap egeret a macska
            Console.WriteLine(fileQueue.Dequeue());
        }
        else
        {
            // különben fel kell bontani egy új babát
            var dirToProcess = dirQueue.Dequeue();

            // a babából minden egér a dobozba
            Array.ForEach(
                FileSystem.GetFiles(dirToProcess, fileType),
                f => fileQueue.Enqueue(f));

            // és minden baba az asztalra
            Array.ForEach(
                FileSystem.GetDirectories(dirToProcess),
                d => dirQueue.Enqueue(d));
        } // else
    } // while
} // DumpFiles()

A fenti implementáció természetesen adódik. Amit a MoveNext()-hez el kellene érni, hogy a ciklus képes legyen visszaadni a vezérlést a Console.WriteLine-nál a hívónak, és a következő MoveNext() hívásnál ide találjon vissza, hogy folytassa a munkát. A while ciklusunk szerencsés felépítése miatt ez most nem is lenne olyan nehéz feladat. Ugyanakkor még egyszerűbb, ha elfogadjuk a C# segítő kezét:

internal static class FileBasedDatabase
{           
    internal static IEnumerable<string> Files(string root, string fileType)
    {       
        Queue<string> fileQueue = new Queue<string>();
        Queue<string> dirQueue = new Queue<string>();

        dirQueue.Enqueue(root);

        while (dirQueue.Count > 0 || fileQueue.Count > 0)
        {
            if (fileQueue.Count > 0)
            {
                yield return fileQueue.Dequeue();
            }
            else
            {
                var dirToProcess = dirQueue.Dequeue();

                Array.ForEach(
                    FileSystem.GetFiles(dirToProcess, fileType),
                    f => fileQueue.Enqueue(f));

                Array.ForEach(
                    FileSystem.GetDirectories(dirToProcess),
                    d => dirQueue.Enqueue(d));
            } // else
        } // while
    } // Files()
} // class FileBasedDatabase

Mi történik? A ciklusban a Console.WriteLine ki lett cserélve egy yield return-ra. Ezzel mondjuk a C# fordítónak, hogy ott akarjuk megtörni a ciklusunkat, ezt az értéket szeretnénk visszaadni a MoveNext() hívásnál, és ide szeretnénk visszatalálni a következő híváskor. Ez alapján fogja a C# fordító átszabdalni a kódot. Ezen kívül mást is csinál a C# fordító. Az iterátor pattern-ben van egy Aggregate (Enumerable) és egy Iterator (Enumerator). Nekünk egyiket sem kell megvalósítani. A C# fordító ugyanis generál nekünk két osztályt. Lesz egy IEnumerable, ami az Aggregate szerepkört veszi fel az iterátor patternben. A mi metódusunk (Files) valójában ezt a példányt fogja visszaadni az átalakítás után. A generált IEnumerable megvalósításnak a C# fordító elkészíti a GetEnumerator() metódusát, ami ugyancsak egy C# fordító által generált osztályt fog visszaadni. Ez lesz az iterátor pattern iterátora, .NET terminológiával egy enumerátor. Ebben az osztályban lesz a mi átalakított kódunk. A fentieket próbálja szemléltetni a következő ábra:

LikeStatGenEnumerator

A látszat megtéveszthet

A fenti FileBasedDatabase.File() metódus tehát átalakul fordítás közben. Ha ezt nem vesszük figyelembe, nyomkövetés közben könnyen meglepődhetünk. Tegyük fel, hogy az alábbi módon próbáljuk a vezérlést a töréspontra irányítani:

DebugEnumWontStop

Ha megnyomom az F5-öt, megállunk a törésponton? A Main() metódus a Files()-t hívja, a Files()-nak pedig az első sorában ott a töréspont. A kód mégsem áll meg, és hogy miért, elég ránézni arra az ábrára, ami a kód szétvágását próbálja bemutatni. A Files() metódus belseje át lett mozgatva egy generált enumerátor osztály MoveNext() metódusába, és a töréspontot mi igazából oda tettük. Akkor áll meg a vezérlés, ha a files-tól kérünk egy enumerátort, és azon meghívjuk a MoveNext()-et:

var files = FileBasedDatabase.Files(@"c:\temp", ".txt");
var enumerator = files.GetEnumerator();
enumerator.MoveNext();

A következő részben

Most, hogy kibővítettük az adatbázist, az interjú feladat programja nagyon hosszú ideig számol a megnövekedett adatmennyiségen. Ez az alkalmazott algoritmus miatt van. A következő cikkben feljavítjuk az algoritmust, ami az interjú feladatkiírásának a 3-ik lépése.

  1. C# Tech. interjú – Algoritmus javítása - pro C# tology - devPortal

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: