Õige andmestruktuuri valimine võib muuta teie programmi tõhusamaks. Siin on juhend, mis aitab teil õiget valikut teha.

Eesmärkide jaoks parima andmestruktuuri valimine võib paljude saadaolevate valikute tõttu olla keeruline. Andmestruktuuri valimisel arvestage andmetega, millega te tegelete, andmetega tehtavaid toiminguid ja keskkonda, milles teie rakendus käivitub.

Mõistke oma andmeid

Enne andmestruktuuri valimist käsitletavate andmete mõistmine on ülioluline. Ühised andmestruktuurid mis töötavad erinevate andmetüüpidega, hõlmavad massiive, lingitud loendeid, puid, graafikuid ja räsitabeleid.

Näiteks kui teil on vaja oma andmetest juhuslikult elementidele juurde pääseda, võivad massiivid olla parim valik. Kui teil on pidevalt vaja loendist elemente lisada või kustutada ning loendi suurus võib samuti muutuda, võivad lingitud loendid olla eriti kasulikud.

Kui teil on vaja tõhusalt salvestada mitut taset andmeid (nt kirjestruktuure) ja teha selliseid toiminguid nagu otsimine ja sortimine, on puud kasulikud.

instagram viewer

Kui teil on vaja kirjeldada üksuste vahelisi interaktsioone (nt suhtlusvõrgustikes) ja teha selliseid toiminguid nagu lühim tee ja ühenduvus, eelistatakse graafikuid. Räsitabelid on abiks võtmete kiireks otsimiseks.

Kaaluge andmetega tehtavaid toiminguid

Andmestruktuuri valimisel tuleb arvestada ka andmetega tehtavate toimingutega. Erinevad andmestruktuurid optimeerivad paljusid toiminguid, nagu sortimine, otsimine, sisestamine ja kustutamine.

Näiteks lingitud loendid on paremad selliste toimingute jaoks nagu sisestamine ja kustutamine, kuid binaarpuud on parimad otsimiseks ja sortimiseks. Räsitabel võib olla parim valik, kui teie rakendus nõuab samaaegset sisestamist ja otsimist.

Hinda keskkonda

Andmestruktuuri kaalumisel peate hindama keskkonda, milles rakendus töötab. Keskkond mõjutab seda, kui hästi ja kui kiiresti juurdepääsetavad andmestruktuurid on.

Oma praeguse seisundi hindamisel arvestage järgmiste teguritega:

  1. Töötlemisvõimsus: valige oma rakenduste jaoks andmestruktuurid, mis töötavad hästi väikese töötlemisvõimsusega arvutites platvormil töötamise ajal. Näiteks võivad lihtsamad andmestruktuurid, nagu massiivid, olla sobivamad kui puud või graafikud.
  2. Samaaegsus: peaksite valima lõimekindla andmestruktuuri, mis saab hakkama samaaegse juurdepääsuga ilma andmeid kahjustamata; kui teie rakendus töötab samaaegses keskkonnas, kus andmestruktuurile pääseb korraga juurde mitu lõime või protsessi. Sel juhul lukuvabad andmestruktuurid nagu ConcurrentLinkedQueue ja Samaaegne HashMap võivad olla sobivamad kui traditsioonilised, näiteks ArrayListand HashMap.
  3. Võrgu latentsus: kui teie rakendus nõuab andmeedastust üle võrgu, peate parima andmestruktuuri valimisel arvestama võrgu latentsusega. Sellistes olukordades võib andmestruktuuri kasutamine, mis piirab võrgukõnesid või vähendab andmeedastuse mahtu, aidata täitmist parandada.

Levinud andmestruktuurid ja nende kasutusjuhtumid

Siin on kokkuvõte mitmetest populaarsetest andmestruktuuridest ja nende kasutamisest.

  1. Massiivid: see on lihtne ja tõhus andmestruktuur, mis võib sisaldada sama andmetüübi elementide fikseeritud suurusega seeriat. Et need korralikult töötaksid, vajavad nad kiiret ja otsest juurdepääsu konkreetsetele objektidele indeksi kaudu.
  2. Lingitud loendid: Lingitud loendid koosnevad sõlmedest, mis sisaldavad elementi ja viidet järgmisele sõlmele ja/või eelmisele sõlmele. Tõhusate toimingute tõttu sobivad lingitud loendid kõige paremini olukordades, mis nõuavad elementide sagedast sisestamist või kustutamist. Siiski on lingitud loendites üksikutele elementidele indeksi kaudu juurdepääs massiividega võrreldes aeglasem.
  3. Järjekorrad ja virnad: virnad järgivad reeglit Last-in-First-Out (LIFO), kus viimasena sisestatud üksus on esimene eemaldatud üksus. Järjekorrad juhinduvad FIFO (First-In-First-Out) põhimõttest kus esimene lisatud element kustutatakse ka esimesena.
  4. Räsi tabelid: räsitabelid on andmestruktuuri vorm, mis sisaldab võtme-väärtuste paare. Parim lahendus on kasutada räsitabeleid, kui komponentide arv on ettearvamatu ja vajate kiiret juurdepääsu väärtustele võtme abil.
  5. puud: puud on hierarhilised andmestruktuurid, mis võivad salvestada hierarhias elementide rühma. Parimad kasutusvõimalused binaarsed otsingupuud on hierarhilistes andmestruktuurides, kus andmeüksuste vahelised seosed võivad kujutada endast puulaadset struktuuri.

Õige andmestruktuuri valimine

Enne andmestruktuuri valimist kaaluge oma rakenduse andmeid, kohustusi ja keskkonda. Valiku tegemisel mõelge järgmistele elementidele:

  1. Aja keerukus: teie andmestruktuuri ajaline keerukus võib teie rakenduse toimivust märkimisväärselt mõjutada. Kui teie rakendus nõuab sagedasi otsingu- või toomistoiminguid, kasutage väiksema ajakeerukusega andmestruktuuri, näiteks räsitabelit.
  2. Ruumi keerukus: Andmestruktuuri ruumiline keerukus on veel üks oluline kaalutlus. Kui teie rakendus on mälumahukas, valige ruumilisema keerukusega andmestruktuur, näiteks massiiv. Kui ruum ei ole probleem, võite kasutada suurema ruumilise keerukusega andmestruktuuri, näiteks puud.
  3. Lugege vs. Kirjuta operatsioonid: kui teie rakendus kasutab palju kirjutamisoperatsioone, valige kiirema sisestamisjõudlusega andmestruktuur, näiteks räsitabel. Kui teie rakendus nõuab palju lugemistoiminguid, valige kiirema otsingukiirusega andmestruktuur, näiteks binaarne otsingupuu.
  4. Andmete tüüp: andmed, millega tegelete, võivad samuti mõjutada teie valitud andmestruktuuri. Näiteks võite kasutada puupõhist andmestruktuuri, kui teie andmed on hierarhilised. Kui teil on lihtsaid andmeid, millele tuleb juhuslikult juurde pääseda, võib parim valik olla massiivipõhise andmestruktuuri valimine.
  5. Saadaolevad raamatukogud: kaaluge teeke, mis on teie kaalutava andmestruktuuri jaoks hõlpsasti juurdepääsetavad. Seda võib olla lihtsam käivitada ja hooldada, kui teie programmeerimiskeeles on teatud andmestruktuuri jaoks saadaval sisseehitatud teegid.

Järgmine Pythoni näide demonstreerib, kuidas valida konkreetse kasutusjuhu jaoks parim andmestruktuur.

Mõelge juhtumile, kus arendate failisüsteemi rakendust, mis peab faile hierarhias salvestama ja hankima. Peate valima andmestruktuuri, mis suudab seda hierarhilist struktuuri tõhusalt esindada ja sooritada kiiresti selliseid toiminguid nagu otsing, sisestamine ja kustutamine.

Võib olla hea mõte kasutada puupõhist andmestruktuuri, näiteks binaarset otsingut või B-puud. Kui kirjete arv igas kataloogis on suhteliselt väike ja puu ei ole väga sügav, toimiks binaarne otsingupuu hästi. B-puu oleks sobivam suurema hulga failide ja sügavamate kataloogistruktuuride jaoks.

Allpool on näide binaarsest otsingupuust Pythonis.

klassSõlm:
def__selles__(ise, väärtus):
 ise.väärtus = väärtus
 ise.vasak_laps = Mitte ühtegi
 ise.õige_laps = Mitte ühtegi


klassBinaarne otsingupuu:


def__selles__(ise):
 ise.juur = Mitte ühtegi
defsisestada(ise, väärtus):


kui ise.juur onMitte ühtegi:
 self.root = Sõlm (väärtus)


muidu:
 self._insert (väärtus, ise.juur) 
def_insert(ise, väärtus, praegune_sõlm):


kui väärtus < praegune_sõlm.väärtus:
kui praegune_sõlm.left_child onMitte ühtegi:
 current_node.left_child = Sõlm (väärtus)


muidu:
 self._insert (väärtus, current_node.left_child)
elif väärtus > praegune_sõlm.väärtus:
kui praegune_sõlm.õige_laps onMitte ühtegi:
 current_node.right_child = Sõlm (väärtus)
muidu:
 self._insert (väärtus, current_node.right_child)


muidu:
 print("Väärtus on puus juba olemas.")
defotsing(ise, väärtus):
kui ise.juur onmitteMitte ühtegi:
tagasi self._search (väärtus, ise.juur)


muidu:
tagasiVale
def_otsing(ise, väärtus, praegune_sõlm):


kui väärtus == praegune_sõlm.väärtus:
tagasiTõsi


elif väärtus < praegune_sõlm.väärtus ja praegune_sõlm.left_child onmitteMitte ühtegi:
tagasi self._search (väärtus, current_node.left_child)


elif väärtus > praegune_sõlm.väärtus ja praegune_sõlm.õige_laps onmitteMitte ühtegi:
tagasi self._search (väärtus, current_node.right_child)
muidu:
tagasiVale

Selles teostuses konstrueerite kaks klassi: a Binaarne otsingupuu klass, mis haldab sisestamis- ja otsinguoperatsioone ning a Sõlm klass, mis sümboliseerib binaarse otsingupuu sõlme.

Kui lisamismeetod lisab uue sõlme puu sobivasse asukohta olenevalt selle väärtusest, siis otsingumeetod otsib määratud väärtusega sõlme. Mõlema toimingu ajaline keerukus tasakaalustatud puus on O(log n).

Valige optimaalne andmestruktuur

Teie rakenduse kiirust ja kohanemisvõimet saab teie valitud andmestruktuur oluliselt parandada. Teie andmete, toimingute ja keskkonna arvessevõtmine võib aidata teil valida parima andmestruktuuri.

Olulised on sellised kaalutlused nagu ajaline keerukus, ruumi keerukus, lugemis- ja kirjutamistoimingud, samaaegsus, andmetüüp ja teegi juurdepääsetavus.

Hinnates iga komponendi kaalu, peaksite valima andmestruktuuri, mis vastab teie rakenduse vajadustele.