Алгоритми і структури даних для початківців: динамічний масив


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Іноді від колекції потрібна необмежена місткість і простота використання списку, але при цьому константний час доступу до довільного елемента має бути, як в масиві. В цьому разі використовується список на основі масиву – динамічний масив (Array List).

Клас ArrayList

ArrayList – це колекція, яка реалізує інтерфейс IList і використовує масив для зберігання елементів. Як і зв’язний список, ArrayList може зберігати довільне число елементів (обмежене тільки об’ємом доступної пам’яті), але в іншому поводиться як масив.

Інтерфейс IList надає всі методи ICollection і додатково – методи для читання, вставки і видалення елементів за індексом. Код нижче згенерований за допомогою команди “Implement Interface” в Visual Studio 2010 і, крім автоматично згенерованих заглушок для методів, містить також:

  • Масив з T (_ items) для зберігання елементів.
  • Конструктор за умовчанням, який створює порожній список.
  • Конструктор, що приймає ціле число, яке створює список із заданою місткістю. Зверніть увагу, що місткість списку і його довжина – це не те саме. На практиці може зустрітися ситуація, коли такий конструктор дозволить користувачеві уникнути великої кількості розширень внутрішнього масиву.
public class ArrayList: System.Collections.Generic.IList{ T[]_items; public ArrayList (): this (0) { } public ArrayList (int length) { if (length < 0) { throw new ArgumentException ("length"); }_items = new T[length]; } public int IndexOf (T item) { throw new NotImplementedException (); } public void Insert (int index, T item) { throw new NotImplementedException (); } public void RemoveAt (int index) {
throw new NotImplementedException (); } public T this[int index] { get { throw new NotImplementedException (); } set { throw new NotImplementedException (); } } public void Add (T item) { throw new NotImplementedException (); } public void Clear (){ throw new NotImplementedException (); } public bool Contains (T item) { throw new NotImplementedException (); } public void CopyTo (T[] array, int arrayIndex) { throw new NotImplementedException (); } public int Count { get { throw new NotImplementedException (); } } public bool IsReadOnly { get { throw new NotImplementedException (); } } public bool Remove (T item) { throw new NotImplementedException (); }
public System.Collections.Generic.IEnumerator GetEnumerator (){ throw new NotImplementedException (); } System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator (){ throw new NotImplementedException (); }}

Вставка елементів

Вставка елементів у динамічний масив відрізняється від вставки в зв’язний список. На те є дві причини. Перша: динамічний масив підтримує вставку в середину масиву, тоді як в зв’язний список можна вставляти тільки в кінець або початок. Друга: вставка елемента в зв’язний список завжди виконується за константний час. Вставка в динамічний масив може тривати як O (1), так і O (n) часу.

Розширення масиву

У міру додавання елементів внутрішній масив може переповнитися. В цьому випадку необхідно зробити наступне:

  1. Створити масив більшого розміру.
  2. Скопіювати елементи в новий масив.
  3. Оновити посилання на внутрішній масив списку так, щоб воно вказувало на новий.

Тепер залишилося відповісти на запитання: “Якого розміру має бути новий масив?”. Це визначається стратегією зростання динамічного масиву. Ми розглянемо дві стратегії і для обох подивимося, наскільки швидко зростає масив і наскільки його зростання знижує продуктивність.

Збільшення вдвічі (підхід Mono і Rotor)

Є дві реалізації ArrayList, код яких можна знайти в мережі: Mono і Rotor. Обидві використовують простий алгоритм збільшення розміру масиву, збільшуючи його вдвічі, за необхідності. Якщо первинний розмір масиву дорівнює нулю, то новий вміщуватиме 16 елементів:

size = size == 0 ? 16: size * 2;

Цей алгоритм робить менше виділень пам’яті, але витрачає більше місця, ніж варіант, прийнятий в Java. Іншими словами, він забезпечує частіші випадки вставки за константний час ціною використання більшої кількості пам’яті. Процес створення нового масиву і копіювання в нього елементів відбуватиметься рідше.

Повільне зростання (підхід Java)

У Java використовується схожий підхід, але масив росте повільніше. Розмір нового масиву визначається так:

size =  (size * 3)  / 2 + 1;

При використанні цього алгоритму використовується менше пам’яті.

Давайте подивимося на криві зростання масивів до 200 000 елементів при використанні цих двох стратегій:

Як видно з графіка, для того, щоб перейти границю в 200 000 елементів, варіанта з подвоєнням масиву знадобилося 19 операцій виділень пам’яті і копіювання, тоді як варіант Java потребував 30 операцій.

Яка стратегія краща? Немає правильної і неправильної відповіді на це запитання. При використанні подвоєння у нас буде менше операцій вставки за O (n), але більшою витрата пам’яті. За повільнішого зростання буде використано менше пам’яті. У загальному випадку допустимі обидва варіанти. Якщо Ваш додаток має специфічні вимоги, можливо, Вам потрібно буде реалізувати ту або іншу стратегію розширення. У будь-якому випадку, зовнішня поведінка динамічного масиву не зміниться.

Наша реалізація використовуватиме збільшення вдвічі (підхід Mono/Rotor)

private void GrowArray (){
int newLength =_items.Length == 0 ? 16 :_items.Length << 1; T[] newArray = new T[newLength];_items.CopyTo (newArray, 0);_items = newArray;}

