C# tömbök mesteri szinten (1)

Még régebben találtam rá Put About tömbökkel foglalkozó írására. Mivel az ott leírtakat nemigen lehet megtalálni egyetlen egy magyar nyelvű C#-os könyvben sem, úgy gondoltam, hogy most itt a blogomban is megjelenítem, remélve azt, hogy így még több emberhez eljuthat ez a remek írás.

Tömbölés - a kezdet

Elismerem, picit fura a cím, tegyük tisztába hát. A "Tömbölés" szót ebben az értelemben én találtam ki, és magyarról magyarra fordítva valami "tömbök kezelésének érdekességei programozási nyelvekben"-féleséget kell érteni. Az ötletet, hogy egy picit foglalkozzunk a témával két remek könyv ihlette. Ezek kapcsán gondoltam úgy, hogy bizonyos jelenségek és problémák, melyeket majd leírok (és amelyek nem az én agyszüleményeim), minden programozó számára hasznosak lehetnek a jövőben. Elöljáróban annyit, hogy nem igazán szeretem a tömböket. A múltban, amikor még Fortran, Basic vagy Turbo Pascal nyelvek töltötték ki a napjaimat, más lehetőség hiányában én is intenzív tömbhasználó voltam, aztán kb. 15 éve, amikor az első igazi relációs adatbázis közelébe kerültem, teljesen elbűvölt az itt fellelhető adatszerkezetek, adattárolási (meg egyéb) lehetőségek tárháza. Azóta kerülöm a tömböket bár elismerem, néha napján bizony jól jönnek, sok esetben meg nem is lehet meglenni nélkülük. A következőkben elsősorban az általam jobban ismert .NET alapon létező, C# nyelven készített tömbökről beszélek (a többi platformon vagy nyelven elérhető tömböktől ezúton is bocsánatot kérek).
Minden tömb a System.Array absztrakt osztályból származik, melynek direkt őse a System.Object. Ez egyben azt is jelenti, hogy tömb referencia típus, és így az úgynevezett menedzselt halom (managed heap) területen foglal helyet. Alapvetően háromféle tömb létezik: az egy dimenziós (vektor), a több dimenziós (mátrix, kocka, stb.), illetve a szabálytalan (tömböket tartalmazó tömb, vagy hivatalos nevén "jagged") tömb. Minden tömb deklaráció egy hivatkozás (referencia) a hozzá tartozó, adott típusú adatokra. A tömbök elemeire való hivatkozás (tömb index) alapján történik, amely alapértelmezés szerint 0-tól indul, de persze ha úri kedvünk úgy tartja, ettől eltérő is lehet. Példák:

int[] egeszvektor;          
// Deklaráltunk egy hivatkozást egy tömbre
egeszvektor = new int[100]; 
// Létrehoztunk egy 100 elemből álló tömböt.
int[,] egeszmatrix = new int[10, 20];
// Deklaráltunk és létrehoztunk egy 10x20-as mátrixot
int[,,] egeszkocka = new int[5, 4, 3];
// Deklaráltunk és létrehoztunk egy 5x4x3-as kockát
Point[][] polygonok = new Point[3][];
// Deklaráltunk és létrehoztunk egy poligont (jagged array)

A tömböket automatikusan vagy kényszerítve, de át lehet alakítani egyik típusból a másikba. Példák:

FileStream[,] fs = new FileStream[5, 10];
// Létrehozunk egy 5x10-es fájl stream típusú mátrixot
object[,] fso = fs;
// Automatikus típuskonverzióval beletesszük egy object tömbbe
Stream[] st = (Stream[])fso;
// Típuskényszerítést (kézi konverziót) hajtunk végre egy Stream-re

Az Array típusnak számos jellemzője (property) és metódusa van, melyek jól használhatók a munka közben. Példa:

Array.Copy(tomb1, tomb2, tomb1.Lenght);
// Tömb másolása

