Dynamisk array

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 31 mars 2015; verifiering kräver 51 redigeringar .

En array kallas dynamisk , vars storlek kan ändras under körningen av programmet. Möjligheten att ändra storleken skiljer en dynamisk array från en statisk, vars storlek ställs in när programmet kompileras. För att ändra storleken på en dynamisk array måste ett programmeringsspråk som stöder sådana arrayer tillhandahålla en inbyggd funktion eller operatör. Dynamiska arrayer tillåter mer flexibelt arbete med data, eftersom de tillåter att inte förutsäga de lagrade datavolymerna, utan att justera storleken på arrayen i enlighet med de faktiskt nödvändiga volymerna.

Ibland är dynamiska arrayer också arrayer med variabel längd , vars storlek inte är fixerad under kompilering, utan ställs in när arrayen skapas eller initieras under programkörning. De skiljer sig från "riktiga" dynamiska arrayer genom att de inte tillhandahåller automatisk storleksändring med bevarande av innehåll, så programmeraren måste implementera en sådan möjlighet om det behövs.

Stöd i programmeringsspråk

Dynamiska arrayer kan stödjas antingen på syntaxnivån för själva programmeringsspråket eller på systembiblioteksnivån. Beskrivningen av en dynamisk array kan skilja sig syntaktisk från beskrivningen av en statisk, men den kan vara densamma. I det andra fallet är som regel alla arrayer i språket potentiellt dynamiska, och det är upp till programmeraren att använda denna egenskap i varje enskilt fall. När de stöds av dynamiska arrayer genom systembibliotek, implementeras de vanligtvis som klasser (i OOP - bemärkelse ) eller generiska typer (så kallade "mallar" eller "generics"); array-deklarationen i detta fall är en instansiering av en klass eller en instansiering av en generisk typ. Beroende på språket kan dynamiska arrayer endast vara endimensionella arrayer eller ha två eller flera dimensioner.

Stöd för dynamiska arrayer innebär obligatorisk närvaro av en inbyggd operation för att bestämma den aktuella storleken på en array. Den initiala storleken på en dynamisk array är antingen lika med noll eller ställs in under beskrivning eller initialisering. Ytterligare storleksändring utförs av en speciell inbyggd operation (procedur). På vissa språk (t.ex. JavaScript , Lua ) sker arrayexpansion automatiskt när ett försök görs att skriva till en icke-existerande cell.

Implementering

För att arrayer ska kunna ändras dynamiskt måste implementeringen hitta en "gyllene medelväg" mellan flera motstridiga krav.

Minneseffektiv – Implementeringen bör inte resultera i betydande minneskostnader.
Prestandaeffektivitet , som inkluderar:
- minimal overhead för att ändra storleken på arrayen;
- sparar, om möjligt, en konstant läs/skrivåtkomsttid till arrayelement.
Lågnivåkompatibilitet med vanliga statiska arrayer . Till exempel kan en förutsättning för att använda en dynamisk array i anrop till operativsystemets API-funktioner vara att arrayelementen måste placeras i ett sammanhängande block av fysiskt RAM i den ordning som motsvarar arrayindexeringen. Om detta krav inte uppfylls kan dynamiska arrayer inte användas tillsammans med lågnivåkod.

Beroende på prioriteringen av vissa krav väljs den metod för implementering som uppfyller dem.

Arrayer med variabel längd

Implementeringen av arrayer med variabel längd skiljer sig lite från implementeringen av vanliga statiska arrayer. En array av element av typ T med variabel längd lagras vanligtvis i ett sammanhängande RAM-block av storlek , där N är antalet element som specificeras när arrayen beskrivs (skapas). Det vill säga att deklarationen av en array med variabel längd i själva verket helt enkelt maskerar den dynamiska allokeringen av minnet. Skillnaden kan vara att (till exempel, som i C99 och senare) en array med variabel längd tilldelas minne på stacken, som andra automatiska variabler, medan det typiska sättet för dynamisk minnesallokering (i C - funktion ) allokerar minne på hög . Dessutom, för en array med variabel längd, genererar kompilatorn vanligtvis automatiskt minnesavallokeringskod när den deklarerade arrayen går utanför räckvidden. $sizeof(T)\cdot N$ malloc

Flytta en array i minnet

Det vanligaste för typiska procedurkompilerade språk är att implementera storleksändring av en array genom att flytta den i heapminnet.

