Algoritmusok és adatstruktúrák a kezdő dinamikus tömbhöz

Néha a gyűjtemény korlátlan kapacitást és könnyű listát igényel, de állandó hozzáférési idővel egy tetszőleges elemhez, mint egy tömbhöz. Ebben az esetben tömb alapú listát használunk - egy dinamikus tömb (Array List).

Osztály ArrayList

Az ArrayList olyan gyűjtemény, amely megvalósítja az IList interfészt és tömböt használ az elemek tárolására. A hivatkozott listához hasonlóan az ArrayList tetszőleges számú elemet tárolhat (csak a rendelkezésre álló memória mennyisége korlátozza), de egyébként úgy viselkedik, mint egy tömb.

• T (_items) tömb elemek tárolására.
• Az alapértelmezett szerkesztő, amely üres listát hoz létre.
• Olyan konstruktor, amely olyan egész számot vesz fel, amely egy meghatározott kapacitású listát hoz létre. Ne feledje, hogy a lista kapacitása és hossza nem azonos. A gyakorlatban előfordulhat olyan helyzet, amikor egy ilyen tervező lehetővé teszi a felhasználó számára, hogy elkerülje a belső tömb számos kiterjesztését.

Elemek beillesztése

Az elemek dinamikus tömbbe való beillesztése különbözik a linkelt listákba való beszúrástól. Ennek két oka van. Az első: a dinamikus tömb támogatja a tömb középső részébe történő beillesztést, míg a csatolt listát csak a végén vagy az elején lehet beilleszteni. A második: egy elem beillesztése egy összekapcsolt listára mindig állandó időben történik. A dinamikus tömbbe való beillesztés mind O (1), mind O (n) időt vehet igénybe.

A tömb kiterjesztése

Az elemek hozzáadásával a belső tömb túlcsordulhat. Ebben az esetben a következőket kell tennie:

1. Hozzon létre egy nagyobb méretű tömböt.
2. Másolja át az elemeket egy új tömbre.
3. Frissítse a hivatkozást a lista belső tömbjére, hogy az rámutasson az újra.

Most továbbra is választ kell adni arra a kérdésre, hogy milyen méretűnek kell lennie egy új tömbnek. Ezt a dinamikus tömb növekedési stratégiája határozza meg. Két stratégiát fogunk megvizsgálni, és mindkettőnket látni fogjuk, milyen gyorsan nő a tömb, és mennyire csökkenti a teljesítményét a teljesítmény.

Dupla növekedés (Mono és Rotor megközelítés)

Az ArrayList két megvalósítása létezik. A hálózaton megtalálható kód: Mono és Rotor. Mindkettő egyszerű algoritmust használ a tömb méretének növelésére, szükség esetén megduplázva. Ha a tömb kezdeti mérete nulla, az új tömb 16 elemet tartalmaz:

Ez az algoritmus kevesebb memóriaelosztást tesz lehetővé, de többet költ, mint a Java-ban elfogadott verzió. Más szavakkal, gyakrabban fordul elő olyan esetek, amikor egy állandó időt több memória használatával költenek. Kevésbé gyakori lesz az új tömb és másoló elemek létrehozása.

Lassú növekedés (Java-megközelítés)

A Java hasonló megközelítést alkalmaz, de a tömb lassul. Az új tömb méretét a következőképpen határozzuk meg:

Ezzel az algoritmussal kevesebb memóriát használ.

Nézzük meg a 200 000 elemből álló tömbök növekedési görbéit a két stratégia segítségével:

Amint azt a grafikonból láthatjuk, ahhoz, hogy a határt 200 000 elemre át lehessen átkapcsolni, a tömb megduplázására szolgáló változat 19 memóriaelosztási és másolási műveletet igényelt, míg a Java verzió 30 műveletet igényelt.