Ja igen, ez tényleg olyan unalmas, hogy már magam is vattát köpök. Rendben, akkor elemi iskolai magyarázatokból ennyi elég is volt. Nem áll szándékomban programozói tanfolyamot indítani, úgyhogy lépjünk tovább az érdekesebb, főleg nem várt teljesítményproblémákat felvető részek felé.
Az Array.Copy() metódus nem az eszeveszett sebességéről híres, épp ezért megfontolandó, hogy nem érdemesebb-e helyette időnként a System.Buffer.BlockCopy() metódusát használni. Ez, a benne alkalmazott bájt-eltolási módszer miatt lényegesen gyorsabb az előzőleg említett "kollégájánál", azonban csak az egyszerű (primitive) típusú tömbök másolását támogatja, és nem ajánlja fel ugyanazon konverziós lehetőségeket, minta sima Array.Copy(). Elsősorban bájt vagy karaktersorozatokat tartalmazó tömbökhöz célszerű használni. A BlockCopy()-ról részletek itt olvashatók.
Amennyiben igazán biztonságos másolásra vágyunk, akkor a System.Array.ConstrainedCopy() metódus a mi emberünk. Ez ugyanis garantálja, hogy a másolási művelet teljesen szabályos legyen, ellenkező esetben kivételt fog dobni. Sajnos a forrás tömb csak ugyanolyan típusú lehet (vagy ugyanannak a leszármazottja), mint a célként meghatározott tömb. A ConstrainedCopy()-ról részletek itt olvashatók.
A tömbök mindegyike automatikusan (implicit módon) megvalósítja az IEnumerable, ICollection, és IList interfészeket, a velük járó lehetőségekkel együtt. Azonban a nevezett interfészek generikus változatainak a megvalósítását a CLR (Common Language Runtime) csapat nem hajtotta végre, hivatalosan elsősorban a több dimenziós és nem 0 kezdetű tömbök kellemetlenségei miatt. Ugyanakkor egy kis trükkel futás közben mégiscsak belecsempészték a generikus interfészeket, de ezek elmagyarázása sajnos túl sokáig tartana, úgyhogy egyelőre legyen elég annyi, hogy a fentebb említett interfészek generikus változatai nincsenek ugyan, de mégis vannak.
Egy egydimenziós, 0 kezdetű (0 bázisú, vagy 0 kezdő indexet tartalmazó) tömb kezelése lényegesen gyorsabb a nem 0 bázisú és/vagy többdimenziós tömbökhöz képest. Ennek egyik oka az, hogy az egydimenziós, 0 bázisú tömbre külön IL (Intermediate Language) utasítások vannak, úgy mint: newarr, idelem, idelema, stelem. Ezek felhasználásával a JIT fordító képes remekül optimalizálni a műveleteket. Pl.: a 0 bázisú, egydimenziós tömbök eltolását (memóriabeli elhelyezkedésük címét) egyszerű műveletekkel képes kiszámolni, míg a nem 0 bázisú tömböknél viszont különféle osztásokat is kell még végeznie. A másik ok az, hogy a 0 bázisú tömböknél a JIT fordító képes az index tartomány ellenőrzést előre, pl.: még a ciklus végrehajtása előtt elvégezni. Mondanom se kell, hogy ezzel bizony majdhogynem fénysebességre gyorsulhat a művelet. Példa:

int[] a = new int[5];
for (int index = 0; index < a.Length; index++)
{
// Itt valamit csinálni kellene…
}

A ciklus fejben lévő index < a.Length jellemző értékének vizsgálata valójában a háttérben egy metódushívás, ami az "a" tömb hosszát kérdezi le. Ez az információ azonban már ismert a ciklus megkezdése előtt is, így tehát a JIT fordító képes előre megvizsgálni, majd egy munkaváltozóba félretenni ezt az értéket még a végrehajtás előtt azért, hogy a "a.Lenght" hívásra később (a ciklus végrehajtása során) már ne kerüljön sor. Tanúság: ennek a hatására a ciklus végrehajtás bizony sokkal gyorsabb lesz. A másik tanúság az, hogy a programozó ne akarjon "okos" kódot írni, azaz ne akarjon okosabb lenni a JIT fordítónál és látván a helyzetet, előre kiemelni egy változóba az "a.Length" értékét, majd azt beletenni a ciklus fej részébe. Ez, eredményét tekintve persze ugyanolyan jó megoldás, mint amit a JIT fordító választ, csak az a baj, hogy teljesen felesleges, és rontja a kód olvashatóságát (mivel a JIT fordító is megtenné ugyanezt helyettünk). Nagyon fontos, hogy egy programozó tudja, miképp viselkedik az a környezet, ahol tevékenykedik, mert így legalább később egy csomó, csúnyácska megoldást elkerülhet.
Ugyanennél a példánál maradva képes a JIT fordító előre leellenőrizni, hogy lesz-e tömbhatár túllépés vagy sem. Érdekes mi? Egy még meg nem történt dolgot előre látni? Ahh, "akkor ezt itt most, hogy?" (az idézet nem tőlem van). Hát úgy, hogy bizony a JIT mindent előre tud. Először is a tömb kezdő indexe 0, vagyis ez ellenőrizhető. A legmagasabb index vizsgálatra pedig a következő ((a.Length - 1) <= a.GetUpperBound(0)) kifejezés alkalmas. Ez is előre elvégezhető. Márpedig ha ez mind igaz (mármint hogy ha a JIT fordító előre tudja, hogy bizony nem lesz tömbhatár túllépés), akkor a teljes ciklus végrehajtási kódjából kihagyhatja az erre vonatkozó ellenőrzési utasításokat. Ettől kezdve a mi kis ciklusunk hiperűrsebességre kapcsolhat, és olyan gyorsan befejeződik, hogy időnk se lesz rá gondolni többet. A fentebb leírtak is alátámasztják azt a jóslatot, miszerint: a menedzselt, JIT fordítóval generált kódé lesz a jövő. Milyen igaz. Sajnos a nem 0 bázisú és többdimenziós tömböknél a JIT fordító nem képes előre elvégezni a tömbhatár túllépési ellenőrzéseket (legalábbis a .NET 2.0-ig ez így volt), ami azt jelenti, hogy ezek a részek továbbra is a cikluson belül maradnak, vagyis az ellenőrzés a tömbelemre való tényleges hivatkozáskor fog megtörténni. Még további gyorsítási tippek, trükkök is léteznek, de erről majd máskor.

Put About