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

Az interjú C# gyakorlati feladatban a második megoldandó lépés a file alapú adatbázis szerkezetének átalakítása. Az az igény, hogy egy adott gyökérkönyvtártól számítva az összes file-t fel kell dolgozni, beleértve az alkönyvtárban található állományokat is.

A program jelenlegi felépítése olyan, hogy egy IEnumerable<string> ként várja a feldolgozandó állományok neveit, így a dolgunk az, hogy a könyvtárszerkezetből összegyűjtsük az összes file-nevet.

Nevezetes algoritmusok

A könyvtárak bejárása lényegében egy fabejárás, amely egy típusfeladata a főiskolákon/egyetemeken a rekurzió tanításának. Emiatt aki olyan helyen tanult, szinte azonnal rávágja, hogy ezt a feladatot rekurzióval kell megcsinálni.

De mi az a rekurzió?

Ez a kérdés nagyon gyakran elhangzik az interjúkon, és a válasz jellemzően: “Amikor egy metódus saját magát hívja”. Ez a válasz azonban felületes, és nem is fedi a lényeget.

A rekurzió nem az implementáció szempontjából érdekes (minthogy egy metódus magát hívja). A rekurzió mint feladatmegoldási stratégia érdekes a programozásban.

Mit értünk feladatmegoldási stratégia alatt? Akkor tudjuk a feladatot rekurzióval megoldani, ha a megoldás során a feladatot több, kisebb, az eredetihez hasonló feladatra bontjuk. Nézzünk egy triviális (ám de önmagában értelmetlen) példát. Tegyük fel, hogy van egy tömbünk:

int[] a = { 1, 2, 3, 4, 5, 6 };

A feladat egy olyan algoritmus megadása, amely minden elem értékét megnöveli 1-gyel. Hogy ne legyen könnyű a dolgunk, tegyük fel, hogy egy bug-os C# compillerrel dolgozunk, amely nem tudja lefordítani azokat a vezérlési szerkezeteket, amelyek ciklusszervezésre használhatóak. Így nincs for, foreach, while, de még akkor is hibázik, ha if/goto-val próbálkozunk. De amit például tenni tudunk, hogy a tömb i-ik elemét meg tudjuk növelni.

Hogyan használhatjuk a rekurzió elvét ilyen körülmények között? A problémában, amit meg akarunk oldani, vannak elemek: [a1,…,an]. Amit nem tudunk csinálni, hogy végigiterálunk az elemeken. Amit tudunk csinálni, hogy vesszük a1-et, vagy vesszük a5-öt. A gond, hogy nem tudjuk, hogy n az tíz vagy százmillió. Emiatt ez nem megoldás:

static void Increment(int[] a)
{
  if (a.Lenght > 0)
    a[0]++;
  else
    return;

  if (a.Lenght > 1)
    a[1]++;
  else
    return;

...

  if (a.Lenght > 2345643)
    a[2345643]++;
  else
    return;
...
}

Most oldjunk csak meg egy részproblémát:

static void Increment(int[] a)
{
  if (a.Lenght > 0)
    a[0]++;
}

Mi a maradék probléma? Az, hogy [a2,…,an]-ban meg kell növelni az értékeket. Ez egy majdnem ugyanolyan probléma, mint az eredeti – csak kisebb. Hogyan tudjuk ezt felhasználni? Vegyük egy kicsit általánosabbra a feladatot és azonnal látni fogjuk:

adott [a1,…,ak,…,an]

A feladat, hogy [ak,…,an] elemeket növeljük meg eggyel. Ha k=1, akkor az eredeti feladatot kapjuk. Ha most megoldjuk a következő részproblémát:

static void Increment(int[] a, int k)
{
  a[k]++;
}

akkor a maradék feladat az, hogy [ak+1,…,an] elemeket kell megnövelni, ami már kisebb, és pontosan olyan feladat, mint amit az imént megoldottunk. Mivel a feladat ugyanaz, ugyanúgy kell megoldani, mint a most éppen megoldás alatt álló eredeti feladatot – csak a kisebb, maradék résztömbre:

static void Increment(int[] a, int k)
{
  a[k]++;
  Increment(a, k+1);
}

Ez már majdnem jó – csak egy plusz dologra kell figyelni. Ahogy egyre kisebb és kisebb alproblémát faragunk, a probléma egyszer csak eltűnik – és nekünk ezt a pillanatot észre kell venni. Ez nem olyan nehéz, amikor k = n, akkor készen vagyunk, nincs egy még kisebb problémánk, emiatt ezt nem kell megoldani sem:

static void Increment(int[] a, int k)
{
  a[k]++;

  if (k+1 < a.Length)
    Increment(a, k+1);
}

Miért fontos érteni a rekurzió igazi lényegét? Mert sokkal könnyebb és hatékonyabb azon gondolkodni, hogy hogyan osszuk a feladatot kisebb és ugyanolyan feladatokra, mint azon, hogy hogyan írjunk egy metódust, ami saját magát meghívhatja – ráadásul nem minden rekurzívan megoldható feladatnál a rekurzív metódushívás a legjobb megoldás. Ha valakinek be is ugrik, hogy a könyvtárbejárás rekurzióval megoldható, ha nem jön rá, hogy melyek a részproblémák, akkor nem fogja tudni felírni a rekurzív metódust.

Könyvtárbejárás és részproblémái

Ha valaki megértette – vagy eleve értette, hogy mi a rekurzió lényege, akkor a következő már triviális lesz számára: adott egy könyvtárrendszer egy gyökér könyvtárral. A feladat, hogy az összes állomány nevét gyűjtsük össze a könyvtárrendszerből.

