Izbira prave podatkovne strukture lahko naredi vaš program učinkovitejši. Tukaj je vodnik, ki vam bo pomagal narediti pravo izbiro.

Izbira najboljše podatkovne strukture za vaše cilje je lahko izziv z več razpoložljivimi možnostmi. Pri izbiri podatkovne strukture upoštevajte podatke, s katerimi boste imeli opravka, operacije, ki jih je treba izvesti na podatkih, in okolje, v katerem se bo izvajala vaša aplikacija.

Razumejte svoje podatke

Razumevanje podatkov, s katerimi boste imeli opravka, je ključnega pomena, preden izberete strukturo podatkov. Skupne podatkovne strukture ki delujejo z različnimi vrstami podatkov, vključujejo polja, povezane sezname, drevesa, grafe in zgoščene tabele.

Na primer, ko morate naključno dostopati do elementov svojih podatkov, so polja morda najboljša izbira. V primeru, da morate nenehno dodajati ali brisati elemente s seznama in se lahko spremeni tudi velikost seznama, so lahko povezani seznami še posebej uporabni.

Kadar morate učinkovito shraniti več ravni podatkov, kot so strukture zapisa, in izvajati operacije, kot sta iskanje in razvrščanje, so drevesa uporabna.

instagram viewer

Ko morate opisati interakcije med entitetami, kot so tiste v družabnih omrežjih, in izvajati operacije, kot sta najkrajša pot in povezljivost, so prednostni grafi. Zgoščevalne tabele so v pomoč pri hitrem iskanju ključev.

Razmislite o operacijah, ki jih je treba izvesti na podatkih

Pri izbiri podatkovne strukture morate upoštevati tudi operacije, ki jih boste izvajali s podatki. Različne podatkovne strukture optimizirajo številna dejanja, kot so razvrščanje, iskanje, vstavljanje in brisanje.

Na primer, povezani seznami so boljši za dejanja, kot sta vstavljanje in brisanje, vendar so binarna drevesa najboljša za iskanje in razvrščanje. Zgoščevalna tabela je lahko najboljša izbira, če vaša aplikacija zahteva hkratno vstavljanje in iskanje.

Ocenite okolje

Ko razmišljate o strukturi podatkov, morate oceniti okolje, v katerem se bo aplikacija izvajala. Okolje vpliva na to, kako dobro in kako hitro so dostopne podatkovne strukture.

Pri ocenjevanju svojega trenutnega stanja upoštevajte naslednje dejavnike:

  1. Procesna moč: Izberite podatkovne strukture za svoje aplikacije, ki dobro delujejo na osebnih računalnikih z malo procesorske moči, medtem ko delujejo na platformi. Enostavnejše podatkovne strukture, kot so nizi, bi lahko bile na primer primernejše od dreves ali grafov.
  2. Sočasnost: Izbrati bi morali podatkovno strukturo, varno za niti, ki lahko obravnava hkratni dostop brez poškodb podatkov; če vaša aplikacija deluje v sočasnem okolju, kjer več niti ali procesov istočasno dostopa do strukture podatkov. V tem primeru podatkovne strukture brez zaklepanja, kot je ConcurrentLinkedQueue in ConcurrentHashMap morda primernejši od tradicionalnih, kot je ArrayListand HashMap.
  3. Zakasnitev omrežja: Če vaša aplikacija zahteva prenos podatkov prek omrežja, morate pri odločanju o najboljši podatkovni strukturi upoštevati omrežno zakasnitev. V takšnih situacijah lahko uporaba podatkovne strukture, ki omejuje omrežne klice ali zmanjša količino prenosa podatkov, pomaga izboljšati izvajanje.

Skupne podatkovne strukture in primeri njihove uporabe

Tukaj je povzetek več priljubljenih podatkovnih struktur in njihove uporabe.

  1. Nizi: To je preprosta in učinkovita podatkovna struktura, ki lahko vsebuje vrsto elementov iste podatkovne vrste s fiksno velikostjo. Za pravilno delovanje potrebujejo hiter, neposreden dostop do določenih predmetov prek indeksa.
  2. Povezani seznami: Povezani seznami so sestavljeni iz vozlišč, ki vsebujejo element in sklic na naslednje vozlišče in/ali prejšnje vozlišče. Zaradi učinkovitega delovanja so povezani seznami najprimernejši v situacijah, kjer je potrebno pogosto vstavljanje ali brisanje elementov. Vendar je dostop do posameznih elementov po indeksu v povezanih seznamih počasnejši v primerjavi z nizi.
  3. Čakalne vrste in skladi: skladi se držijo pravila LIFO (Last-In-First-Out), kjer je zadnji vstavljeni element prvi odstranjen. Čakalne vrste so urejene po načelu FIFO (First-In-First-Out). kjer je prvi dodan element tudi prvi izbrisani.
  4. Zgoščevalne tabele: Zgoščevalne tabele so oblika podatkovne strukture, ki vsebuje pare ključ-vrednost. Najboljša rešitev je uporaba zgoščenih tabel, kadar je število komponent nepredvidljivo in potrebujete hiter dostop do vrednosti po ključu.
  5. Drevesa: Drevesa so hierarhične podatkovne strukture, ki lahko shranijo skupino elementov v hierarhiji. Najboljše uporabe za binarna iskalna drevesa so v hierarhičnih podatkovnih strukturah, kjer lahko razmerja med podatkovnimi postavkami predstavljajo drevesno strukturo.

Izbira prave podatkovne strukture

