Å velge riktig datastruktur kan gjøre programmet mer effektivt. Her er en guide som hjelper deg å ta det riktige valget.

Å velge den beste datastrukturen for målene dine kan være utfordrende med flere tilgjengelige alternativer. Når du velger en datastruktur, bør du vurdere dataene du skal forholde deg til, operasjonene som skal utføres på dataene og miljøet der applikasjonen din skal kjøres.

Forstå dataene dine

Det er viktig å forstå dataene du skal forholde deg til før du velger en datastruktur. Vanlige datastrukturer som fungerer med ulike datatyper inkluderer arrays, koblede lister, trær, grafer og hashtabeller.

For eksempel, når du trenger å få tilgang til elementer tilfeldig fra dataene dine, kan arrays være det beste valget. I tilfelle du hele tiden trenger å legge til eller slette elementer fra en liste, og listestørrelsen også kan endre seg, kan koblede lister være spesielt nyttige.

Når du trenger å effektivt lagre flere nivåer av data, for eksempel poststrukturer, og utføre operasjoner som søk og sortering, er trær nyttige.

instagram viewer

Når du trenger å beskrive interaksjoner mellom enheter, for eksempel de i sosiale nettverk, og utføre operasjoner som korteste vei og tilkobling, er Grafer å foretrekke. Hash-tabeller er nyttige for raske nøkkeloppslag.

Vurder operasjonene som skal utføres på dataene

Mens du velger en datastruktur, må du også vurdere operasjonene som skal utføres på dataene. Ulike datastrukturer optimaliserer en rekke handlinger, for eksempel sortering, søking, innsetting og sletting.

For eksempel er koblede lister bedre for handlinger som innsetting og sletting, men binære trær er best for søk og sortering. En hash-tabell kan være det beste valget hvis applikasjonen din krever samtidig innsetting og søking.

Vurder miljøet

Når du vurderer en datastruktur, må du evaluere miljøet der applikasjonen skal kjøres. Miljøet påvirker hvor godt og hvor raskt tilgjengelige datastrukturer er.

Vurder følgende faktorer når du vurderer din nåværende tilstand:

  1. Prosessorkraft: Velg datastrukturer for applikasjonene dine som fungerer godt på PC-er med lite prosessorkraft mens de kjører på plattformen. For eksempel kan enklere datastrukturer som matriser være mer passende enn trær eller grafer.
  2. Samtidighet: Du bør velge en trådsikker datastruktur som kan håndtere samtidig tilgang uten datakorrupsjon; hvis applikasjonen din kjører i et samtidig miljø, der flere tråder eller prosesser får tilgang til datastrukturen samtidig. I dette tilfellet låsefrie datastrukturer som ConcurrentLinkedQueue og ConcurrentHashMap kan være mer passende enn tradisjonelle som ArrayListand HashMap.
  3. Nettverksforsinkelse: Hvis applikasjonen din krever dataoverføring over et nettverk, må du vurdere nettverksforsinkelse mens du bestemmer deg for den beste datastrukturen. I slike situasjoner kan bruk av en datastruktur som begrenser nettverksanrop eller reduserer mengden dataoverføring bidra til å forbedre kjøringen.

Vanlige datastrukturer og deres brukstilfeller

Her er et sammendrag av flere populære datastrukturer og deres bruk.

  1. Matriser: Dette er en enkel og effektiv datastruktur som kan inneholde en serie med fast størrelse av elementer av samme datatype. For at de skal fungere ordentlig, trenger de rask, direkte tilgang til spesifikke objekter via en indeks.
  2. Koblede lister: Koblede lister er bygd opp av noder, som inneholder et element og en referanse til neste node og/eller forrige node. På grunn av deres effektive operasjoner er koblede lister best egnet i situasjoner som krever hyppig innsetting eller sletting av elementer. Tilgang til individuelle elementer etter indeks i koblede lister er imidlertid tregere sammenlignet med matriser.
  3. Køer og stabler: Stabler overholder regelen Last-In-First-Out (LIFO), der det siste elementet som er satt inn, er det første elementet som fjernes. Køer styres av First-In-First-Out (FIFO)-prinsippet der det første elementet som legges til også er det første som slettes.
  4. Hash-tabeller: Hash-tabeller er en form for datastruktur som inneholder nøkkel-verdi-par. Den beste løsningen er å bruke hashtabeller når antallet komponenter er uforutsigbart, og du trenger rask tilgang til verdiene med nøkkel.
  5. Trær: Trær er hierarkiske datastrukturer som kan lagre en gruppe elementer i et hierarki. De beste bruksområdene for binære søketrær er i hierarkiske datastrukturer der relasjonene mellom dataelementene kan representere en trelignende struktur.

Velge riktig datastruktur

Før du velger en datastruktur, bør du vurdere applikasjonens data, forpliktelser og miljø. Mens du går med valget ditt, tenk på følgende elementer:

  1. Tidskompleksitet: Ytelsen til applikasjonen din kan bli betydelig påvirket av tidskompleksiteten til datastrukturen. Hvis applikasjonen din krever hyppige søk eller gjenfinningsoperasjoner, bruk en datastruktur med redusert tidskompleksitet, som en hashtabell.
  2. Plass kompleksitet: Datastrukturens plasskompleksitet er en annen viktig faktor. Hvis programmet er minnekrevende, velg en datastruktur med mindre plasskompleksitet, for eksempel en matrise. Hvis plass ikke er et problem, kan du bruke en datastruktur med større plasskompleksitet, for eksempel et tre.
  3. Les vs. Skriv operasjoner: Hvis applikasjonen din bruker mange skriveoperasjoner, velg en datastruktur med raskere innsettingsytelse, som en hashtabell. Hvis applikasjonen krever mange leseoperasjoner, velg en datastruktur med raskere søkehastighet, for eksempel et binært søketre.
  4. Type data: Dataene du har å gjøre med kan også påvirke den valgte datastrukturen. Du kan for eksempel bruke en trebasert datastruktur hvis dataene dine er hierarkiske. Hvis du har enkle data som må åpnes tilfeldig, kan det være det beste alternativet å velge en array-basert datastruktur.
  5. Tilgjengelige biblioteker: Vurder bibliotekene som er lett tilgjengelige for datastrukturen du vurderer. Det kan være enklere å utføre og vedlikeholde hvis programmeringsspråket ditt har innebygde biblioteker tilgjengelig for en bestemt datastruktur.

Følgende Python-eksempel viser hvordan du velger den beste datastrukturen for et bestemt brukstilfelle.

Tenk på tilfellet der du utvikler en filsystemapplikasjon som må lagre og hente filer i et hierarki. Du må velge en datastruktur som effektivt kan representere denne hierarkiske strukturen og raskt utføre operasjoner som søk, innsetting og sletting.

Det kan være en god idé å bruke en trebasert datastruktur som et binært søk eller et B-tre. Hvis antallet oppføringer i hver katalog er relativt lite og treet ikke er veldig dypt, vil binært søketre fungere bra. Et B-tre ville være mer passende for større antall filer og dypere katalogstrukturer.

Nedenfor er et eksempel på et binært søketre i Python.

klasseNode:
def__i det__(selv, verdi):
 egenverdi = verdi
 self.left_child = Ingen
 self.right_child = Ingen


klasseBinarySearchTree:


def__i det__(selv):
 self.root = Ingen
defsett inn(selv, verdi):


hvis selv.rot erIngen:
 self.root = Node (verdi)


ellers:
 self._insert (verdi, self.root) 
def_sett inn(selv, verdi, gjeldende_node):


hvis verdi < gjeldende_node.verdi:
hvis gjeldende_node.venstre_barn erIngen:
 current_node.left_child = Node (verdi)


ellers:
 self._insert (verdi, current_node.left_child)
elif verdi > gjeldende_node.verdi:
hvis current_node.right_child erIngen:
 current_node.right_child = Node (verdi)
ellers:
 self._insert (verdi, current_node.right_child)


ellers:
 skrive ut("Verdi finnes allerede i treet.")
defSøk(selv, verdi):
hvis selv.rot erikkeIngen:
komme tilbake self._search (verdi, self.root)


ellers:
komme tilbakeFalsk
def_Søk(selv, verdi, gjeldende_node):


hvis verdi == gjeldende_node.verdi:
komme tilbakeekte


elif verdi < gjeldende_node.verdi og gjeldende_node.venstre_barn erikkeIngen:
komme tilbake self._search (value, current_node.left_child)


elif verdi > gjeldende_node.verdi og current_node.right_child erikkeIngen:
komme tilbake self._search (verdi, current_node.right_child)
ellers:
komme tilbakeFalsk

I denne implementeringen konstruerer du to klasser: a BinarySearchTree klasse som administrerer innsettings- og søkeoperasjoner og en Node klasse som symboliserer en node i det binære søketreet.

Mens innsettingsmetoden setter inn en ny node på riktig plassering i treet avhengig av verdien, søker søkemetoden etter en node med en spesifisert verdi. Begge operasjoners tidskompleksitet i et balansert tre er O(log n).

Velg den optimale datastrukturen

Applikasjonens hastighet og tilpasningsevne kan forbedres betydelig av datastrukturen du velger. Å ta hensyn til dataene dine, driften og miljøet ditt kan hjelpe deg med å velge den beste datastrukturen.

Betraktninger som tidskompleksitet, romkompleksitet, lese versus skriveoperasjoner, samtidighet, datatype og bibliotektilgjengelighet er viktige.

Ved å vurdere vekten av hver komponent bør du velge datastrukturen som tilfredsstiller applikasjonens behov.