Tippek a gyűjtemények használatához

1. Gyűjtemények listája

Mint emlékezhet, a Java gyűjteményekkel rendelkezik – egy praktikus eszköz az azonos típusú objektumok tárolására.

Próbáljuk felidézni a főbb gyűjteményhez kapcsolódó felületeket:

Lista , készlet , térkép és sor .

Mint általában, az eszközök nem feltétlenül jók vagy rosszak – az számít, hogy a rendeltetésüknek megfelelően használja-e őket. Ehhez pedig alaposan meg kell értenünk sajátosságaikat, hogy tudjuk, melyik gyűjteményt és mikor használjuk.

1. Lista

Kezdjük a leggyakrabban használt kollekcióval.

Listázzon a lehető legközelebb egy sima régi tömbhöz.

Ez a gyűjtemény lehetővé teszi, hogy kényelmesen tároljuk az azonos típusú objektumok listáját anélkül, hogy magának a gyűjteménynek a mérete miatt kellene aggódnunk, mint ahogyan tömb használata esetén kellene. A gyűjtemény elemei indexen keresztül érhetők el. Ha pontosan tudjuk, hol van egy objektum, és gyakran hozzá kell férnünk anélkül, hogy gyakran kellene elemeket hozzáadnunk vagy eltávolítanunk, a lista ideális.

2. Állítsa be

A készlet teljesen más szerkezetű.

A készlet akkor a legalkalmasabb, ha egyedi tárgyakat kell tárolnunk. Például a szerzők halmaza egy könyvtárban, ahol minden szerző egyedi. De nem mehetünk el, és nem ragadhatunk ki belőle egyetlen konkrét szerzőt sem. A Set segítségével gyorsan ellenőrizhetjük, hogy egy adott szerző jelen van-e a könyvtárunkban, azaz ellenőrizhetjük, hogy van-e egyedi objektum a készletben . A teljes gyűjteményben is iterálhatunk, elérve az egyes elemeket, de ez nem optimális.

Más szóval, a mi könyvtárunkban egy készlet képviselheti az összes egyedi szerző gyűjteményét, így gyorsan ellenőrizhető, hogy jelen van-e egy adott szerző.

3. Térkép

A térkép inkább egy iratszekrényhez hasonlít, ahol minden fájl alá van írva, és egyedi objektumokat vagy teljes struktúrákat tárolhat. A térképet olyan esetekben kell használni, amikor az egyik értékről a másikra leképezést kell fenntartanunk.

A Map esetében ezeket a kapcsolatokat kulcs-érték pároknak nevezzük.

Ezt a struktúrát használhatjuk könyvtárunkban, ha kulcsként szerző objektumokat használunk, értékekként pedig könyvek listáit ( Lista objektumok) használjuk. Így, miután ellenőriztük a készletet , hogy megnézzük, létezik-e szerzői objektum a könyvtárban, ugyanazt a szerzői objektumot használhatjuk arra, hogy lekérjük a könyveinek listáját egy térképről .

4. Sor

A Queue egy olyan gyűjtemény, amely - meglepetés! — egy sor viselkedését valósítja meg. És a sor lehet LIFO (Last In, First Out) vagy FIFO (First In, First Out). Sőt, a sor lehet kétirányú, vagy „kétvégű”.

Ez a struktúra akkor hasznos, ha az osztályhoz hozzáadott objektumokat a beérkezésük sorrendjében kell használni. Például vegyük a könyvtárunkat.

Az újonnan érkező látogatókat felvehetjük egy sorba , és felváltva kiszolgálhatjuk őket, kiadva azokat a könyveket, amelyekért jönnek.

Amint látjuk, ezek a szerkezetek mindegyike jó, ha a rendeltetésének megfelelően használják. Mind a négy gyűjteménytípusnak jó felhasználási lehetőséget találtunk egyetlen könyvtári példában.

2. Bonyolultság

Amint már említettük, a fent vizsgált gyűjtemények interfészek, ami azt jelenti, hogy rendelkezniük kell implementációkkal ahhoz, hogy használni tudjuk őket.

Ahogy a szögek mikroszkóppal történő kalapálása sem a legjobb ötlet, a kollekció minden kivitelezése sem alkalmas minden helyzetre.

A munkához megfelelő szerszám kiválasztásakor általában 2 jellemzőt veszünk figyelembe:

• Mennyire alkalmas a szerszám a feladatra?
• Milyen gyorsan végzi el a munkát?

Sok időt töltöttünk azzal, hogy kitaláljuk, hogyan válasszunk megfelelő szerszámot egy munkához, de a sebessége valami új.

A számítástechnikában az eszköz sebességét gyakran az idő bonyolultságával fejezik ki, és nagy O betűvel jelölik.

Mi a fenét az időbonyolítás?

Egyszerűen fogalmazva, az időbonyolultság azt az időt jelenti, amelyre egy algoritmusnak szüksége van a gyűjteményben egy adott művelet végrehajtásához (elem hozzáadása/eltávolítása, elem keresése).

ArrayList vs LinkedList

Nézzük meg ezt a List interfész két megvalósításával – az ArrayList és a LinkedList segítségével .