Preden izberete podatkovno strukturo, razmislite o podatkih, obveznostih in okolju vaše aplikacije. Pri izbiri upoštevajte naslednje elemente:

  1. Časovna zapletenost: Na delovanje vaše aplikacije lahko znatno vpliva časovna kompleksnost vaše strukture podatkov. Če vaša aplikacija zahteva pogoste operacije iskanja ali priklica, uporabite podatkovno strukturo z zmanjšano časovno kompleksnostjo, kot je zgoščena tabela.
  2. Kompleksnost prostora: Kompleksnost prostora podatkovne strukture je še en pomemben vidik. Če vaša aplikacija zahteva veliko pomnilnika, izberite podatkovno strukturo z manj prostorsko kompleksnostjo, kot je matrika. Če prostor ni zaskrbljujoč, lahko uporabite podatkovno strukturo z večjo kompleksnostjo prostora, kot je drevo.
  3. Branje vs. Pisanje operacij: Če vaša aplikacija uporablja veliko zapisovalnih operacij, izberite podatkovno strukturo s hitrejšim delovanjem vstavljanja, kot je zgoščena tabela. Če vaša aplikacija zahteva veliko bralnih operacij, izberite podatkovno strukturo s hitrejšo hitrostjo iskanja, kot je binarno iskalno drevo.
  4. Vrsta podatkov: Podatki, s katerimi imate opravka, lahko vplivajo tudi na izbrano strukturo podatkov. Če so vaši podatki hierarhični, lahko na primer uporabite drevesno strukturo podatkov. Če imate preproste podatke, do katerih je treba dostopati naključno, je lahko izbira podatkovne strukture, ki temelji na nizu, najboljša možnost.
  5. Razpoložljive knjižnice: Razmislite o knjižnicah, ki so zlahka dostopne za podatkovno strukturo, ki jo razmišljate. Lahko bi bilo lažje izvajati in vzdrževati, če ima vaš programski jezik vgrajene knjižnice, ki so na voljo za določeno strukturo podatkov.

Naslednji primer Pythona prikazuje, kako izbrati najboljšo strukturo podatkov za določen primer uporabe.

Razmislite o primeru, ko razvijate aplikacijo datotečnega sistema, ki mora shranjevati in pridobivati ​​datoteke v hierarhiji. Izbrati morate podatkovno strukturo, ki lahko učinkovito predstavlja to hierarhično strukturo in hitro izvaja operacije, kot so iskanje, vstavljanje in brisanje.

Morda bi bilo dobro uporabiti drevesno podatkovno strukturo, kot je binarno iskanje ali B-drevo. Če je število vnosov v vsakem imeniku relativno majhno in drevo ni zelo globoko, bi binarno iskalno drevo dobro delovalo. B-drevo bi bilo primernejše za večje število datotek in globlje strukture imenikov.

Spodaj je primer binarnega iskalnega drevesa v Pythonu.

razredVozlišče:
def__v__(jaz, vrednost):
 self.value = vrednost
 self.left_child = Noben
 self.right_child = Noben


razredBinarnoIskalnoDrevo:


def__v__(sebe):
 self.root = Noben
defvstavi(jaz, vrednost):


če self.root jeNoben:
 self.root = Vozlišče (vrednost)


drugače:
 self._insert (vrednost, self.root) 
def_vstavi(jaz, vrednost, trenutno_vozlišče):


če vrednost < trenutno_vozlišče.vrednost:
če trenutno_vozlišče.levi_otrok jeNoben:
 current_node.left_child = Vozlišče (vrednost)


drugače:
 self._insert (vrednost, current_node.left_child)
elif vrednost > trenutno_vozlišče.vrednost:
če trenutno_vozlišče.desni_otrok jeNoben:
 current_node.right_child = Vozlišče (vrednost)
drugače:
 self._insert (vrednost, current_node.right_child)


drugače:
 natisni("Vrednost že obstaja v drevesu.")
defIskanje(jaz, vrednost):
če self.root jeneNoben:
vrnitev self._search (vrednost, self.root)


drugače:
vrnitevFalse
def_Iskanje(jaz, vrednost, trenutno_vozlišče):


če vrednost == trenutno_vozlišče.vrednost:
vrnitevPrav


elif vrednost < trenutno_vozlišče.vrednost in trenutno_vozlišče.levi_otrok jeneNoben:
vrnitev self._search (vrednost, current_node.left_child)


elif vrednost > trenutno_vozlišče.vrednost in trenutno_vozlišče.desni_otrok jeneNoben:
vrnitev self._search (vrednost, current_node.right_child)
drugače:
vrnitevFalse

V tej izvedbi sestavite dva razreda: a BinarnoIskalnoDrevo razred, ki upravlja operacije vstavljanja in iskanja ter a Vozlišče razred, ki simbolizira vozlišče v binarnem iskalnem drevesu.

Medtem ko metoda vstavljanja vstavi novo vozlišče na ustrezno mesto v drevesu glede na njegovo vrednost, metoda iskanja išče vozlišče z določeno vrednostjo. Časovna zahtevnost obeh operacij v uravnoteženem drevesu je O(log n).

Izberite optimalno strukturo podatkov

Hitrost in prilagodljivost vaše aplikacije je mogoče bistveno izboljšati s podatkovno strukturo, ki ste jo izbrali. Upoštevanje vaših podatkov, vaših operacij in vašega okolja vam lahko pomaga pri izbiri najboljše strukture podatkov.

Pomembni so vidiki, kot so časovna kompleksnost, kompleksnost prostora, operacije branja in pisanja, sočasnost, tip podatkov in dostopnost knjižnice.

Z ocenjevanjem teže vsake komponente bi morali izbrati podatkovno strukturo, ki zadovoljuje potrebe vaše aplikacije.