Pareizas datu struktūras izvēle var padarīt jūsu programmu efektīvāku. Šeit ir ceļvedis, kas palīdzēs izdarīt pareizo izvēli.

Izvēlēties vislabāko datu struktūru saviem mērķiem var būt sarežģīti, jo ir pieejamas vairākas iespējas. Izvēloties datu struktūru, ņemiet vērā datus, ar kuriem jums būs darīšana, darbības, kas jāveic ar datiem, un vidi, kurā tiks izpildīta jūsu lietojumprogramma.

Izprotiet savus datus

Pirms datu struktūras izvēles ir svarīgi saprast datus, ar kuriem strādāsit. Kopīgas datu struktūras kas darbojas ar dažādiem datu tipiem, ietver masīvus, saistītos sarakstus, kokus, grafikus un jaucēj tabulas.

Piemēram, ja jums ir nepieciešams nejauši piekļūt elementiem no saviem datiem, masīvi varētu būt labākā izvēle. Gadījumā, ja jums pastāvīgi jāpievieno vai jādzēš elementi no saraksta un var mainīties arī saraksta lielums, saistītie saraksti var būt īpaši noderīgi.

Ja nepieciešams efektīvi uzglabāt vairākus datu līmeņus, piemēram, ierakstu struktūras, un veikt tādas darbības kā meklēšana un šķirošana, koki ir noderīgi.

instagram viewer

Ja nepieciešams aprakstīt mijiedarbību starp entītijām, piemēram, sociālajos tīklos, un veikt tādas darbības kā īsākais ceļš un savienojamība, priekšroka tiek dota diagrammām. Hash tabulas ir noderīgas ātrai atslēgu meklēšanai.

Apsveriet darbības, kas jāveic ar datiem

Izvēloties datu struktūru, jāņem vērā arī ar datiem veicamās darbības. Dažādas datu struktūras optimizē daudzas darbības, piemēram, kārtošanu, meklēšanu, ievietošanu un dzēšanu.

Piemēram, saistītie saraksti ir labāki tādām darbībām kā ievietošana un dzēšana, bet binārie koki ir vislabākie meklēšanai un kārtošanai. Jaukšanas tabula var būt labākā izvēle, ja jūsu lietojumprogrammai ir nepieciešama vienlaicīga ievietošana un meklēšana.

Novērtējiet vidi

Apsverot datu struktūru, jums ir jānovērtē vide, kurā lietojumprogramma darbosies. Vide ietekmē to, cik labi un cik ātri ir pieejamas datu struktūras.

Novērtējot savu pašreizējo stāvokli, ņemiet vērā šādus faktorus:

  1. Apstrādes jauda: izvēlieties datu struktūras savām lietojumprogrammām, kas labi darbojas datoros ar mazu apstrādes jaudu, kamēr darbojas platformā. Piemēram, vienkāršākas datu struktūras, piemēram, masīvi, varētu būt piemērotākas nekā koki vai diagrammas.
  2. Vienlaicīgums: Jums vajadzētu izvēlēties pavedienu drošu datu struktūru, kas var apstrādāt vienlaicīgu piekļuvi bez datu sabojāšanas; ja jūsu lietojumprogramma darbojas vienlaicīgā vidē, kur datu struktūrai vienlaikus piekļūst vairāki pavedieni vai procesi. Šajā gadījumā datu struktūras bez bloķēšanas, piemēram, ConcurrentLinkedQueue un ConcurrentHashMap var būt piemērotāki nekā tradicionālie, piemēram, ArrayListand HashMap.
  3. Tīkla latentums: ja jūsu lietojumprogrammai ir nepieciešama datu pārsūtīšana tīklā, lemjot par labāko datu struktūru, jāņem vērā tīkla latentums. Šādās situācijās datu struktūras izmantošana, kas ierobežo tīkla zvanus vai samazina datu pārsūtīšanas apjomu, var palīdzēt uzlabot izpildi.

Izplatītas datu struktūras un to izmantošanas gadījumi

Šeit ir vairāku populāru datu struktūru un to izmantošanas kopsavilkums.

  1. Masīvi: šī ir vienkārša un efektīva datu struktūra, kurā var būt fiksēta izmēra viena un tā paša datu tipa elementu sērija. Lai tie darbotos pareizi, tiem ir nepieciešama ātra, tieša piekļuve konkrētiem objektiem, izmantojot indeksu.
  2. Saistītie saraksti: saistītos sarakstus veido mezgli, kas satur elementu un atsauci uz nākamo mezglu un/vai iepriekšējo mezglu. Pateicoties to efektīvai darbībai, saistītie saraksti ir vispiemērotākie situācijās, kad nepieciešama bieža elementu ievietošana vai dzēšana. Tomēr piekļuve atsevišķiem elementiem, izmantojot indeksu saistītajos sarakstos, ir lēnāka, salīdzinot ar masīviem.
  3. Rindas un skursteņi: skursteņi atbilst kārtulai Last-In-First-Out (LIFO), kur pēdējais ievietotais vienums ir pirmais noņemtais vienums. Rindas regulē FIFO (First-In-First-Out) princips kur pirmais pievienotais elements tiek dzēsts arī pirmais.
  4. Hash tabulas: Hash tabulas ir datu struktūras veids, kurā ir atslēgu un vērtību pāri. Labākais risinājums ir izmantot hash tabulas, ja komponentu skaits nav paredzams un jums ir nepieciešama ātra piekļuve vērtībām pēc atslēgas.
  5. Koki: koki ir hierarhiskas datu struktūras, kas var glabāt elementu grupu hierarhijā. Labākie lietojumi priekš binārie meklēšanas koki atrodas hierarhiskās datu struktūrās, kur attiecības starp datu vienumiem var attēlot kokam līdzīgu struktūru.

Pareizās datu struktūras izvēle

Pirms datu struktūras izvēles apsveriet savas lietojumprogrammas datus, pienākumus un vidi. Veicot izvēli, padomājiet par šādiem elementiem:

  1. Laika sarežģītība: jūsu lietojumprogrammas veiktspēju var būtiski ietekmēt datu struktūras laika sarežģītība. Ja jūsu lietojumprogrammai ir nepieciešamas biežas meklēšanas vai izguves darbības, izmantojiet datu struktūru ar samazinātu laika sarežģītību, piemēram, jaucējtabulu.
  2. Kosmosa sarežģītība: datu struktūras telpas sarežģītība ir vēl viens svarīgs apsvērums. Ja jūsu lietojumprogrammai ir daudz atmiņas, izvēlieties datu struktūru ar mazāku vietas sarežģītību, piemēram, masīvu. Ja telpa nerada bažas, varat izmantot datu struktūru ar lielāku telpas sarežģītību, piemēram, koku.
  3. Lasīt vs. Rakstīt operācijas: ja jūsu lietojumprogramma izmanto daudz rakstīšanas darbību, izvēlieties datu struktūru ar ātrāku ievietošanas veiktspēju, piemēram, jaucējtabulu. Ja jūsu lietojumprogramma prasa daudzas lasīšanas darbības, izvēlieties datu struktūru ar ātrāku meklēšanas ātrumu, piemēram, bināro meklēšanas koku.
  4. Datu veids: dati, ar kuriem jūs strādājat, var ietekmēt arī jūsu izvēlēto datu struktūru. Piemēram, ja jūsu dati ir hierarhiski, varat izmantot uz koku balstītu datu struktūru. Ja jums ir vienkārši dati, kuriem ir jāpiekļūst nejauši, labākā izvēle var būt uz masīvu balstītas datu struktūras izvēle.
  5. Pieejamās bibliotēkas: Apsveriet bibliotēkas, kas ir viegli pieejamas datu struktūrai, kuru apsverat. To varētu būt vieglāk izpildīt un uzturēt, ja jūsu programmēšanas valodā noteiktai datu struktūrai ir pieejamas iebūvētas bibliotēkas.

Šis Python piemērs parāda, kā izvēlēties labāko datu struktūru konkrētam lietošanas gadījumam.

Apsveriet gadījumu, kad izstrādājat failu sistēmas lietojumprogrammu, kurai ir jāsaglabā un jāizgūst faili hierarhijā. Jums ir jāizvēlas datu struktūra, kas var efektīvi attēlot šo hierarhisko struktūru un ātri izpildīt tādas darbības kā meklēšana, ievietošana un dzēšana.

Varētu būt laba ideja izmantot uz koku balstītu datu struktūru, piemēram, bināro meklēšanu vai B koku. Ja ierakstu skaits katrā direktorijā ir salīdzinoši mazs un koks nav ļoti dziļš, binārās meklēšanas koks darbotos labi. B-koks būtu piemērotāks lielākam failu skaitam un dziļākām direktoriju struktūrām.

Tālāk ir sniegts Python binārā meklēšanas koka piemērs.

klasēMezgls:
def__tajā__(sevis, vērtība):
 pašvērtība = vērtība
 self.left_child = Nav
 self.right_child = Nav


klasēBinārais meklēšanas koks:


def__tajā__(pats):
 self.root = Nav
defievietot(sevis, vērtība):


ja sevis.sakne irNav:
 self.root = mezgls (vērtība)


cits:
 self._insert (vērtība, self.root) 
def_ievietot(pašs, vērtība, pašreizējais_mezgls):


ja vērtība < pašreizējā_mezgls.vērtība:
ja pašreizējais_mezgls.left_child irNav:
 current_node.left_child = Mezgls (vērtība)


cits:
 self._insert (vērtība, pašreizējais_node.left_child)
elifs vērtība > pašreizējā_mezgls.vērtība:
ja pašreizējais_mezgls.labais_bērns irNav:
 current_node.right_child = Mezgls (vērtība)
cits:
 self._insert (vērtība, current_node.right_child)


cits:
 drukāt ("Vērtība jau pastāv kokā.")
defMeklēt(sevis, vērtība):
ja sevis.sakne irnēNav:
atgriezties self._search (vērtība, self.root)


cits:
atgrieztiesNepatiesi
def_Meklēt(pašs, vērtība, pašreizējais_mezgls):


ja vērtība == pašreizējais_node.vērtība:
atgrieztiesTaisnība


elifs vērtība < pašreizējā_mezgls.vērtība un pašreizējais_mezgls.left_child irnēNav:
atgriezties self._search (vērtība, pašreizējais_node.left_child)


elifs vērtība > pašreizējā_mezgls.vērtība un pašreizējais_mezgls.labais_bērns irnēNav:
atgriezties self._search (vērtība, current_node.right_child)
cits:
atgrieztiesNepatiesi

Šajā īstenošanā jūs izveidojat divas klases: a Binārais meklēšanas koks klase, kas pārvalda ievietošanas un meklēšanas darbības un a Mezgls klase, kas simbolizē mezglu binārajā meklēšanas kokā.

Kamēr ievietošanas metode ievieto jaunu mezglu attiecīgajā koka vietā atkarībā no tā vērtības, meklēšanas metode meklē mezglu ar noteiktu vērtību. Abu operāciju laika sarežģītība līdzsvarotā kokā ir O(log n).

Atlasiet optimālo datu struktūru

Jūsu lietojumprogrammas ātrumu un pielāgošanās spēju var ievērojami uzlabot jūsu izvēlētā datu struktūra. Jūsu datu, darbību un vides ņemšana vērā var palīdzēt jums izvēlēties labāko datu struktūru.

Svarīgi ir tādi apsvērumi kā laika sarežģītība, telpas sarežģītība, lasīšanas un rakstīšanas darbības, vienlaicīgums, datu tips un bibliotēkas pieejamība.

Novērtējot katra komponenta svaru, jums vajadzētu izvēlēties datu struktūru, kas atbilst jūsu lietojumprogrammas vajadzībām.