Melyik stratégia jobb? Nincs helyes és helytelen válasz erre a kérdésre. A duplázáskor kevesebb beillesztési műveletet fogunk végrehajtani O (n) értékkel, de több memóriahasználatot. Lassabb növekedés esetén kevesebb memóriát fognak használni. Általánosságban mindkét lehetőség elfogadható. Ha az alkalmazásnak speciális követelményei vannak, előfordulhat, hogy egy vagy másik bővítési stratégiát kell végrehajtania. Mindenesetre a dinamikus tömb külső viselkedése nem változik.

Végrehajtásunk kettős (Mono / Rotor megközelítés)

Beszúrás módja

• Viselkedés: hozzáad egy elemet a megadott indexhez. Ha az index egyenlő vagy nagyobb az elemek számánál, kivételt vet ki.
• Komplexitás: O (n).

Egy adott indexbe való beszúrása minden elem elcserélését igényli, kezdve ezzel az indexszel, egy pozícióval jobbra. Ha a belső tömb tele van, a betét növeli annak méretét.

A következő példa öt pozícióval rendelkező tömböt ad, amelyek közül négy töltődik be. A "3" érték be van helyezve a harmadik pozícióba (2. index):

Array elemek áthelyezése előtt

Array az elemeltolás után

Array, miután egy elemet üres helyre helyezett

• Viselkedés: hozzáad egy elemet a lista végéhez.
• Komplexitás: O (1), ha több szabad hely maradt; O (n), ha ki kell bővíteni a tömböt.

Elemek törlése

Az RemoveAt módszer

• Viselkedés: törli a megadott indexben található elemet.
• Komplexitás: O (n).

Az elem törlése index szerint fordított művelet. A megadott elem törlődik, és a fennmaradó elemek egy pozícióban balra vannak mozgatva.

Array, mielőtt eltávolítanánk egy elemet

Array egy elem eltávolítása után

Array az elemeltolás után

Az eltávolítási módszer

• Viselkedés: eltávolítja az első elemet, amelynek értéke megegyezik az adott értékkel. Eredmény igaz. ha az elem törölve vagy hamis.
• Komplexitás: O (n).

Elemek elérése

IndexOf módszer

• Viselkedés: az első elem indexét adja vissza, amelynek értéke megegyezik a megadott értékkel, vagy -1, ha nincs ilyen érték.
• Komplexitás: O (n).

Elem módszer

• Viselkedés: lehetővé teszi az index értékének olvasását vagy módosítását.
• Komplexitás: O (1).

Módszert tartalmaz

• Viselkedés: igaz értéket ad vissza. ha az érték szerepel a listán, és hamis.
• Komplexitás: O (n).

A GetEnumerator módszer

• Viselkedés: visszatér egy iterátor IE számlálóhoz A lista összes elemének átadása.
• Összetettség: Egy iterátor megszerzése O (1), a lista áthaladása O (n).

Figyeljük meg, hogy nem lehet csak átkelni a _items tömbön. mivel olyan cellákat tartalmaz, amelyek még nem töltődnek be, ezért korlátozzuk azt a tartományt, amellyel az elemek számát meg fogjuk ismételni.

Egyéb IList módszerek

Tiszta módszer

• Viselkedés: eltávolítja az összes elemet a listából.
• Komplexitás: O (1).

Két lehetőség van a Clear módszer végrehajtására. Az első esetben új üres tömb jön létre, a második esetben csak a gráf mező van nullázva. Végrehajtásunk során új tömb nulla hosszúságú lesz.

• Viselkedés: minden elemet átmásol a belső tömbről a megadottra, a megadott indexből kiindulva.
• Komplexitás: O (n).

Metódusszám

• Viselkedés: a gyűjtemény aktuális számát adja vissza. Ha a lista üres, akkor 0 értéket ad.
• Komplexitás: O (1).

A gráf egy automatikus növekményes mező, amelyben egy privát szetter és egy public getter található. A felhasználó csak olvassa el, és módosíthatja az elemek hozzáadásának és eltávolításának módját.

IsReadOnly módszer

• Viselkedés: mindig hamis. mivel gyűjteményünk változó.
• Komplexitás: O (1).

Folytatni kell

Ez a dinamikus tömbök elemzését vonja le. Legközelebb továbbhaladunk a kötegekre és sorokra.