Array-ul este o colecție de elemente similare care alocă spațiu continuu în memorie şi poate fi accesat prin index. Array-urile sunt frecvent utilizate în programare pentru a stoca şi procesa datele eficient, ceea ce le face un concept foarte important de înteles pentru orice developer. Ele pot fi unidimensionale (array linear) sau multidimensionale (matrici). În acest articol vor fi analizate asimptotic operațiunile pe array-uri statice şi dinamice unidimensionale.
În informatică analiza asimptotică este în general folosită pentru a analiza eficiența în timp sau spațiu a unui algoritm şi de a-i evalua performanța cu cât datele de intrare cresc spre infinit. În general aceste date de intrare sunt notate cu “n”.
În analiza asimptotică sunt folosite 3 notații pentru a descrie complexitatea în timp sau spațiu:
Big O notation: Oferă limita superioară a ratei de creștere a complexității în timp sau spațiu, indicând scenariul cel mai rău: timpul şi spațiul maxim necesar pe măsură ce dimensiunea datelor de intrare cresc.
Omega notation: Oferă limita inferioară a ratei de creștere a complexității în timp sau spațiu, indicând scenariul cel mai bun: timpul şi spațiul minim necesar pe măsură ce dimensiunea datelor de intrare cresc.
Theta notation: Oferă şi limita superioară şi cea inferioară la runtime şi descrie rata exactă de creştere a complexitătii în timp sau spațiu, care este esențială pentru compararea diferiților algoritmi pentru a-l alege pe cel mai eficient pentru o anumită problemă.
Static array
Array-ul static este o colecție de elemente similare care alocă spațiu continuu şi dimensiune fixă în zona de memorie. Alocarea de memorie este fixată la compile time şi nu se schimbă la runtime.
Accesare
Accesarea unui singur element dintr-un array folosing accesul direct (index-ul său) este o operațiune în timp constant O(1), datorită locației fixe din memorie a fiecărui element. Acest lucru o face o operațiune extrem de eficientă, care nu depinde de dimensiunea array-ului.
Căutare
Pentru a căuta un element într-un array se va efectua iterarea fiecărui element din array până se găseşte valoarea căutată.
În cel mai bun caz, elementul căutat se află la index-ul 0, iar această operațiune va fi O(1).
În cazul cel mai rău, elementul căutat se află la finalul array-ului şi vom avea "n" elemente căutate până îl găsim - O(n).
Analiza asimptotică se realizează pentru cazul cel mai rău, şansa ca elementul căutat să fie pe prima poziție din array fiind extrem de mică, deci căutarea unui element se realizează în timp liniar - O(n).
Inserare
Pentru analiza adăugarii unui element vom analiza următoarele situații:
A. Inserarea elementului la sfârşitul array-ului
B. Inserarea elementului la începutul array-ului
C. Inserarea elementului în mijlocul array-ului
A. Inserarea elementului la sfârşitul array-ului
Datorită faptului că spațiul alocat la inițializarea array-ului este fix, în momentul în care un nou element este inserat la final, vom primi eroarea IndexOutOfRangeException.
IndexOutOfRangeException reprezintă încercarea de a introduce un element în afara memoriei alocată array-ul respectiv.
Pentru a putea insera un element in continuarea array-ului “a” vor fi necesari urmatorii paşi:
Alocarea unui nou array “b” în altă zonă de memorie, pentru a se asigura continuitatea acesteia. Acest array va avea dimensiunea array-ului inițial “a” + spațiul necesar ultimului element. Lungimea array-ului “b” va fi egală cu lungimea array-ului “a” plus 1.
Copierea elementelor din array-ul “a” în array-ul “b”.
Inserarea elementului la finalul array-ului la index-ul "lungime - 1".
Atenție! În programare există două metode de a copia un array: copie superficială şi copie adâncă. Deşi conceptul de copie superficială şi adâncă există în toate limbajele de programare şi sunt similare, implementarea lor poate diferi în funcție de modelul de gestionare al memoriei.
Analiza asimptotică pentru a insera la finalul array-ului un element este 0(1), dar mutarea tuturor elementelor în altă zonă de memorie va fi O(n). Calculul final al acesteia fiind:
O(1) + O(n) = O(n) - se face abstracție de analiza asimptotică mai performantă.
B. Inserarea elementului la începutul array-ului
Pentru inserarea elementelor la începutul array-ului (la index-ul 0), va fi necesară schimbarea fiecărui element din pozitia initială cu o pozitie la dreapta.
Analiza asimptotică pentru inserare la început este O(1), dar schimbarea poziției la indexul alăturat al fiecărui element va fi O(n). Calculul final al acesteia fiind:
O(1) + O(n) = O(n) - se face abstracție de analiza asimptotică mai performantă.
C. Inserarea elementului în mijlocul array-ului
În cazul inserării in mijlocul array-ului situația este similară cu cea anterioară, doar că schimbarea elementelor se va efectua de la indexul unde trebuie inserat.
Exemplu: dacă vrem să inserăm la indexul n/2, va trebui schimbată poziția indexului cu 1 pentru a doua jumătate a array-ului.
Analiza asimptotică va fi O(1) pentru inserare, iar pentru schimbare O(n/2). Calculul final fiind:
O(1) + O(n/2) = O(n/2) - în situația aceasta facem abstracție si de analiza asimptotică mai performantă si de constanta din a doua analiză şi va rezulta O(n).
Ştergere
Pentru ştergerea elementelor din array operațiunile sunt inverse celor de inserare. Atenție, ne referim la ştergerea completă a spațiului ocupat din zona de memorie, nu doar al valorii.
Array dinamic
Array-urile dinamice sunt structuri de dată în care dimensiunea creşte sau se micşorează după nevoie la runtime, spre deosebire de array-urile statice a căror dimensiune este fixă la compile time.
Memoria este alocată dinamic in Heap, iar în momentul în care array-ul este plin şi este inserat un element, acest array se va muta în altă zonă de memorie şi va aloca capacitatea necesară. Eficiența volumului de memorie suplimentar alocat depinde de numărul de operații de inserare şi ştergere.
În array-urile dinamice se alocă capacitate mai mare în memorie decât elementele inserate inițial.
Analiza asimptotică pentru inserarea unui nou element la sfârşitul array-ului se realizează în timp constant amortizat - O(1)+.
Timp constant amortizat se referă la faptul că: deşi uneori array-ul este mutat şi îi este alocat capacitate mai mare, această operatiune realizându-se in O(n), inserările unui element nou la finalul noului array vor fi efectuate in O(1).
Majoritatea operațiunilor de inserare la final vor fi efectuate in O(1), uneori efectându-se o operațiune mai lentă O(n).
Spre exemplu: Un array conține 5 elemente şi îi este alocată capacitate inițială dublă (10);
Vom avea 5 inserări O(1) până se umple capacitatea alocată inițial;
Elementele array-ul (10) vor fi mutate în altă parte a memoriei şi noului array îi este alocat capacitate dublă (20) - O(n);
În noul array avem iar 10 inserări O(1);
Pentru implementarea unui array personalizat şi metodele din acest articol folosind C# puteți vizita https://github.com/bogse/Arrays
Tips!
1. În C# există două tipuri de array-uri: array de tip referință şi array de tip valoare.
În array-ul de tip referință sunt stocate referințele către obiecte, ci nu obiectele în sine.
Obiectele propriu-zise sunt stocate în memoria Heap, iar referința stocată în array indică locația obiectului.
Memoria Heap este gestionată de Common Language Runtime (CLR) prin garbage collector, care este componenta CLR responsabilă pentru alocarea şi dealocarea memoriei pe heap.
Mai multe informații despre CLR şi garbage collector puteți găsi pe documentația oficială Microsoft:
2. În C# sunt folosite metodele Array.Clone() si Array.Copy() pentru a crea o copie a unui array, dar acestea funcționează diferit.
Metoda “Array.Clone()” va crea o copie superficială a array-ului. Noul array este un obiect separat, dar elementele sale au încă referințe către elementele array-ului original. Aceasta înseamnă că modificările elementelor făcute într-un array îl vor afecta şi pe celălalt.
Metoda “Array.Copy()” va crea o copie adancă a array-ului. Noul array şi elementele acestuia vor fi separate complet de array-ul original. Orice modificare efectuată ulterior într-unul dintre array-uri nu îl va afecta pe celălalt.
3. În .NET Core, array-ul static este implementat prin clasa Array (namespace: System). Această clasă oferă metode pentru manipularea array-urilor şi este clasă de bază pentru celelalte array-uri din CLR.
Mai multe informații pot fi găsite pe documentația oficială Microsoft:
4. În .NET Core, array-ul dinamic este implementat prin clasele List<T> (namespace: System.Collections.Generic) şi ArrayList (namespace: System.Collections).
Acestea conțin diferite metode şi proprietăți pentru a realiza operațiunile. În momentul în care capacitatea array-ului este prea mică pentru a acomoda elementele, capacitatea este automat mărită pentru a putea acomoda noile elemente.
Proprietatea "Capacity" este setată implicit la 0 când un array dinamic este creat, urmând ca atunci când primul element este inserat, să fie setată la valoarea 4. Când proprietatea "Count" (numărul de elemente din array ) este egală cu "Capacity" şi un nou element este inserat, capacitatea va creşte cu rata “Capacity * 2”.
Capacitatea poate fi setată şi explicit folosind unul din constructorii clasei care acceptă ca argument un integer.
Metodele List<T>.TrimExcess() şi ArrayList.TrimToSize() pot fi folosite pentru a redimensiona capacitatea array-ului să fie egală cu numarul de elemente.
Din motive de performanță este recomandată folosirea clasei List<T>.
Mai multe informații despre cele două clase, proprietățile şi metodele lor pot fi găsite pe documentația oficială Microsoft:
5. În fereastra de "Watch" putem vedea adresa de memorie la care este alocat un obiect folosind sintaxa: caracterul ‘&’ + obiectul urmărit în debugger.
Referințe
Sunt pasionat de IT și îmi doresc să mă conectez cu alți profesioniști din domeniu, cu care să împărtășesc cunoștințe și experiențe. Vă invit să mă urmăriți și să ne conectăm pe LinkedIn, la următorul link: