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


Іноді від колекції потрібно необмежена місткість і простота використання списку, але при цьому константний час доступу до довільного елементу, як в масиві. В цьому випадку використовується список на основі масиву – динамічний масив (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"

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

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