Att välja rätt datastruktur kan göra ditt program mer effektivt. Här är en guide som hjälper dig att göra rätt val.

Att välja den bästa datastrukturen för dina mål kan vara utmanande med flera tillgängliga alternativ. När du väljer en datastruktur, överväga vilken data du kommer att hantera, de operationer som ska utföras på datan och miljön där din applikation kommer att köras.

Förstå dina uppgifter

Det är viktigt att förstå vilken data du kommer att hantera innan du väljer en datastruktur. Vanliga datastrukturer som fungerar med olika datatyper inkluderar arrayer, länkade listor, träd, grafer och hashtabeller.

Till exempel, när du behöver komma åt element slumpmässigt från dina data, kan arrayer vara det bästa valet. Om du ständigt behöver lägga till eller ta bort element från en lista, och liststorleken också kan ändras, kan länkade listor vara särskilt användbara.

När du effektivt behöver lagra flera nivåer av data, såsom poststrukturer, och utföra operationer som sökning och sortering, då är träd användbara.

instagram viewer

När du behöver beskriva interaktioner mellan enheter, som de i sociala nätverk, och utföra operationer som kortaste vägen och anslutning, är grafer att föredra. Hash-tabeller är användbara för snabba nyckeluppslagningar.

Överväg de operationer som ska utföras på data

När du väljer en datastruktur måste du också ta hänsyn till de operationer som ska utföras på data. Olika datastrukturer optimerar många åtgärder, såsom sortering, sökning, infogning och radering.

Till exempel är länkade listor bättre för åtgärder som infogning och borttagning, men binära träd är bäst för sökning och sortering. En hashtabell kan vara det bästa valet om din applikation kräver samtidig infogning och sökning.

Utvärdera miljön

När du överväger en datastruktur måste du utvärdera miljön där applikationen kommer att köras. Miljön påverkar hur bra och hur snabbt tillgängliga datastrukturer är.

Tänk på följande faktorer när du utvärderar ditt nuvarande tillstånd:

  1. Process kraft: Välj datastrukturer för dina applikationer som fungerar bra på datorer med liten processorkraft när de körs på plattformen. Enklare datastrukturer som arrayer kan till exempel vara mer lämpliga än träd eller grafer.
  2. Samtidighet: Du bör välja en trådsäker datastruktur som kan hantera samtidig åtkomst utan datakorruption; om din applikation körs i en samtidig miljö, där flera trådar eller processer kommer åt datastrukturen samtidigt. I det här fallet låsfria datastrukturer som ConcurrentLinkedQueue och ConcurrentHashMap kan vara mer lämpliga än traditionella sådana som ArrayListand HashMap.
  3. Nätverkslatens: Om din applikation kräver dataöverföring över ett nätverk måste du ta hänsyn till nätverkslatens när du bestämmer dig för den bästa datastrukturen. I sådana situationer kan användning av en datastruktur som begränsar nätverkssamtal eller minskar mängden dataöverföring bidra till att förbättra exekveringen.

Vanliga datastrukturer och deras användningsfall

Här är en sammanfattning av flera populära datastrukturer och deras användning.

  1. Matriser: Detta är en enkel och effektiv datastruktur som kan innehålla en serie av element med fast storlek av samma datatyp. För att de ska fungera korrekt behöver de snabb, direkt tillgång till specifika objekt via ett index.
  2. Länkade listor: Länkade listor är uppbyggda av noder, som innehåller ett element och en referens till nästa nod och/eller föregående nod. På grund av deras effektiva operationer är länkade listor bäst lämpade i situationer som kräver frekvent infogning eller radering av element. Det går dock långsammare att komma åt enskilda element via index i länkade listor jämfört med arrayer.
  3. Köer och travar: Stackar följer regeln Last-In-First-Out (LIFO), där det sista objektet som infogas är det första objektet som tas bort. Köer styrs av First-In-First-Out-principen (FIFO). där det första elementet som läggs till också är det första som tas bort.
  4. Hash tabeller: Hashtabeller är en form av datastruktur som innehåller nyckel-värdepar. Den bästa lösningen är att använda hashtabeller när antalet komponenter är oförutsägbart och du behöver snabb tillgång till värdena med nyckel.
  5. Träd: Träd är hierarkiska datastrukturer som kan lagra en grupp av element i en hierarki. De bästa användningsområdena för binära sökträd är i hierarkiska datastrukturer där relationerna mellan dataposterna kan representera en trädliknande struktur.

Att välja rätt datastruktur

Innan du väljer en datastruktur, överväg din applikations data, skyldigheter och miljö. När du gör ditt val, tänk på följande faktorer:

  1. Tidskomplexitet: Prestandan för din applikation kan påverkas avsevärt av tidskomplexiteten i din datastruktur. Om din applikation kräver frekventa sökningar eller hämtning, använd en datastruktur med reducerad tidskomplexitet, som en hashtabell.
  2. Rymdkomplexitet: Datastrukturens rymdkomplexitet är en annan viktig faktor. Om din applikation är minneskrävande, välj en datastruktur med mindre utrymmeskomplexitet, till exempel en array. Om utrymme inte är ett problem kan du använda en datastruktur med större rymdkomplexitet, till exempel ett träd.
  3. Läs vs. Skriv operationer: Om din applikation använder många skrivoperationer, välj en datastruktur med snabbare insättningsprestanda, som en hashtabell. Om din applikation kräver många läsoperationer, välj en datastruktur med snabbare sökhastighet, till exempel ett binärt sökträd.
  4. Typ av data: Datan du har att göra med kan också påverka din valda datastruktur. Du kan till exempel använda en trädbaserad datastruktur om dina data är hierarkiska. Om du har enkla data som behöver nås slumpmässigt kan det vara det bästa alternativet att välja en arraybaserad datastruktur.
  5. Tillgängliga bibliotek: Tänk på de bibliotek som är lättillgängliga för den datastruktur du funderar på. Det kan vara lättare att köra och underhålla om ditt programmeringsspråk har inbyggda bibliotek tillgängliga för en viss datastruktur.

Följande Python-exempel visar hur man väljer den bästa datastrukturen för ett visst användningsfall.

Tänk på fallet där du utvecklar en filsystemapplikation som måste lagra och hämta filer i en hierarki. Du måste välja en datastruktur som effektivt kan representera denna hierarkiska struktur och snabbt utföra operationer som sökning, infogning och radering.

Det kan vara en bra idé att använda en trädbaserad datastruktur som en binär sökning eller ett B-träd. Om antalet poster i varje katalog är relativt litet och trädet inte är särskilt djupt skulle binärt sökträd fungera bra. Ett B-träd skulle vara mer lämpligt för större antal filer och djupare katalogstrukturer.

Nedan är ett exempel på ett binärt sökträd i Python.

klassNod:
def__i det__(själv, värde):
 själv.värde = värde
 self.left_child = Ingen
 self.right_child = Ingen


klassBinarySearchTree:


def__i det__(själv):
 self.root = Ingen
defFöra in(själv, värde):


om själv.rot ärIngen:
 self.root = Nod (värde)


annan:
 self._insert (värde, self.root) 
def_Föra in(själv, värde, aktuell_nod):


om värde < aktuell_nod.värde:
om current_node.left_child ärIngen:
 current_node.left_child = Nod (värde)


annan:
 self._insert (value, current_node.left_child)
elif värde > aktuell_nod.värde:
om current_node.right_child ärIngen:
 current_node.right_child = Nod (värde)
annan:
 self._insert (värde, current_node.right_child)


annan:
 skriva ut("Värde finns redan i trädet.")
defSök(själv, värde):
om själv.rot ärinteIngen:
lämna tillbaka self._search (värde, self.root)


annan:
lämna tillbakaFalsk
def_Sök(själv, värde, aktuell_nod):


om värde == aktuell_nod.värde:
lämna tillbakaSann


elif värde < aktuell_nod.värde och current_node.left_child ärinteIngen:
lämna tillbaka self._search (value, current_node.left_child)


elif värde > aktuell_nod.värde och current_node.right_child ärinteIngen:
lämna tillbaka self._search (value, current_node.right_child)
annan:
lämna tillbakaFalsk

I den här implementeringen konstruerar du två klasser: a BinarySearchTree klass som hanterar infogning och sökoperationer och en Nod klass som symboliserar en nod i det binära sökträdet.

Medan infogningsmetoden infogar en ny nod på lämplig plats i trädet beroende på dess värde, söker sökmetoden efter en nod med ett specificerat värde. Båda operationernas tidskomplexitet i ett balanserat träd är O(log n).

Välj den optimala datastrukturen

Din applikations hastighet och anpassningsförmåga kan förbättras avsevärt av den datastruktur du valt. Att ta hänsyn till din data, din verksamhet och din miljö kan hjälpa dig att välja den bästa datastrukturen.

Överväganden som tidskomplexitet, rymdkomplexitet, läs- och skrivoperationer, samtidighet, datatyp och bibliotekstillgänglighet är viktiga.

Genom att bedöma vikten av varje komponent bör du välja den datastruktur som uppfyller din applikations behov.