Ismerje meg a kódolás alapjait: a halmazok és tömbök közötti fő különbségeket

A The Forge CS hallgatóimtól sokat kaptam egy kérdést, hogy miért használok készleteket sima régi tömbök helyett interjúproblémákban.

A kérdés megválaszolásához meg kell értenünk egy halmaz és egy tömb közötti alapvető különbségeket.

Ha vizuális tanuló vagy, és inkább egy videomagyarázatot szeretnél, íme egy 3 perces videó, amely elmagyarázza a választ (bár kisebb mélységben).

A tömbök voltak az első adatstruktúrák, amelyek használatát megtanultam.

Nemcsak alapvető adatstruktúra, amelyet szinte minden kódoló alkalmazásban használnak, de meglehetősen könnyen érthetők.

Csak később, szoftveres karrierem során ismertem meg a tömb furcsa, de varázslatos unokatestvérét:

A készlet.

A halmazok olyanok, mint a tömbök ... csakhogy nem.

Gyorsan emlékeztessük magunkat egy tömb működésére

Tömbök:

  • Rendeltek
  • Az indexek 0-tól kezdődnek
  • Ismétlődő elemeket tartalmazhat
  • Legyen O (n) keresési ideje, amikor elemre keres

A készletek azonban kissé másként viselkednek

Készletek:

  • Vannak rendezetlen (szinte minden nyelven)
  • Van kivonatolt indexek
  • Lehet nem tartalmazhat ismétlődő elemeket
  • Legyen O (1) keresési ideje elem keresésekor

Vizsgáljuk meg alaposabban.

1. Beállítja a beszúrást hasheléssel

A halmaz elemeit egészen másképpen tárolják, mint egy tömbét.

Ahogy egy készlet tárolja az elemeit, az Hashing.

Tegyük fel, hogy az „A” karaktert egy halmazban és egy tömbben szeretné tárolni.

A tömb egyszerűen megtalálja a következő elérhető indexet, hacsak másképp nincs meghatározva, és az elemet abba az indexbe helyezi.

A hasítással azonban a dolgok kissé másképp néznek ki.

Hogyan működik a hashing

A hashelés az (x) bemenet befogadása , egy bizonyos hash függvény (h) torzítása és a végső kimenet (y) megszerzése.

Alapvetően h (x) = (y)

Kicsit zavarónak tűnik?

Ne aggódj! Ennek tisztáznia kell a dolgokat.

A hash függvény (h) egyszerű példája lehet az „asdf” hozzáfűzése a bemenet végéhez (x).

Ha (x) „A” és az „asdf” csatolása (h), akkor az (y) kimenet egyszerűen a következő lenne:

„A” + „asdf” → „Aasdf”

Tehát az „Aasdf” lenne a mi (y).

Szóval, hogyan használja egy készlet a hashst?

Egy készlet kivonatolással dönti el, hogy hol tárolja a bevitelt (x).

Dióhéjban egy halmaz veszi a bevitelt, kivonja és tárolja a kivonatolt bemenetnek megfelelő indexben, az AKA a kimenetet (y).

Ez az oka annak, hogy a halmazok a legtöbb nyelvben rendezetlenek.

A tömb indexelése egyszerű, 0-tól n-ig, így könnyen megjegyezheti, mi következik.

De a legtöbb fordító által használt összetett kivonatolási funkciók mellett az elemek beillesztési sorrendje csak akkor érhető el, ha megtartja a másodlagos indexelési mechanizmust.

2. A készletek nem tartalmazhatnak másolatokat

Úgy van!

Egy készlet csak egyedi elemeket tartalmazhat.

A hangzással ellentétben ez valóban nagyon hasznos lehet sok helyzetben, ideértve a Google Interjúkérdéseket is.

Miért teszi ezt, kérdezed?

Nos, a hashelés miatt!

Mivel a hash függvényem (h) konzisztens marad a program futása közben, ugyanazt az (x) beírása mindig ugyanazt (y) fogja kapni.

Ez azt jelenti, hogy ha megpróbálok beilleszteni egy második „A” -t, akkor a kivonatolási funkcióm ugyanazt a címet adja ki, mint az első „A”, és egyszerűen felülírja!

Tömbbel egyszerűen hozzáfűzi a második „A” -t a következő elérhető indexhez.

3. A halmazok O (1) keresési idővel rendelkeznek

Tegyük fel, hogy van egy n elemből álló tömbje , ahol n nagy szám, és meg akarta tudni, hogy létezik-e „A” abban a tömbben.

Nos, a legrosszabb esetben az „A” nem létezik.

És hogy ezt megtudja, át kell ismételnie az összes n elemet!

Ez egy tömbnek O (n) időbeli összetettségét adja, amikor egy elemet kell megkeresni.

Nagyon sok időt spórolhatunk egy szettel

Ha meg akartuk találni, hogy létezik-e elem a készletünkben, akkor csak annyit kell tennünk, hogy kivonatoljuk ezt az elemet és ellenőrizzük az indexet!

Ne feledje: Az index, amelyben egy elem tárolódik, magához az elemhez kapcsolódik.

Ezért, ha azt szeretnénk megtudni, hogy létezik-e „A” a készletünkben, akkor azt csak el kell hasholnunk (+ „asdf”), és ellenőriznünk kell ezt az indexet!

Mivel ez a folyamat mindig állandó mennyiségű műveletet fog végrehajtani, függetlenül attól, hogy mekkora a készlet, állandóan összetett az idő.

Ez azt jelenti, hogy egy halmaz időbeli összetettsége O (1), amikor egy elemet kell megkeresni ... Ami óriási előrelépés!

Gondolna valamilyen helyzetre, ahol ez hasznos?

Ha nem tudod, nézd meg ezt a Google interjúkérdést, ahol egy készlet minden különbséget jelent!

Köszönöm, hogy elolvasta!

.a

PS - További adatstruktúrákról és algoritmusokról szóló oktatóanyagokért és az interjú előkészítéséért keresse fel a www.TheForge.ca oldalt!

Segítünk a diákoknak és az új évfolyamoknak álmaik szoftveres munkájánál!