Ett fragment av RAM tilldelas för arrayen, vars storlek är större än den nödvändiga så kallade. logisk storlek (storlek eller längd). Antalet element som faktiskt kan placeras i detta minne kallas kapaciteten för den dynamiska arrayen. Den aktuella längden av arrayen lagras i en separat räknare. Det kan användas för att bestämma den aktuella storleken, såväl som för att kontrollera arrayspill, om språket stöder sådan kontroll. Således är i verkligheten en dynamisk array en array av en fast storlek, i vilken endast en del av cellerna är upptagna.
Kommandot för att öka storleken på arrayen, om den nya storleken inte överstiger kapaciteten, ändrar helt enkelt arraylängden till önskad storlek. Det finns ingen förändring i själva arrayen.
En ökningsinstruktion där den nya storleken överskrider kapaciteten gör att arrayen flyttas till minnet:

ett nytt RAM-fragment tilldelas, vars storlek överstiger arrayens storlek;
innehållet i arrayen kopieras till det nyligen allokerade minnet;
arrayens storlek och kapacitet uppdateras;
i tjänstestrukturen som lagrar arrayparametrarna ändras värdet på datapekaren till en ny;
kommandot för att frigöra RAM-fragmentet som tidigare tilldelats för arrayen startas; om språket stöder automatisk minneshantering , kvarstår frigörandet av minne som tidigare allokerats för arrayen hos sopsamlaren.

Kommandot för att minska storleken på en array kan leda till att den flyttas i minnet om, som ett resultat av dess exekvering, andelen upptagna celler i arrayen faller under ett visst värde. Förflyttning i detta fall utförs enligt samma schema som i fallet med kommandot för att öka arrayen.

Denna implementering är den mest effektiva när det gäller åtkomsthastighet till redan allokerade arrayceller. Dessutom ger den konstant åtkomsttid till alla element, oavsett dess index. Den extra omkostnaden för storleksändringsoperationer kan dock vara betydande. Värdet av dessa kostnader beror på parametrarna för arrayrörelsealgoritmen.

Den initiala kapaciteten och ökningen i kapacitet när storleken ökar. Det kan anges antingen som ett relativt värde (en viss bråkdel av den logiska längden av arrayen), eller som ett absolut inkrement över den nödvändiga arraylängden. Ju större dessa parametrar är, desto senare, med samma arrayfyllningsläge, kommer nästa drag att krävas, men desto mer minne kommer potentiellt att förbli oanvänt. Att utöka arrayen med valfri konstant faktor garanterar att infogning av n element tar O(n) tid, vilket innebär att varje infogning tar en specifik, definierad tid. Det numeriska värdet av denna koefficient leder till olika indikatorer: den genomsnittliga insättningstiden för en operation är a/(a-1), medan antalet bortkastade celler är (a-1)n. Värdet på denna konstant i olika applikationer och bibliotek kan vara olika: många läroböcker använder värdet 2, men Java-språkimplementeringen av ArrayList använder en faktor på 3/2, i vissa andra fall använder de a=9/8.
Minsta kapacitet. Vanligtvis inställt av effektivitetsskäl, för att inte förlora prestanda när små arrayer ändras ofta. I praktiken innebär inställningen att alla dynamiska arrayer som är mindre än minimikapaciteten faktiskt kommer att slösa med minne.
Minsta fyllningsprocent för arrayen. Anger när omlokalisering kommer att ske efter att arrayen har minskats i storlek. Ju större detta värde är, desto oftare kommer rörelsen att inträffa när arraystorleken minskar. Ju mindre det är, desto mer minne förblir upptaget men används inte när arraystorleken minskas.

Det finns olika uppskattningar av de optimala värdena för parametrarna för den rörliga algoritmen, men från allmänna överväganden är det klart att ingen av metoderna för att bestämma dem garanterar maximal effektivitet i alla fall, och för alla är det möjligt att välja en algoritm för att arbeta med en array, där förflyttningen blir ineffektiv. För att kompensera för de negativa effekterna har många språk som stöder dynamiska arrayer ytterligare parametrar i array-öknings-/minskningskommandona som låter dig styra arraykapaciteten direkt. Om programmeraren med säkerhet vet till vilken storlek arrayen kommer att öka/minska som ett resultat av den eller den operationen, och hur arrayen kommer att bearbetas i framtiden, kan han direkt specificera den slutliga kapaciteten som krävs i resize-kommandot och därmed undvika ett stort antal meningslösa rörelser.

Andra dynamiska allokeringsalgoritmer

Det finns många algoritmer för att implementera dynamiska arrayer, förutom ovanstående. Således är det möjligt att implementera andra olika datastrukturer med hjälp av dynamiska minnesceller sammankopplade med länkar. De flesta av dessa metoder ger en fördel i vissa specifika förhållanden, men ger antingen inte konstant åtkomsttid eller är inkompatibla med statiska arrayer och kan därför inte fungera med lågnivåkod.

Användning

Dynamiska arrayer används för att bearbeta uppsättningar av homogena data vars storlek inte är känd exakt vid tidpunkten för programmets skrivning, men som potentiellt kan passa i tillgängligt minne. Utan användning av dynamiska arrayer reduceras lösningen av sådana problem till en av följande strategier:

allokering av en statisk array av stor storlek, uppenbarligen tillräcklig för fullständig dataplacering;
använda en statisk array som en buffert i vilken data laddas i delar;
användning av andra dynamiska datastrukturer (till exempel listor).

Det första alternativet är endast tillämpligt när datauppsättningens storlek ändras inom ett litet, hårt begränsat intervall (till exempel i ordbehandling är en gräns på 1000 tecken per rad helt acceptabel). Annars kommer valet av en liten array att begränsa programmets funktionalitet, och en stor (så att den säkert räcker för alla indata) kommer att leda till ineffektiv användning av minne. Bearbetningsbuffring komplicerar algoritmen, och andra dynamiska strukturer i uppgifter att bearbeta stora sekvenser av enkla data kan inte jämföras med en array när det gäller effektivitet.

Användningen av dynamiska arrayer gör att du kan allokera exakt så mycket minne som verkligen är nödvändigt (omedelbart, om uppgiften låter dig bestämma mängden innan du laddar data, eller under laddning, utöka arrayen efter behov), ladda all data till en array och bearbeta dem enhetligt. Men denna strategi har också nackdelar:

minskning i hastighet på grund av overheadkostnader för att ändra storleken på en dynamisk array;
potentiell minskning av tillförlitlighet: med en extremt stor mängd indata kan ett försök att öka arrayen till lämplig storlek leda till en plötslig betydande nedgång eller till och med misslyckande i programmet på grund av brist på ledigt minne.

I allmänhet kan det ses att stödet för dynamiska arrayer ökar bekvämligheten med utveckling, men befriar inte programmeraren från behovet av att utvärdera programmets minnesbehov; det kräver också att man förstår egenskaperna hos en specifik implementering av dynamiska arrayer och matchar databehandlingsalgoritmer med dessa funktioner.

Exempel

Pascal

Dynamiska arrayer stöds av Delphi , FreePascal , men inte av Turbo Pascal .

var byteArray : Array of Byte ; // Endimensionell array multiArray : Array av Array av sträng ; // Multidimensional array ... begin ... // Ställ in storleken på en endimensionell array till n element SetLength ( byteArray , n ) ; // Tillgång till en dynamisk array liknar åtkomst till en vanlig. // Indexering börjar alltid från noll, index är alltid heltal. byteArray [ 0 ] := 10 ; // Ändra storlek till m element. SetLength ( byteArray , m ) ; ... // Ställ in storleken på en tvådimensionell array till X*Y element SetLength ( multiArray , X , Y ) ; multiArray [ 7 , 35 ] := 'ru.wikipedia.org' ; ... slut .

Xi

Det finns inga dynamiska arrayer i själva C-språket, men standardbiblioteksfunktionerna malloc, freeoch realloclåter dig implementera en array med variabel storlek:

int * mas = ( int * ) malloc ( storleken på ( int ) * n ); // Skapa en matris med n element av typen int ... mas = ( int * ) realloc ( mas , storlek på ( int ) * m ); // Ändra storleken på arrayen från n till m, behåll innehållet ... fri ( mas ); // Frigör minne efter att ha använt arrayen

Nackdelen med detta tillvägagångssätt är behovet av att beräkna storleken på det allokerade minnet, tillämpa en explicit typkonvertering och noggrant övervaka matrisens livslängd (som alltid är fallet med dynamiskt allokerat minne i C).

En multidimensionell dynamisk array kan skapas som en array av pekare till arrayer:

int ** A = ( int ** ) malloc ( N * storleken på ( int * )); for ( int i = 0 ; i < N ; i ++ ) { A [ i ] = ( int * ) malloc ( M * storleken på ( int )); }

Emellertid komplicerar ökningen i dimension avsevärt procedurerna för att skapa en array och frigöra minne efter att användningen är klar. Uppgiften att ändra storlek på en array längs en eller flera koordinater blir ännu mer komplicerad.

Vissa C-kompilatorer tillhandahåller en icke-standardiserad biblioteksfunktion void *alloca(size_t size)som gör arbetet med dynamiska arrayer något lättare. Denna funktion allokerar minne inte på högen, som malloc, utan på högen, och detta minne frigörs automatiskt när operatören nås return. Det vill säga när en dynamisk array allokeras av denna funktion behöver den inte raderas manuellt, men en sådan array kan inte returneras från funktionen till anropspunkten.

Sedan versionen av C99-standarden har arrayer med variabel längd introducerats i språket. I den vanliga syntaxen för att deklarera en C-matris, i stället för storleken på matrisen, kan inte bara en konstant utan också en variabel av heltalstyp anges:

void func ( int arraySize ) { intmas [ arraySize ] ; // Beskrivning av en array med variabel längd för ( int i = 0 ; i < arraySize ; ++ i ) { mas [ i ] = anotherFunc ( i ); // Refererar till matriselement } ... }

En array med variabel längd kan ställas in till valfri storlek vid skapandet. Minnet för det allokeras på stacken. En array med variabel längd existerar tills den lämnar omfattningen där den deklarerades, varefter dess minne automatiskt frigörs. Som i föregående fall kan en array med variabel längd inte returneras från en funktion till den som ringer.

C++

Standardbiblioteket tillhandahåller en mallklass std::vector[1] som implementerar funktionen hos en dynamisk array:

// Deklarera en array mas, som initialt innehåller talen 1 - 5: std :: vektor < int > mas = { 1 , 2 , 3 , 4 , 5 }; mas . reserv ( 100 ); // Reservera lagringsutrymme för minst 100 artiklar utan att ändra den faktiska storleken. Innehållet förblir detsamma. mas . ändra storlek ( 50 ); // Ange explicit storlek till exakt 50 element. Saknade element kommer att få "default"-värdet, extra element kommer att tas bort. mas [ i ] = i ; // Tilldela det i'te elementet värdet i mas . push_back ( 100 ); // Lägg till ett element i slutet av arrayen int x = mas . tillbaka (); // Få tillgång till det sista elementet, i detta exempel x == 100 mas . pop_back (); // Ta bort det sista elementet std :: cout << mas . storlek () << " " << mas . kapacitet () << " \n " ; // Visningskapacitet och verklig storlek auto mas2 = mas ; // Variabel mas2 innehåller en komplett kopia av mas

std::vectorhar många metoder och operatorer, av vilka några visas i exemplet ovan. De låter dig komma åt genom index, ändra storleken på arrayen i valfri riktning, använda den som en stack, skriva ett nytt värde till en godtycklig position i arrayen (med en förskjutning av de återstående elementen) och generellt stödja semantiken av värdetypen : kopiera, byta, flytta, överföra i en funktion och returnera, elementmässigt jämföra med ett annat objekt av samma typ. Hanterad är inte bara den faktiska storleken, utan också kapaciteten, vilket gör att du kan optimera processen för minnesallokering.

std::vectorimplementerar RAII- principen : äger sina underobjekt, allokerar och frigör minne och anropar konstruktörer/destruktörer korrekt.

C++-standarden kräver en implementering för att uppfylla följande villkor:

alla element i arrayen måste lagras i en rad i ordning med ökande index i ett integrerat block av RAM;
en konstant åtkomsttid till ett godtyckligt element måste garanteras.

Lågnivåarbete med dynamiskt minne kan implementeras med medel som ärvts från förfäderspråket , men för att säkerställa typsäkerhet och uppfylla kraven i objektmodellen rekommenderas det att allokera minne för arrayer med hjälp av språkspecifika operatorer new []och delete []:

// Tilldela minne för en int-matris med längden n int * mas = new int [ n ]; ... // Frigör arrayminnet radera [] mas ;

Detta tillåter dig bland annat att omdefiniera operatörer för new []användardefinierade delete []typer och därmed implementera dina egna minnesallokeringsscheman.

I modern C++ är manuell minneshantering en viktig grund för att implementera mallbehållare, men det ger betydande svårigheter även för erfarna programmerare och rekommenderas inte för användning i applikationskod. [2] [3]

Anteckningar

↑ std::vector - cppreference.com . Hämtad 16 oktober 2021. Arkiverad från originalet 28 juni 2011. (obestämd)
↑ C++ Core Guidelines: R.1: Hantera resurser automatiskt med hjälp av resurshandtag och RAII (Resource Acquisition Is Initialization) . Hämtad 16 oktober 2021. Arkiverad från originalet 8 februari 2020. (obestämd)
↑ C++ Core Guidelines: R.11: Undvik att anropa ny och ta bort explicit . Hämtad 16 oktober 2021. Arkiverad från originalet 8 februari 2020. (obestämd)

Data struktur
Listor	array enbart länkad lista dubbelt länkad lista Passlista
Träd	B-träd Binärt sökträd AVL-träd Röd-svart träd högen
Räknar	Riktad graf Riktad acyklisk graf Binärt beslutsdiagram Hypergraf
Övrig	Hashbord Stack