Amikor egy könyvtárban vagyunk (pl a gyökérben) mi az a részfeladat, amit könnyen meg tudunk oldani? Az adott könyvtárban lévő állományok neveit könnyen össze tudjuk gyűjteni.

Mi (mik) azok a részproblémák, amelyek hátramaradnak, de ugyanolyan felépítésűek, mint az a probléma, amit most éppen megoldunk? Természetesen az alkönyvtárakban levő file-ok összegyűjtése.

A könyvtárbejárás implementálása

Az eredeti feladatban egy FileSystem statikus osztály-t használhatunk arra, hogy egy könyvtárban található file-okat illetve alkönyvtárakat összegyűjtsük. A metódus, amit implementálni készülünk, egy számára root-nak tekinthető könyvtárban fog dolgozni. Ahhoz, hogy tudja mi ez a root, ezt meg kell kapnia például metódus paraméterként:

void GetFileList(string root)

Ezen kívül csak bizonyos típusú file-ok kellenek, azaz kell egy szűrő:

void GetFileList(string root, string sourceType)

Amikor ez megvan, az adott szinten levő részprobléma megoldása nagyon egyszerű:

void GetFileList(string root, string sourceType)
{
  var result = FileSystem.GetFiles(root, sourceType);
  ...
}

A kérdés, hogy hogyan érdemes használni a result-ot? A következő lépés ebben a metódusban az lesz, hogy rekurzívan megoldjuk a hátramaradt részproblémákat, ami részeredményeket fog szolgáltatni. Ha a GetFileList() a saját részmegoldását visszatérési értékként adja vissza, akkor tömbök tucatjait kell folyamatosan összefűzgélni. Bár ez nem különösebben bonyolult, még egyszerűbb, ha azt mondjuk: minden részmegoldás folyamata (azaz egy GetFileList() hívás) egy a feladatra nézve globális IList-be tölti fel a maga részeredményeit. Ezt az IList-et pedig paraméterben fogjuk körbeadogatni. Ezek alapján:

void GetFileList(string root, string sourceType, IList<string> cumulativeFileList)
{
    Array.ForEach(
        FileSystem.GetFiles(root, sourceType), 
        f => cumulativeFileList.Add(f));
    ...
}

A fenti kódban a FileSystem.GetFiles() hívás visszaad egy tömböt. Ezt a tömböt pedig az Array.ForEach segítségével belepumpáljuk a paraméterként körbeadogatott, végső eredményt gyűjtögető listába.

A teljes probléma egy könnyen megoldható szakaszát tehát megoldottuk, és hátramaradtak az ugyanolyan, de kisebb részproblémáink, ezek az alkönyvtárak bejárása. Nincs más hátra, mint minden egyes alkönyvtárra elvégezzük pontosan azt a műveletet, aminek a végrehajtásán éppen dolgozunk:

void GetFileList(string root, string sourceType, IList<string> cumulativeFileList)
{
    Array.ForEach(
        FileSystem.GetFiles(root, sourceType), 
        f => cumulativeFileList.Add(f));

    Array.ForEach(
        FileSystem.GetDirectories(root),
        d => GetFileList(d, sourceType, cumulativeFileList));
}

Az alkönyvtárak – alfeladatok – feldolgozásához szintén az Array.ForEach()-t használjuk. Első lépésben a FIleSystem.GetDirectories() hívás visszaad egy alkönyvtár listát. Az Array.ForEach veszi az összes alkönyvtár nevét, és mindegyikkel meghívja a GetFileList() metódust.

Végül már csak egyetlen metódus van hátra, ami az egész folyamatot beindítja, tehát ami a teljes “nagy” feladat megoldását elkezdeni:

IEnumerable<string> GetFileList()
{
    var result = new List<string>();

    GetFileList(
        this.GetDatabasePath(),
        this.GetSelectedSourceType(),
        result);

    return result;
}

Kell ide a rekurzió?

Bár a könyvtárszerkezet rekurzív jellegű (egy könyvtárban ugyanolyan dolgok lehetnek, mint az adott könyvtár maga), nem feltétlenül kell programozó értelemben vett rekurzió – azaz önmagát hívó metódus – a bejárásához. Ha a mostani példánkban nem is jelent gondot, az önmagát hívó metódusoknak az a problémája, hogy a feladatmegoldás folyamatának állapotát ugyanott tartja, ahol a futtató környezet a program hívásláncának állapotát – a végrehajtási vermen. Ha ez bonyolultan hangzik, azt szeretném kifejezni, hogy egy önmagát hívó metódus esetében nem lehet azt megcsinálni, hogy az algoritmus felénél megállok, visszatérek az eredeti hívóhoz (a rekurzív híváslánc elé) majd egyszer valamikor, egyéb teendők után azt újra folytatom, ahol korábban abbahagytam.

Hogy még világosabb legyen, tegyük fel, hogy a könyvtárszerkezet csilliárd elemet tartalmaz, ami nem fér be a memóriába. Mégis, a file-okat fel kell dolgozni. Ehhez olyan algoritmus kellene, ami egyenként – vagy legalább szakaszosan – szolgáltatja az állományok neveit. Amit most kidolgoztunk, az egyben felolvassa az összes állományt.

Hogy lássuk, hogy az önmagát hívó metódusoknak is van alternatívája, egy ilyen megoldást nézünk meg legközelebb.

  1. StackOverflow kivédése rekurziónál - pro C# tology - devPortal
  2. C# Tech. interjú – nem-rekurzív könyvtárbejárás - 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: