At vælge den rigtige datastruktur kan gøre dit program mere effektivt. Her er en guide til at hjælpe dig med at træffe det rigtige valg.

At vælge den bedste datastruktur til dine mål kan være udfordrende med flere tilgængelige muligheder. Når du vælger en datastruktur, skal du overveje de data, du skal beskæftige dig med, de operationer, der skal udføres på dataene, og det miljø, hvor din applikation vil køre.

Forstå dine data

Det er afgørende at forstå de data, du vil beskæftige dig med, før du vælger en datastruktur. Fælles datastrukturer der arbejder med forskellige datatyper, omfatter arrays, linkede lister, træer, grafer og hashtabeller.

For eksempel, når du skal have adgang til elementer tilfældigt fra dine data, kan arrays være det bedste valg. Hvis du konstant skal tilføje eller slette elementer fra en liste, og listestørrelsen også kan ændre sig, kan linkede lister være særligt nyttige.

Når du effektivt skal gemme flere niveauer af data, såsom registreringsstrukturer, og udføre operationer som søgning og sortering, så er træer nyttige.

instagram viewer

Når du skal beskrive interaktioner mellem enheder, såsom dem i sociale netværk, og udføre operationer såsom korteste vej og forbindelse, så foretrækkes Grafer. Hash-tabeller er nyttige til hurtige nøgleopslag.

Overvej de operationer, der skal udføres på dataene

Mens du vælger en datastruktur, skal du også overveje de operationer, der skal udføres på dataene. Forskellige datastrukturer optimerer adskillige handlinger, såsom sortering, søgning, indsættelse og sletning.

For eksempel er linkede lister bedre til handlinger som indsættelse og sletning, men binære træer er bedst til søgning og sortering. En hash-tabel kan være det bedste valg, hvis din applikation kræver samtidig indsættelse og søgning.

Vurder miljøet

Når du overvejer en datastruktur, skal du evaluere det miljø, som applikationen skal køre i. Miljøet påvirker, hvor godt og hvor hurtigt tilgængelige datastrukturer er.

Overvej følgende faktorer, når du vurderer din nuværende tilstand:

  1. Bearbejdningskraft: Vælg datastrukturer til dine applikationer, der fungerer godt på pc'er med ringe processorkraft, mens de kører på platformen. For eksempel kunne enklere datastrukturer som arrays være mere passende end træer eller grafer.
  2. Samtidighed: Du bør vælge en trådsikker datastruktur, der kan håndtere samtidig adgang uden datakorruption; hvis din applikation kører i et samtidig miljø, hvor flere tråde eller processer får adgang til datastrukturen samtidigt. I dette tilfælde låsefri datastrukturer som ConcurrentLinkedQueue og ConcurrentHashMap kan være mere passende end traditionelle som ArrayListand HashMap.
  3. Netværksforsinkelse: Hvis din applikation kræver dataoverførsel over et netværk, skal du overveje netværksforsinkelse, mens du beslutter dig for den bedste datastruktur. I sådanne situationer kan brug af en datastruktur, der begrænser netværksopkald eller reducerer mængden af ​​dataoverførsel, hjælpe med at forbedre eksekveringen.

Fælles datastrukturer og deres anvendelsestilfælde

Her er en oversigt over flere populære datastrukturer og deres brug.

  1. Arrays: Dette er en enkel og effektiv datastruktur, der kan indeholde en serie af elementer i fast størrelse af samme datatype. For at de kan fungere korrekt, har de brug for hurtig, direkte adgang til specifikke objekter via et indeks.
  2. Sammenkædede lister: Sammenkædede lister er opbygget af noder, som indeholder et element og en reference til den næste node og/eller forrige node. På grund af deres effektive operationer er linkede lister bedst egnede i situationer, der kræver hyppig elementindsættelse eller sletning. Adgang til individuelle elementer efter indeks i sammenkædede lister er dog langsommere sammenlignet med arrays.
  3. Køer og stakke: Stabler overholder reglen Last-In-First-Out (LIFO), hvor det sidst indsatte element er det første element, der fjernes. Køer er styret af First-In-First-Out-princippet (FIFO). hvor det første tilføjede element også er det første slettede.
  4. Hash tabeller: Hash-tabeller er en form for datastruktur, der indeholder nøgle-værdi-par. Den bedste løsning er at bruge hash-tabeller, når antallet af komponenter er uforudsigeligt, og du har brug for hurtig adgang til værdierne med nøgle.
  5. Træer: Træer er hierarkiske datastrukturer, der kan gemme en gruppe af elementer i et hierarki. De bedste anvendelser til binære søgetræer er i hierarkiske datastrukturer, hvor relationerne mellem dataelementerne kan repræsentere en trælignende struktur.

Valg af den rigtige datastruktur

Inden du vælger en datastruktur, skal du overveje din applikations data, forpligtelser og miljø. Mens du går med dit valg, skal du tænke på følgende elementer:

  1. Tidskompleksitet: Ydeevnen af ​​din applikation kan blive væsentligt påvirket af tidskompleksiteten af ​​din datastruktur. Hvis din applikation kræver hyppige søge- eller genfindingsoperationer, skal du bruge en datastruktur med reduceret tidskompleksitet, som en hash-tabel.
  2. Rumkompleksitet: Datastrukturens pladskompleksitet er en anden vigtig overvejelse. Hvis din applikation er hukommelsesintensiv, skal du vælge en datastruktur med mindre pladskompleksitet, såsom et array. Hvis plads ikke er et problem, kan du bruge en datastruktur med større pladskompleksitet, såsom et træ.
  3. Læs vs. Skriv operationer: Hvis din applikation bruger mange skriveoperationer, skal du vælge en datastruktur med en hurtigere indsættelsesydelse, f.eks. en hash-tabel. Hvis din applikation kræver mange læseoperationer, skal du vælge en datastruktur med en hurtigere søgehastighed, såsom et binært søgetræ.
  4. Type af data: De data, du har at gøre med, kan også påvirke din valgte datastruktur. For eksempel kan du bruge en træbaseret datastruktur, hvis dine data er hierarkiske. Hvis du har simple data, der skal tilgås tilfældigt, kan det være den bedste løsning at vælge en array-baseret datastruktur.
  5. Tilgængelige biblioteker: Overvej de biblioteker, der er let tilgængelige for den datastruktur, du overvejer. Det kunne være lettere at udføre og vedligeholde, hvis dit programmeringssprog har indbyggede biblioteker til rådighed for en bestemt datastruktur.

Det følgende Python-eksempel demonstrerer, hvordan man vælger den bedste datastruktur til en bestemt brugssag.

Overvej det tilfælde, hvor du udvikler en filsystemapplikation, der skal gemme og hente filer i et hierarki. Du skal vælge en datastruktur, der effektivt kan repræsentere denne hierarkiske struktur og hurtigt udføre operationer som søgning, indsættelse og sletning.

Det kunne være en god idé at bruge en træbaseret datastruktur som en binær søgning eller et B-træ. Hvis antallet af poster i hver mappe er relativt lille, og træet ikke er særlig dybt, ville binært søgetræ fungere godt. Et B-træ ville være mere passende til et større antal filer og dybere mappestrukturer.

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

klasseNode:
def__i det__(selv, værdi):
 selv.værdi = værdi
 self.left_child = Ingen
 self.right_child = Ingen


klasseBinarySearchTree:


def__i det__(selv):
 self.root = Ingen
defindsætte(selv, værdi):


hvis selv.rod erIngen:
 self.root = Node (værdi)


andet:
 self._insert (værdi, self.root) 
def_indsæt(selv, værdi, nuværende_node):


hvis værdi < nuværende_node.værdi:
hvis current_node.left_child erIngen:
 current_node.left_child = Node (værdi)


andet:
 self._insert (værdi, current_node.left_child)
elif værdi > nuværende_node.værdi:
hvis current_node.right_child erIngen:
 current_node.right_child = Node (værdi)
andet:
 self._insert (værdi, current_node.right_child)


andet:
 Print("Værdien findes allerede i træet.")
defSøg(selv, værdi):
hvis selv.rod erikkeIngen:
Vend tilbage self._search (værdi, self.root)


andet:
Vend tilbageFalsk
def_Søg(selv, værdi, nuværende_node):


hvis værdi == nuværende_node.værdi:
Vend tilbageRigtigt


elif værdi < nuværende_node.værdi og current_node.left_child erikkeIngen:
Vend tilbage self._search (værdi, current_node.left_child)


elif værdi > aktuel_node.værdi og current_node.right_child erikkeIngen:
Vend tilbage self._search (værdi, current_node.right_child)
andet:
Vend tilbageFalsk

I denne implementering konstruerer du to klasser: a BinarySearchTree klasse, der styrer indsættelses- og søgeoperationer og en Node klasse, der symboliserer en node i det binære søgetræ.

Mens indsættelsesmetoden indsætter en ny node på den passende placering i træet afhængigt af dens værdi, søger søgemetoden efter en node med en specificeret værdi. Begge operationers tidskompleksitet i et balanceret træ er O(log n).

Vælg den optimale datastruktur

Din applikations hastighed og tilpasningsevne kan forbedres væsentligt af den datastruktur, du har valgt. Ved at tage hensyn til dine data, din drift og dit miljø kan du hjælpe dig med at vælge den bedste datastruktur.

Overvejelser som tidskompleksitet, rumkompleksitet, læse versus skriveoperationer, samtidighed, datatype og biblioteks tilgængelighed er vigtige.

Ved at vurdere vægten af ​​hver komponent bør du vælge den datastruktur, der opfylder din applikations behov.