Bevezetés:
Talán már tisztában van azzal, hogy az algoritmusok és az adatstruktúrák a szoftverfejlesztők alapvető készségeinek számítanak. Hasznos az adattudományi területen?
Az olyan adattudományi területek, mint az adatelemzők, adatmérnökök és adattudósok, nagy mennyiségű adattal dolgoznak nap mint nap. Az adatok kinyerése, átalakítása és betöltése (ETL) mindennapi tevékenységünk részévé válik. Hogyan segíthetnek nekünk az adatstruktúrák ilyen esetekben?
Adatszerkezetek:
A kód megírásának módja közvetlen hatással van az erőforrások felhasználására, különös tekintettel arra, hogy a mai világban a legtöbb dolgot felhő alapú szolgáltatásokon, például az AWS-en telepítik. Nemcsak a kódunk hatékony megírása befolyásolja a szolgáltatások igénybevételének költségeit, hanem közvetlenül megfelel a programunk végrehajtásához szükséges időnek is. Az adatszerkezeteket tekintve ez egy Big O jelöléssel ábrázolható. Ez egy módszer egy algoritmus időbeli összetettségének kifejezésére. Az időbonyolultsággal együtt jár a térbonyolultság is, amely a kódrészlet által végrehajtott térkihasználás mértéke.
Üzleti szempontból a költségek alacsonyan tartása közvetlenül összefügg a profit maximalizálásával, ezért fontos a megfelelő adatszerkezetek használata, ahol csak lehetséges.
A következő részben az adatszerkezet néhány terminológiáján fogok végigvezetni, a következő cikkekben pedig néhány példával mélyrehatóan belemerülhetünk ebbe.
Bonyolultsági elemzés:
A naponta előállított adatok egyre növekvő mérete miatt elengedhetetlen az adatok megfelelő feldolgozása, amely a burkolat alatt lévő számítások ismeretében elemezhető.
Háromféle elemzés végezhető.
Legjobb eset:-
Ez az az eset, amikor a programod a legkevesebb időt vagy helyet foglal el
Átlagos eset:-
Ez az átlagos eset segít megérteni a teljesítményt, amely a legjobb és a legrosszabb eset között van.
Legrosszabb eset:-
Ebben az esetben annak a bemenetnek az algoritmusát elemezzük, amelynél a legrosszabbul teljesít
A következő jelölések segítenek a fenti esetek elemzésében: -
Főleg háromféle jelölés létezik, amelyek alapján egy kód bonyolultságát megítélhetjük.
1. Théta jelölés (θ):-
Az esetek átlagos összetettségének megadására szolgál
2. Omega-jelölés (Ω):-
A legjobb eset összetettségének meghatározására szolgál
3. Big-O jelölés (Ο): –
A legrosszabb eset bonyolultságának meghatározására szolgál. Aggódunk a legrosszabb eset miatt, hogy tudjuk, milyen rossz lehet a legrosszabb eset.
Különböző nagy O futási idők: -
Itt ismertetjük az algoritmusok leggyakoribb futási idejét.
O(n):- Lineáris időbonyolultság
O(log n):- Logaritmikus időbonyolultság
O(n²):- Olyan algoritmust jelöl, amelynek növekedése megduplázódik egyetlen bemeneti adat hozzáadásával
Néhány adatstruktúra és algoritmus áttekintése: -
- Tömbök:
A tömbök és listák egyszerre több elem tárolására szolgálnak.
Gyakorlati alkalmazások:
- Online jegyértékesítő rendszer.
2. Hivatkozott listák:
Egy linkelt listában az elemek linkek segítségével kapcsolódnak egymáshoz, amelyek gyakorlatilag az egyes elemek memóriacímét jelentik.
Gyakorlati alkalmazások:
- A zenelejátszóban a dalok a következő és az előző dalhoz kapcsolódnak.
- Többjátékos játék
3. Halmok:
A verem egy olyan adatstruktúra, amely a Last In First Out (LIFO) függvényt követi az elemek tárolására, azaz az utoljára beírt elemek kerülnek ki először.
Gyakorlati alkalmazások:
- Műveletek visszavonása / újraindítása a Wordben.
- A Java Virtual Machine (JVM) egy veremet használ. A szintaxisok elemzése verem segítségével történik.
4. Várólisták:
A Queue egy olyan adatstruktúra, amely a First In First Out (FIFO) parancsot követi az elemek tárolására. Mert pl. Filmsor, amelyben az elsőként érkező személyt szolgálják ki először.
Gyakorlati alkalmazások:
- CPU feladatütemezés
- Az egyedi megosztott erőforrások, például a nyomtatók a Queue funkciót használják a kérések kiszolgálására.
- Az Ügyfélszolgálati Képviseleti Rendszer a kérések szekvenciális kiszolgálásához egy sort használ.
5. Fákra
A fák egy nemlineáris adatstruktúra formája, amelyet hierarchikusan tárolnak.
Gyakorlati alkalmazások:
- A Decision Trees fa adatstruktúrát használ
- Elemzők
6. Térképek és kivonatolás:
Ezek az adatstruktúrák indexelést követnek. Alapvetően a hash függvény kiszámítja az indexet, hogy a kulcsérték segítségével egy vödörben tárolja azt.
Gyakorlati alkalmazások:
- Valósítson meg egy szótárt
- Adatbázis indexelés
- Fordítóműveletek
- Kriptográfia
7. Próbálkozásokra
A Trie adatstruktúra hasonló a fa adatstruktúrához. Minden csomópont tárol valamilyen értéket, például egy egyedi betűt.
Praktikus alkalmazások:
- Automatikus javítás
- E-mail automatikus kiegészítése
- Böngészőelőzmények automatikus kiegészítése
Rendezési algoritmusok: -
1. Buborékos rendezés:
A buborékos rendezés a szomszédos elemek összehasonlításával és felcserélésével működik, amíg a végeredmény a megfelelő sorrendbe nem kerül.
2. Összevonási rendezésre
Az egyesítési rendezés a bemenetet fele méretű alrészekre osztja. Az egyes alrészeket külön-külön dolgozzák fel, és végül újra egyesítik, hogy megkapják a végső eredményeket. Az összevont rendezés időbonyolultsága jobb, mint a buborékos rendezés, bár a térkomplexitás rosszabb, mint a buborékos rendezés.
3. Gyors rendezésre
A gyors rendezési algoritmus elsősorban pivot segítségével működik. A rendszer kiválasztja a pivotot, majd az adatokat az adott pivot elem körül particionálja. Addig folytatjuk a forgatást, amíg meg nem kapjuk a végső rendezett eredményeket.
4. Halomrendezésre
Ez egy helyben történő rendezési algoritmus. Egy tömböt bináris faként kezel, és a legnagyobb elemet a végére mozgatja, amíg meg nem kapjuk a rendezett eredményt.
Speciális algoritmusok: -
Bináris keresés
A bináris keresés segít egy elem megtalálásában egy rendezett listában. Folyamatosan felosztja a bemenetet, amíg meg nem találjuk a végeredményt. Ennek a keresésnek az időbonyolultsága O(log n).
2. Mohó algoritmusokban
A mohó algoritmusok olyan megközelítésen dolgoznak, amely a jelenlegi szakasz legjobb eredményeit veszi figyelembe. Az eredményeket darabonként építi fel, mindig az aktuális szakasz legjobbját figyelembe véve. Ennek az az egyik hátránya, hogy bár a legjobb eredményeket egyenként választják ki, az általános megoldás nem biztos, hogy optimális.
3. Oszd meg és uralkodj algoritmusok:
Az Oszd meg és uralkodj algoritmusokban a probléma részproblémákra, azaz egy adott probléma példányainak részeire való felosztására összpontosítunk. Az oszd meg és uralkodj egy példa a bináris keresési és egyesítő rendezési algoritmusok. A részproblémák függetlenek egymástól.
4. Dinamikus programozás:
A Dynamic Programming az Oszd meg és uralkodj kiterjesztése, ahol olyan módszereket használhatunk, mint például a memorizálás. A részproblémák ebben az esetben az Oszd meg és uralkodj, ellentétben egymással.
5. Grafikonalgoritmusok:
A gráf csomópontokból és élekből áll. Két csomópont közötti új relációhoz élek kötik össze őket. Valós példa erre a Meta(Facebook), ahol minden felhasználó egy csomópontnak tekinthető. Ha valakivel új barátságba kerülsz, új csomóponti kapcsolat jön létre közted és a másik felhasználó között.
6. A*
Az A* algoritmus segít megtalálni a legrövidebb távolságot az aktuális csomópont és a cél között. A mohó algoritmusokkal ellentétben ez nem tekinti a legjobb megoldást az aktuális lépésben, hanem átfogóan optimális megoldást keres.
Ebben a cikkben néhány alapvető adatstruktúra áttekintését tárgyaltuk valós példákkal. Remélem hasznosnak találja a cikket. Ha bármilyen kérdése van, nyugodtan tegye fel őket az alábbi megjegyzés részben. Remélem szép napod van előtted :)