A külső megjelenés szempontjából ezekkel a gyűjteményekkel való munka hasonló:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Amint látható, mindkét gyűjteménytípus esetében ugyanúgy néz ki az elemek hozzáadása, lekérése és eltávolítása. Ez azért van, mert ezek a megvalósítások ugyanazon a felületen. De itt véget is érnek a hasonlóságok.

A List interfész eltérő megvalósítása miatt ez a két struktúra más-más műveleteket hatékonyabban hajt végre, mint mások.

Fontolja meg egy elem eltávolítását és hozzáadását.

Ha el kell távolítanunk egy elemet egy ArrayList közepéről , felül kell írnunk a lista bármely részét, amely az eltávolított elem után következik.

Tegyük fel, hogy van egy 5 elemből álló listánk, és el akarjuk távolítani a 3. elemet.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

Ebben az esetben az eltávolítás egy cellát szabadít fel, így a 4. elemet oda kell írnunk, ahol a 3. volt, és az 5. elemet, ahol a 4. volt.

Ez rendkívül hatástalan.

Ugyanez történik, ha egy elemet adunk a lista közepére.

A LinkedList felépítése eltérő. Az elemek hozzáadása vagy eltávolítása gyors, hiszen csak az előző és a következő elemek hivatkozásait kell megváltoztatnunk, így az eltávolítandó objektumot kizárjuk az elemek láncából.

Visszatérve ugyanezen 5 elemből álló lista példájára, a 3. elem eltávolítása után nem kell mást tennünk, mint a 2. elem hivatkozását a következő elemre, a 4. elem hivatkozását pedig az előzőre módosítani.

Amikor egy elemet adunk a listához, ugyanaz a folyamat megy végbe, de fordítva.

Figyeljük meg, mennyivel kevesebb munkát kell végeznünk egy LinkedList- ben , mint egy ArrayList- ben . És ez csak 5 elem. Ha a listánk 100 vagy több elemből állna, a LinkedList fölénye még szembetűnőbbé válna.

De hogyan változik a helyzet, ha index alapján érünk el egy elemet?

Itt minden pont az ellenkezője.

Mivel az ArrayList egy közönséges tömbként van felszerelve, nagyon egyszerű lesz számunkra bármilyen elemet az indexe alapján megszerezni. Egyszerűen mozgatjuk a mutatót egy bizonyos helyre, és megkapjuk az elemet a megfelelő cellából.

De a LinkedList egyszerűen nem működik így. A lista összes elemét végig kell mennünk, hogy megtaláljuk az adott indexű elemet.

Megpróbáljuk mindezt nagy O-val kifejezni?

Kezdjük azzal, hogy egy elemet index alapján érünk el.

Az ArrayListben ez egy lépésben történik, függetlenül attól, hogy az elem hol található a listában. Akár a végén, akár az elején.

Ebben az esetben az időbonyolultság O(1) lesz .

A LinkedListben a szükséges index értékével megegyező számú elemet kell iterálnunk.

Egy ilyen művelet időbonyolultsága O(n) , ahol n a szükséges elem indexe.

Itt látható, hogy a nagy-O zárójelbe tett szám megfelel a végrehajtott műveletek számának.

Shell visszatérünk az eltávolításához és hozzáadásához?

Kezdjük a LinkedList-tel.

Mivel nem kell sok műveletet végrehajtanunk egy elem hozzáadásához vagy eltávolításához, és ennek a műveletnek a sebessége semmilyen módon nem függ attól, hogy az elem hol helyezkedik el, összetettségét O(1)-ként fejezzük ki, és azt mondjuk . állandónak lenni.

Ennek a műveletnek az időbonyolultsága ArrayList esetén szintén O(n) , amit lineáris komplexitásnak nevezünk.

A lineáris bonyolultságú algoritmusoknál a futási idő közvetlenül függ a feldolgozandó elemek számától. Ez az elem pozíciójától is függhet, akár a lista elején, akár a végén található.

Az időbonyolultság logaritmikus is lehet. Ezt O(log n) -ként fejezzük ki .

Példaként vegyünk egy 10 számból álló rendezett TreeSetet . Meg akarjuk találni a 2-es számot.

Mivel a lista rendezett és nem tartalmaz ismétlődéseket, kettéoszthatjuk, és ellenőrizhetjük, hogy melyik fele tartalmazza a kívánt számot, eldobjuk a nem releváns részt, majd ismételjük ezt a folyamatot, amíg el nem érjük a kívánt elemet. Végül a log(n) elemszám feldolgozása után megtaláljuk (vagy nem találjuk) a számot.

Íme egy táblázat, amely összefoglalja a többi gyűjtemény időbeli összetettségét.

Most, hogy van egy táblázatunk, amely a népszerű gyűjtemények időbeli összetettségét mutatja, megválaszolhatjuk azt a kérdést, hogy a sok gyűjtemény közül miért használjuk leggyakrabban az ArrayList -et , a HashSet-et és a HashMap-et .

Egyszerűen arról van szó, hogy a legtöbb feladathoz ezek a leghatékonyabbak :)