Метод Insert

  • Поведінка: додає елемент за вказаним індексом. Якщо індекс дорівнює кількості елементів або більше його, видає виняток.
  • Складність: O (n).

Вставка за певним індексом вимагає зрушення всіх елементів, починаючи з цього індексу, на одну позицію праворуч. Якщо внутрішній масив заповнений, вставка потебує збільшення його розміру.

У наступному прикладі дається масив з п’ятьма позиціями, чотири з яких заповнені. Значення “3” вставляється на третю позицію (з індексом 2) :

Масив до зрушення елементів

Масив після зрушення елементів

Масив після вставки елементу на вільну позицію

public void Insert (int index, T item){ if (index >= Count) { throw new IndexOutOfRangeException (); } if (_ items.Length == this.Count) { this.GrowArray (); }
// Shift all the items following index one slot to the right. Array.Copy (_ items, index,_items, index + 1, Count - index);_items[index] = item; Count++;}

Метод Add

  • Поведінка: додає елемент в кінець списку.
  • Складність: O (1), якщо залишилося більше як одне вільне місце; O (n), якщо потрібне розширення масиву.
public void Add (T item){ if (_ items.Length == Count) { GrowArray (); }_items[Count++] = item;}

Видалення елементів

Метод RemoveAt

  • Поведінка: видаляє елемент, розташований за заданим індексом.
  • Складність: O (n).

Видалення елемента за індексом – операція, зворотна вставці. Вказаний елемент видаляється, а інші зрушуються на одну позицію ліворуч.

Масив до видалення елемента

Масив після видалення елемента

Масив після зрушення елементів

public void RemoveAt (int index){ if (index >= Count) { throw new IndexOutOfRangeException (); } int shiftStart = index + 1;
if (shiftStart < Count) { // Shift all the items following index one slot to the left. Array.Copy (_ items, shiftStart,_items, index, Count - shiftStart); } Count--;}

Метод Remove

  • Поведінка: видаляє перший елемент, значення якого дорівнює наданому. Повертає true, якщо елемент був видалений, або false , якщо ні.
  • Складність: O (n).
public bool Remove (T item){ for (int i = 0; i < Count; i++) { if (_ items[i].Equals (item)) { RemoveAt (i); return true; } } return false;}

Доступ до елементів

Метод IndexOf

  • Поведінка: повертає індекс першого елемента, значення якого дорівнює наданому, або – 1, якщо такого значення немає.
  • Складність: O (n).
public int IndexOf (T item){ for (int i = 0; i < Count; i++) { if (_ items[i].Equals (item)) { return i; } } return - 1;}

Метод Item

  • Поведінка: дозволяє прочитати або змінити значення за індексом.
  • Складність: O (1).
public T this[int index]{ get { if (index < Count) { return_items[index]; } throw new IndexOutOfRangeException (); } set { if (index < Count) {_items[index] = value; } else {
throw new IndexOutOfRangeException (); } }}

Метод Contains

  • Поведінка: повертає true, якщо значення є в списку, і false, якщо ні.
  • Складність: O (n).
public bool Contains (T item){ return IndexOf (item) != - 1;}

Перебір

Метод GetEnumerator

  • Поведінка: повертає ітератор IEnumerator для проходу всіма елементами списку.
  • Складність: отримання ітератора – O (1), обхід списку – O (n).

Зверніть увагу, що ми не можемо просто пройтися по масиву _ items, оскільки він містить ще не заповнені осередки, тому ми обмежуємо діапазон, по якому будемо ітерируватись кількістю елементів.

public System.Collections.Generic.IEnumerator GetEnumerator (){ for (int i = 0; i < Count; i++) { yield return_items[i]; }}System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator (){ return GetEnumerator ();}

Інші методи IList

Метод Clear

  • Поведінка: видаляє всі елементи зі списку.
  • Складність: O (1).

Существет два варіанти реалізації методу Clear. У першому випадку створюється новий порожній масив, в другому – тільки обнуляється поле Count. У нашій реалізації створюватиметься новий масив нульової довжини.

public void Clear (){_items = new T[0]; Count = 0;}

Метод CopyTo

  • Поведінка: копіює всі елементи з внутрішнього масиву у вказаний, починаючи зі вказаного індексу.
  • Складність: O (n).

Ми не використовуємо метод CopyTo масиву _ items, оскільки хочемо скопіювати тільки елементи з індексами від 0 до Count, а не весь масив. При використанні Array.Copy ми можемо вказати кількість копійованих елементів.

public void CopyTo (T[] array, int arrayIndex){ Array.Copy (_ items, 0, array, arrayIndex, Count);}

Метод Count

  • Поведінка: повертає поточну кількість елементів у колекції. Якщо список порожній, повертає 0.
  • Складність: O (1).

Count – автоінкрементоване поле з приватним сетером і публічним гетером. Користувач може тільки прочитати його, а змінювати методи додавання і видалення елементів.

public int Count{ get; private set;}

Метод IsReadOnly

  • Поведінка: завжди повертає false, оскільки наша колекція змінювана.
  • Складність: O (1).
public bool IsReadOnly{ get { return false; }}

Далі буде

На цьому ми закінчуємо розбір динамічних масивів. Наступного разу ми перейдемо до стеків і черг.

Переклад статті “The Array List”

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *