Pasirinkus tinkamą duomenų struktūrą, programa gali būti efektyvesnė. Štai vadovas, padėsiantis padaryti teisingą pasirinkimą.

Gali būti sudėtinga pasirinkti geriausią duomenų struktūrą savo tikslams, nes yra keletas galimų parinkčių. Renkantis duomenų struktūrą, atsižvelkite į duomenis, su kuriais turėsite susidoroti, su duomenimis atliktinas operacijas ir aplinką, kurioje bus vykdoma jūsų programa.

Supraskite savo duomenis

Labai svarbu suprasti duomenis, su kuriais dirbsite prieš pasirenkant duomenų struktūrą. Įprastos duomenų struktūros kurie veikia su įvairių tipų duomenimis, apima masyvus, susietus sąrašus, medžius, grafikus ir maišos lenteles.

Pavyzdžiui, kai reikia atsitiktinai pasiekti elementus iš duomenų, masyvai gali būti geriausias pasirinkimas. Jei jums nuolat reikia pridėti ar ištrinti sąrašo elementus, o sąrašo dydis taip pat gali keistis, susieti sąrašai gali būti ypač naudingi.

Kai reikia efektyviai saugoti kelių lygių duomenis, pvz., įrašų struktūras, ir atlikti tokias operacijas kaip paieška ir rūšiavimas, medžiai yra naudingi.

instagram viewer

Kai reikia apibūdinti sąveiką tarp objektų, pvz., esančių socialiniuose tinkluose, ir atlikti tokias operacijas kaip trumpiausias kelias ir ryšys, pirmenybė teikiama diagramoms. Maišos lentelės yra naudingos norint greitai ieškoti raktų.

Apsvarstykite operacijas, kurias reikia atlikti su duomenimis

Renkantis duomenų struktūrą, taip pat turite atsižvelgti į operacijas, kurias reikia atlikti su duomenimis. Įvairios duomenų struktūros optimizuoja daugybę veiksmų, tokių kaip rūšiavimas, paieška, įterpimas ir ištrynimas.

Pavyzdžiui, susieti sąrašai geriau tinka tokiems veiksmams kaip įterpimas ir trynimas, tačiau dvejetainiai medžiai geriausiai tinka paieškai ir rūšiavimui. Maišos lentelė gali būti geriausias pasirinkimas, jei jūsų programai reikia vienu metu įterpti ir ieškoti.

Įvertinkite Aplinką

Svarstydami duomenų struktūrą, turite įvertinti aplinką, kurioje programa veiks. Aplinka turi įtakos tam, kaip gerai ir kaip greitai pasiekiamos duomenų struktūros.

Vertindami savo dabartinę būklę, atsižvelkite į šiuos veiksnius:

  1. Apdorojimo galia: pasirinkite duomenų struktūras savo programoms, kurios gerai veiktų kompiuteriuose su maža apdorojimo galia, kai veikia platformoje. Pavyzdžiui, paprastesnės duomenų struktūros, pvz., masyvai, gali būti tinkamesnės nei medžiai ar grafikai.
  2. Lygiagretumas: Turėtumėte pasirinkti gijų saugią duomenų struktūrą, kuri gali apdoroti vienalaikę prieigą be duomenų sugadinimo; jei jūsų programa veikia lygiagrečioje aplinkoje, kur kelios gijos arba procesai vienu metu pasiekia duomenų struktūrą. Šiuo atveju neužrakintos duomenų struktūros kaip ConcurrentLinkedQueue ir ConcurrentHashMap gali būti tinkamesni nei tradiciniai, tokie kaip ArrayListand HashMap.
  3. Tinklo delsa: jei jūsų programai reikalingas duomenų perdavimas tinkle, nuspręsdami dėl geriausios duomenų struktūros turite atsižvelgti į tinklo delsą. Tokiose situacijose naudojant duomenų struktūrą, kuri riboja tinklo skambučius arba sumažina duomenų perdavimo kiekį, gali padėti pagerinti vykdymą.

Įprastos duomenų struktūros ir jų naudojimo atvejai

Čia pateikiama kelių populiarių duomenų struktūrų ir jų naudojimo santrauka.

  1. Masyvai: Tai paprasta ir efektyvi duomenų struktūra, kurioje gali būti fiksuoto dydžio to paties duomenų tipo elementų. Kad jie tinkamai veiktų, jiems reikia greitos, tiesioginės prieigos prie konkrečių objektų per rodyklę.
  2. Susieti sąrašai: susietus sąrašus sudaro mazgai, kuriuose yra elementas ir nuoroda į kitą mazgą ir (arba) ankstesnį mazgą. Dėl efektyvių operacijų susieti sąrašai geriausiai tinka situacijose, kai reikia dažnai įterpti arba ištrinti elementus. Tačiau prieiga prie atskirų elementų pagal indeksą susietuose sąrašuose yra lėtesnė, palyginti su masyvais.
  3. Eilės ir krūvos: rietuvės atitinka taisyklę Last-In-First-Out (LIFO), kai paskutinis įterptas elementas yra pirmasis pašalintas elementas. Eilės reguliuojamos pagal FIFO principą kur pirmasis pridėtas elementas yra ir pirmasis ištrintas.
  4. Maišos lentelės: maišos lentelės yra duomenų struktūros forma, kurioje yra raktų ir reikšmių poros. Geriausias sprendimas yra naudoti maišos lenteles, kai komponentų skaičius yra nenuspėjamas ir jums reikia greitai pasiekti reikšmes pagal raktą.
  5. medžiai: medžiai yra hierarchinės duomenų struktūros, kurios gali saugoti elementų grupę hierarchijoje. Geriausias panaudojimas skirtas dvejetainiai paieškos medžiai yra hierarchinėse duomenų struktūrose, kur ryšiai tarp duomenų elementų gali būti į medį panaši struktūra.

Tinkamos duomenų struktūros pasirinkimas

Prieš rinkdamiesi duomenų struktūrą, apsvarstykite programos duomenis, įsipareigojimus ir aplinką. Rinkdamiesi pagalvokite apie šiuos elementus:

  1. Laiko sudėtingumas: jūsų programos našumui gali turėti didelės įtakos duomenų struktūros sudėtingumas laiko atžvilgiu. Jei jūsų programai reikalingos dažnos paieškos arba gavimo operacijos, naudokite sumažėjusio laiko sudėtingumo duomenų struktūrą, pvz., maišos lentelę.
  2. Erdvės sudėtingumas: Dar vienas svarbus aspektas yra duomenų struktūros sudėtingumas erdvėje. Jei jūsų programai reikia daug atminties, rinkitės mažiau sudėtingą duomenų struktūrą, pvz., masyvą. Jei vietos nerūpi, galite naudoti sudėtingesnę duomenų struktūrą, pvz., medį.
  3. Skaityti vs. Rašymo operacijos: jei jūsų programoje naudojama daug rašymo operacijų, pasirinkite duomenų struktūrą su greitesniu įterpimu, pvz., maišos lentelę. Jei jūsų programai reikia daug skaitymo operacijų, pasirinkite duomenų struktūrą su greitesniu paieškos greičiu, pvz., dvejetainį paieškos medį.
  4. Duomenų tipas: duomenys, su kuriais dirbate, taip pat gali turėti įtakos pasirinktai duomenų struktūrai. Pavyzdžiui, galite naudoti medžiu pagrįstą duomenų struktūrą, jei jūsų duomenys yra hierarchiniai. Jei turite paprastų duomenų, kuriuos reikia pasiekti atsitiktinai, geriausias pasirinkimas gali būti masyvo duomenų struktūros pasirinkimas.
  5. Galimos bibliotekos: apsvarstykite bibliotekas, kurios yra lengvai pasiekiamos duomenų struktūrai, kurią svarstote. Gali būti lengviau vykdyti ir prižiūrėti, jei jūsų programavimo kalba turi įmontuotų bibliotekų, skirtų tam tikrai duomenų struktūrai.

Šis Python pavyzdys parodo, kaip pasirinkti geriausią duomenų struktūrą konkrečiam naudojimo atvejui.

Apsvarstykite atvejį, kai kuriate failų sistemos programą, kuri turi saugoti ir gauti failus hierarchijoje. Turite pasirinkti duomenų struktūrą, kuri galėtų efektyviai reprezentuoti šią hierarchinę struktūrą ir greitai atlikti tokias operacijas kaip paieška, įterpimas ir trynimas.

Gali būti naudinga naudoti medžiu pagrįstą duomenų struktūrą, pvz., dvejetainę paiešką arba B medį. Jei įrašų skaičius kiekviename kataloge yra palyginti mažas, o medis nėra labai gilus, dvejetainis paieškos medis veiktų gerai. B-medis labiau tiktų didesniam failų skaičiui ir gilesnėms katalogų struktūroms.

Žemiau pateikiamas dvejetainio Python paieškos medžio pavyzdys.

klasėMazgas:
def__init__(aš, vertė):
 savęs.vertė = vertė
 self.left_child = Nė vienas
 pats.teisus_vaikas = Nė vienas


klasėBinarySearchTree:


def__init__(savarankiškai):
 savaime.šaknis = Nė vienas
defĮdėti(aš, vertė):


jeigu savęs.šaknis yraNė vienas:
 self.root = Mazgas (vertė)


Kitas:
 self._insert (value, self.root) 
def_Įdėti(savaime, vertė, dabartinis_mazgas):


jeigu reikšmė < dabartinis_mazgas.vertė:
jeigu dabartinis_mazgas.left_child yraNė vienas:
 current_node.left_child = Mazgas (reikšmė)


Kitas:
 self._insert (vertė, current_node.left_child)
elifas vertė > dabartinis_mazgas.vertė:
jeigu dabartinis_mazgas.dešinysis_vaikas yraNė vienas:
 current_node.right_child = Mazgas (vertė)
Kitas:
 self._insert (vertė, current_node.right_child)


Kitas:
 spausdinti ("Vertė medyje jau yra.")
defPaieška(aš, vertė):
jeigu savęs.šaknis yraneNė vienas:
grąžinti self._search (value, self.root)


Kitas:
grąžintiNetiesa
def_Paieška(savaime, vertė, dabartinis_mazgas):


jeigu vertė == dabartinis_mazgas.vertė:
grąžintiTiesa


elifas reikšmė < dabartinis_mazgas.vertė ir dabartinis_mazgas.left_child yraneNė vienas:
grąžinti self._search (vertė, dabartinis_mazgas.left_child)


elifas reikšmė > dabartinis_mazgas.vertė ir dabartinis_mazgas.dešinysis_vaikas yraneNė vienas:
grąžinti self._search (vertė, current_node.right_child)
Kitas:
grąžintiNetiesa

Šiame įgyvendinime sukuriate dvi klases: a BinarySearchTree klasė, kuri valdo įterpimo ir paieškos operacijas ir a Mazgas klasė, kuri simbolizuoja mazgą dvejetainiame paieškos medyje.

Nors įterpimo metodas įterpia naują mazgą į atitinkamą medžio vietą, atsižvelgiant į jo reikšmę, paieškos metodas ieško mazgo su nurodyta verte. Abiejų operacijų laiko sudėtingumas subalansuotame medyje yra O(log n).

Pasirinkite optimalią duomenų struktūrą

Pasirinkta duomenų struktūra gali žymiai pagerinti jūsų programos greitį ir pritaikomumą. Atsižvelgdami į savo duomenis, operacijas ir aplinką, galite pasirinkti geriausią duomenų struktūrą.

Svarbūs aspektai, tokie kaip laiko sudėtingumas, erdvės sudėtingumas, skaitymo ir rašymo operacijos, lygiagretumas, duomenų tipas ir bibliotekos prieinamumas.

Įvertindami kiekvieno komponento svorį, turėtumėte pasirinkti duomenų struktūrą, atitinkančią jūsų programos poreikius.