Uzziniet savus kodēšanas pamatus: galvenās atšķirības starp kopām un masīviem

Jautājums, ko daudz saņemu no saviem CS studentiem The Forge, ir iemesls, kāpēc intervijas problēmās bieži izmantoju komplektus, nevis vienkāršus vecos masīvus.

Lai atbildētu uz šo jautājumu, mums ir jāsaprot būtiskās atšķirības starp kopu un masīvu.

Ja esat vizuāli izglītojies un dodat priekšroku video skaidrojumam, šeit ir 3 minūšu ilgs video, kurā paskaidrota atbilde (lai arī mazākā mērā).

Masīvi bija viena no pirmajām datu struktūrām, ko iemācījos izmantot.

Tie ir ne tikai fundamentāla datu struktūra, ko izmanto gandrīz katrā kodēšanas lietojumprogrammā, bet arī diezgan viegli saprotami.

Tikai vēlāk programmatūras karjeras laikā es iepazinos ar masīva dīvaino, bet maģisko brālēnu:

Komplekts.

Komplekti ir kā masīvi ... izņemot to, ka tie nav.

Atgādināsim sev ātri par to, kā darbojas masīvs

Masīvi:

  • Tiek pasūtīti
  • Indeksi sākas ar 0
  • Var saturēt elementu dublikātus
  • Veicot elementa meklēšanu, ir jābūt O (n) uzmeklēšanas laikam

Tomēr komplekti izturas mazliet savādāk

Komplekti:

  • Nav pasūtīti (gandrīz visās valodās)
  • Ir jaukti indeksi
  • Var NESATUR elementu dublikātus
  • Ir O (1) uzmeklēšanas laiks , meklējot elementu

Apskatīsim padziļinātāk.

1. Iestata ievietošanu ar jaukšanu

Komplektā esošie elementi tiek glabāti diezgan atšķirīgi nekā masīva.

Veids, kā komplekts glabā savus elementus, ir Hašings.

Pieņemsim, ka vēlaties saglabāt burtu “A” komplektā un masīvā.

Masīvs vienkārši atrastu nākamo pieejamo indeksu, ja vien nav norādīts citādi, un ievietotu elementu šajā indeksā.

Tomēr ar jaukšanu viss izskatās mazliet savādāk.

Kā darbojas jaukšana

Jaukšana ir ievades (x) uzņemšana, tās sagrozīšana ar noteiktu hash funkciju (h) un gala izejas iegūšana (y).

Būtībā h (x) = (y)

Izskatās mazliet mulsinoši, vai ne?

Neuztraucieties! Tam vajadzētu noskaidrot lietas.

Vienkāršs jaukšanas funkcijas (h) piemērs varētu būt “asdf” pievienošana ievades beigām (x).

Ja (x) ir “A” un pievienojot “asdf” ir (h), izeja (y) vienkārši ir šāda:

“A” + “asdf” → “Aasdf”

Tātad “Aasdf” būtu mūsu (y).

Tātad, kā komplekts izmanto hashingu?

Komplekts izmanto jaukšanu, lai izlemtu, kur glabāt ievadi (x).

Īsāk sakot, kopa ņem jūsu ievadi, jauc to un uzglabā indeksā, kas atbilst jauktai ievadei, AKA izejai (y).

Tas ir iemesls, kāpēc vairumā valodu kopas netiek sakārtotas.

Masīvu indeksēšana ir vienkārša, no 0 līdz n, lai jūs varētu viegli atcerēties, kas notiks tālāk.

Bet, ņemot vērā sarežģītās jaucējfunkcijas, kuras lielākā daļa kompilatoru izmanto, secību, kādā elementi tika ievietoti, nevar atrast, ja vien neturat sekundāro indeksēšanas mehānismu.

2. Komplekti nevar saturēt dublikātus

Pareizi!

Komplektā var būt tikai unikāli elementi.

Pretēji tam, kā izklausās, tas tiešām var būt ļoti noderīgs daudzās situācijās, tostarp Google intervijas jautājumos.

Kāpēc tā dara, jūs jautājat?

Nu jaukšanas dēļ!

Tā kā mana jaukšanas funkcija (h) paliks konsekventa, kamēr mana programma darbojas, ievadot to pašu (x), vienmēr iegūsiet to pašu (y).

Tas nozīmē, ka, ja es mēģinātu ievietot otro “A”, mana jaukšanas funkcija izdotu to pašu adresi kā pirmā “A”, un tā to vienkārši pārrakstītu!

Izmantojot masīvu, tas vienkārši pievienotu otro “A” nākamajam pieejamajam indeksam.

3. Komplektiem ir O (1) uzmeklēšanas laiks

Pieņemsim, ka jums ir n elementu masīvs , kur n ir liels skaitlis, un jūs vēlējāties redzēt, vai šajā masīvā pastāv “A”.

Nu, sliktākajā gadījumā “A” nepastāv.

Un, lai to uzzinātu, jums vajadzētu atkārtot visus šos elementus n !

Tas piešķir masīvam O (n) laika sarežģītību, meklējot elementu.

Ar komplektu mēs varam ietaupīt daudz laika

Ja mēs vēlējāmies noskaidrot, vai elements mūsu komplektā pastāv, mums atliek tikai jaukt šo elementu un pārbaudīt indeksu!

Atcerieties: Indekss, kurā tiek glabāts elements, ir saistīts ar pašu elementu.

Tāpēc, ja mēs gribētu redzēt, vai mūsu komplektā pastāv “A”, mums tas vienkārši ir jāmaisa (+ “asdf”) un jāpārbauda šis indekss!

Tā kā šim procesam vienmēr būs nepieciešams nemainīgs operāciju apjoms, neatkarīgi no tā, cik liels ir kopums, tam ir nemainīga laika sarežģītība.

Tas nozīmē, ka kopai ir O (1) sarežģītība, meklējot elementu ... Kas ir milzīgs uzlabojums!

Vai varat iedomāties kādas situācijas, kurās tas būtu noderīgi?

Ja nevarat, pārbaudiet šo Google intervijas jautājumu, kurā kopa izšķir visu!

Paldies, ka lasījāt!

.a

PS - Lai iegūtu vairāk datu struktūru un algoritmu apmācības un intervijas sagatavošanas darbus, skatiet vietni www.TheForge.ca!

Mēs palīdzam studentiem un jaunajiem skolēniem nosūtīt sapņu programmatūras darbu!