Výber správnej dátovej štruktúry môže zefektívniť váš program. Tu je návod, ktorý vám pomôže urobiť správnu voľbu.

Výber najlepšej štruktúry údajov pre vaše ciele môže byť náročný s viacerými dostupnými možnosťami. Pri výbere dátovej štruktúry zvážte dáta, s ktorými budete pracovať, operácie, ktoré sa majú s dátami vykonať, a prostredie, v ktorom sa bude vaša aplikácia vykonávať.

Pochopte svoje údaje

Pred výberom štruktúry údajov je dôležité porozumieť údajom, s ktorými sa budete zaoberať. Spoločné dátové štruktúry ktoré pracujú s rôznymi typmi údajov, zahŕňajú polia, prepojené zoznamy, stromy, grafy a hašovacie tabuľky.

Napríklad, keď potrebujete získať náhodný prístup k prvkom z vašich údajov, polia môžu byť najlepšou voľbou. V prípade, že neustále potrebujete pridávať alebo odstraňovať prvky zo zoznamu a veľkosť zoznamu sa tiež môže meniť, môžu byť prepojené zoznamy obzvlášť užitočné.

Keď potrebujete efektívne ukladať viaceré úrovne údajov, ako sú napríklad štruktúry záznamov, a vykonávať operácie ako vyhľadávanie a triedenie, potom sú stromy užitočné.

instagram viewer

Keď potrebujete opísať interakcie medzi entitami, ako sú tie v sociálnych sieťach, a vykonať operácie, ako je najkratšia cesta a konektivita, potom sú preferované grafy. Hash tabuľky sú užitočné pre rýchle vyhľadávanie kľúčov.

Zvážte operácie, ktoré sa majú vykonať s údajmi

Pri výbere štruktúry údajov musíte zvážiť aj operácie, ktoré sa majú s údajmi vykonať. Rôzne dátové štruktúry optimalizujú početné akcie, ako je triedenie, vyhľadávanie, vkladanie a mazanie.

Napríklad prepojené zoznamy sú lepšie na akcie, ako je vkladanie a mazanie, ale binárne stromy sú najlepšie na vyhľadávanie a triedenie. Ak vaša aplikácia vyžaduje súčasné vkladanie a vyhľadávanie, môže byť hašovacia tabuľka najlepšou voľbou.

Hodnotiť životné prostredie

Pri zvažovaní štruktúry údajov musíte vyhodnotiť prostredie, v ktorom bude aplikácia bežať. Prostredie ovplyvňuje, ako dobre a ako rýchlo sú dostupné dátové štruktúry.

Pri hodnotení vášho aktuálneho stavu zvážte nasledujúce faktory:

  1. Výkon spracovania: Vyberte si dátové štruktúry pre svoje aplikácie, ktoré dobre fungujú na počítačoch s malým výpočtovým výkonom pri behu na platforme. Napríklad jednoduchšie dátové štruktúry, ako sú polia, by mohli byť vhodnejšie ako stromy alebo grafy.
  2. Súbeh: Mali by ste zvoliť dátovú štruktúru bezpečnú pre vlákna, ktorá dokáže spracovať simultánny prístup bez poškodenia dát; ak vaša aplikácia beží v súbežnom prostredí, kde k štruktúre údajov pristupuje súčasne viacero vlákien alebo procesov. V tomto prípade dátové štruktúry bez zámkov ako ConcurrentLinkedQueue a ConcurrentHashMap môžu byť vhodnejšie ako tradičné, ako napríklad ArrayListand HashMap.
  3. Latencia siete: Ak vaša aplikácia vyžaduje prenos dát cez sieť, pri rozhodovaní o najlepšej dátovej štruktúre musíte zvážiť latenciu siete. V takýchto situáciách môže použitie dátovej štruktúry, ktorá obmedzuje sieťové hovory alebo znižuje objem prenosu dát, pomôcť zlepšiť vykonávanie.

Spoločné dátové štruktúry a ich prípady použitia

Tu je súhrn niekoľkých populárnych dátových štruktúr a ich použitia.

  1. Polia: Toto je jednoduchá a efektívna dátová štruktúra, ktorá môže obsahovať sériu prvkov s pevnou veľkosťou rovnakého dátového typu. Aby správne fungovali, potrebujú rýchly a priamy prístup ku konkrétnym objektom prostredníctvom indexu.
  2. Prepojené zoznamy: Prepojené zoznamy sa skladajú z uzlov, ktoré obsahujú prvok a odkaz na nasledujúci uzol a/alebo predchádzajúci uzol. Prepojené zoznamy sú vďaka svojim efektívnym operáciám najvhodnejšie v situáciách vyžadujúcich časté vkladanie alebo odstraňovanie prvkov. Prístup k jednotlivým prvkom podľa indexu v prepojených zoznamoch je však pomalší v porovnaní s poliami.
  3. Fronty a zásobníky: Hromady dodržiavajú pravidlo Last-In-First-Out (LIFO), kde posledná vložená položka je prvá odstránená položka. Fronty sa riadia princípom First-In-First-Out (FIFO). kde prvý pridaný prvok je zároveň prvým vymazaným prvkom.
  4. Hash tabuľky: Hašovacie tabuľky sú formou dátovej štruktúry, ktorá obsahuje páry kľúč – hodnota. Najlepším riešením je použiť hašovacie tabuľky, keď je počet komponentov nepredvídateľný a potrebujete rýchly prístup k hodnotám pomocou kľúča.
  5. Stromy: Stromy sú hierarchické dátové štruktúry, ktoré môžu uchovávať skupinu prvkov v hierarchii. Najlepšie využitie pre binárne vyhľadávacie stromy sú v hierarchických dátových štruktúrach, kde vzťahy medzi dátovými položkami môžu predstavovať stromovú štruktúru.

Výber správnej dátovej štruktúry

Pred výberom štruktúry údajov zvážte údaje, povinnosti a prostredie vašej aplikácie. Pri výbere sa zamyslite nad nasledujúcimi prvkami:

  1. Časová zložitosť: Výkon vašej aplikácie môže byť výrazne ovplyvnený časovou zložitosťou vašej dátovej štruktúry. Ak vaša aplikácia vyžaduje časté operácie vyhľadávania alebo získavania údajov, použite dátovú štruktúru so zníženou časovou zložitosťou, napríklad hašovaciu tabuľku.
  2. Priestorová zložitosť: Priestorová zložitosť dátovej štruktúry je ďalším dôležitým faktorom. Ak je vaša aplikácia náročná na pamäť, vyberte dátovú štruktúru s menšou priestorovou zložitosťou, napríklad pole. Ak sa priestor netýka, môžete použiť dátovú štruktúru s väčšou priestorovou zložitosťou, ako je napríklad strom.
  3. Čítanie vs. Operácie zápisu: Ak vaša aplikácia využíva veľa operácií zápisu, vyberte dátovú štruktúru s rýchlejším výkonom vkladania, napríklad hašovaciu tabuľku. Ak vaša aplikácia vyžaduje veľa operácií čítania, vyberte dátovú štruktúru s rýchlejšou rýchlosťou vyhľadávania, ako je napríklad binárny vyhľadávací strom.
  4. Typ údajov: Údaje, s ktorými pracujete, môžu tiež ovplyvniť vybratú štruktúru údajov. Môžete napríklad použiť stromovú štruktúru údajov, ak sú vaše údaje hierarchické. Ak máte jednoduché údaje, ku ktorým je potrebné pristupovať náhodne, najlepšou voľbou môže byť výber dátovej štruktúry založenej na poli.
  5. Dostupné knižnice: Zvážte knižnice, ktoré sú ľahko dostupné pre dátovú štruktúru, o ktorej uvažujete. Spustenie a údržba by mohla byť jednoduchšia, ak má váš programovací jazyk k dispozícii vstavané knižnice pre určitú dátovú štruktúru.

Nasledujúci príklad Pythonu ukazuje, ako vybrať najlepšiu dátovú štruktúru pre konkrétny prípad použitia.

Zvážte prípad, keď vyvíjate aplikáciu súborového systému, ktorá musí ukladať a získavať súbory v hierarchii. Musíte si vybrať dátovú štruktúru, ktorá dokáže efektívne reprezentovať túto hierarchickú štruktúru a rýchlo vykonávať operácie ako vyhľadávanie, vkladanie a mazanie.

Mohlo by byť dobrým nápadom použiť stromovú dátovú štruktúru, ako je binárne vyhľadávanie alebo B-strom. Ak je počet záznamov v každom adresári relatívne malý a strom nie je príliš hlboký, binárny vyhľadávací strom by fungoval dobre. Pre väčší počet súborov a hlbšie adresárové štruktúry by bol vhodnejší B-strom.

Nižšie je uvedený príklad binárneho vyhľadávacieho stromu v Pythone.

triedaUzol:
def__init__(ja, hodnota):
 seba.hodnota = hodnota
 self.left_child = žiadne
 self.right_child = žiadne


triedaBinarySearchTree:


def__init__(ja):
 self.koreň = žiadne
defvložiť(ja, hodnota):


ak seba.koreň ježiadne:
 self.root = Uzol (hodnota)


inak:
 self._insert (value, self.root) 
def_vložiť(vlastné, hodnota, aktuálny_uzol):


ak hodnota < aktuálny_uzol.hodnota:
ak current_node.left_child ježiadne:
 current_node.left_child = Uzol (hodnota)


inak:
 self._insert (value, current_node.left_child)
elif hodnota > aktuálny_uzol.hodnota:
ak current_node.right_child ježiadne:
 current_node.right_child = Uzol (hodnota)
inak:
 self._insert (value, current_node.right_child)


inak:
 vytlačiť ("Hodnota už v strome existuje.")
defVyhľadávanie(ja, hodnota):
ak seba.koreň jeniežiadne:
vrátiť self._search (value, self.root)


inak:
vrátiťNepravdivé
def_Vyhľadávanie(vlastné, hodnota, aktuálny_uzol):


ak value == current_node.value:
vrátiťPravda


elif hodnota < aktuálny_uzol.hodnota a current_node.left_child jeniežiadne:
vrátiť self._search (value, current_node.left_child)


elif hodnota > aktuálny_uzol.hodnota a current_node.right_child jeniežiadne:
vrátiť self._search (value, current_node.right_child)
inak:
vrátiťNepravdivé

V tejto implementácii vytvoríte dve triedy: a BinarySearchTree trieda, ktorá riadi operácie vkladania a vyhľadávania a a Uzol trieda, ktorá symbolizuje uzol v binárnom vyhľadávacom strome.

Zatiaľ čo metóda insert vloží nový uzol na príslušné miesto v strome v závislosti od jeho hodnoty, metóda vyhľadávania hľadá uzol so zadanou hodnotou. Časová zložitosť oboch operácií vo vyváženom strome je O (log n).

Vyberte optimálnu dátovú štruktúru

Rýchlosť a prispôsobivosť vašej aplikácie môže výrazne zlepšiť dátová štruktúra, ktorú si zvolíte. Zohľadnenie vašich údajov, vašich operácií a vášho prostredia vám môže pomôcť pri výbere najlepšej štruktúry údajov.

Dôležité sú úvahy ako časová zložitosť, priestorová zložitosť, operácie čítania a zápisu, súbežnosť, typ údajov a dostupnosť knižnice.

Posúdením hmotnosti každého komponentu by ste si mali vybrať štruktúru údajov, ktorá vyhovuje potrebám vašej aplikácie.