Динамичен масив отвътре

Код на:JavaC#PythonJavaScript

Накратко: Динамичният масив (масивът в JavaScript) има повече места, отколкото са елементите: четенето по индекс е O(1), добавянето в края е средно O(1), а вмъкването в началото е O(n).

Проблем

Количката, която се бави

Онлайн магазинът показва количката с последно добавения продукт най-горе. Кодът го прави просто: всеки нов ред влиза на индекс 0.

const orderLines = ["Брашно 25 кг", "Захар 10 кг", "Олио 5 л", "Ориз 10 кг"];
const cart = [];
for (const line of orderLines) {
  cart.unshift(line);
}
console.log("Количката: " + cart.join(", "));

Изход

Количката: Ориз 10 кг, Олио 5 л, Захар 10 кг, Брашно 25 кг

За обикновен клиент с 5 продукта това не се усеща. После идва клиент на едро и качва поръчка от файл: 50 000 реда. Страницата замръзва за секунди.

Причината: всяко вмъкване на индекс 0 мести всички вече добавени с едно място. 50 000 реда правят 1 + 2 + … + 49 999 = 1 249 975 000 премествания.

Идеята

Масив, който се грижи сам

Масивът отвътре е динамичен масив: обикновен масив с повече места, отколкото са елементите, и брояч колко от тях са заети.

• Капацитетът е колко места има масивът.
• Размерът е колко от тях са заети, от 0 до размера минус едно.

Когато местата свършат, той прави нов масив, два пъти по-голям, и копира всичко. Защо това е O(1) средно, е в урока „Амортизирана сложност“. Тук гледаме какво става вътре в масива: при четене, при вмъкване и при махане по индекс.

Местата на масива стоят едно до друго в паметта и са еднакво големи. Ако масивът започва на адрес 1000, а всяко място е 8 байта, място i е на адрес 1000 + i × 8. Затова четенето по индекс е едно умножение и едно събиране: O(1), колкото и да са елементите.

Виж го

Свой динамичен масив

Ето същото, написано на ръка. Масивът започва с 8 места:

class DynamicArray {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[index] = value;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`index ${index}, size ${this.length}`);
    }
  }
}

Гледай какво става с местата при четене, вмъкване и махане:

insert(index, value) {
  this.#check(index, this.length + 1);
  if (this.length === this.items.length) {
    this.#grow();
  }
  for (let i = this.length; i > index; i--) {
    this.items[i] = this.items[i - 1];
  }
  this.items[index] = value;
  this.length++;
}

removeAt(index) {
  this.#check(index, this.length);
  const removed = this.items[index];
  for (let i = index; i < this.length - 1; i++) {
    this.items[i] = this.items[i + 1];
  }
  this.length--;
  this.items[this.length] = undefined;
  return removed;
}

Стъпка по стъпка, с думи

1. Количката е един блок от 8 места едно до друго в паметта. Заети са 5: това е размерът. Всичките 8 са капацитетът.
2. get(3): адресът е начало + 3 × 8 = 1024. Един скок, без да минава през другите: O(1) при всякакъв размер.
3. insert(0, …): място 0 е заето. Всеки продукт се мести с едно място надясно, отзад напред, за да не се изтрие нищо: 5 премествания.
4. Чак сега „Сирене“ влиза на място 0, а размерът става 6.
5. removeAt(2) вади „Мляко“. Трите след него се местят с едно място наляво, за да затворят дупката: 3 премествания.
6. Размерът пада на 5, а последното място получава undefined: старата референция иначе пази продукта жив в паметта.
7. get(5): място 5 го има (капацитетът е 8), но не е в количката. Проверката сверява с размера и хвърля RangeError.
8. Четенето по индекс е един скок. Вмъкването и махането местят всичко след индекса: отпред това са всички n, O(n). В края не се мести нищо.

const cart = new DynamicArray();
cart.add("Хляб");
cart.add("Мляко");
cart.add("Кафе");
cart.add("Масло");
cart.add("Ябълки");
console.log(cart.get(3));
cart.insert(0, "Сирене");
cart.removeAt(2);
for (let i = 0; i < cart.length; i++) {
  console.log(`${i}: ${cart.get(i)}`);
}
console.log("Места: " + cart.capacity);
try {
  cart.get(5);
} catch (e) {
  console.log("Грешка: " + e.message);
}

Изход

Масло
0: Сирене
1: Хляб
2: Кафе
3: Масло
4: Ябълки
Места: 8
Грешка: index 5, size 5

Вграденият масив на JavaScript не проверява индекса: cart[5] извън масива дава undefined, без грешка. Нашият клас проверява и хвърля RangeError, както правят Java, C# и Python.

Пробвай

Предвиди изхода

В масив с 8 места има 8 продукта. Вмъкваш още един отпред:

class DynamicArray {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[index] = value;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`index ${index}, size ${this.length}`);
    }
  }
}

const cart = new DynamicArray();
for (let i = 1; i <= 8; i++) {
  cart.add("P" + i);
}
cart.insert(0, "P0");
console.log("Продукти: " + cart.length);
console.log("Места: " + cart.capacity);
console.log(cart.get(8));

Отговор

Продукти: 9
Места: 16
P0

Продукти: 9
Места: 16
P8

Продукти: 9
Места: 9
P8

Провери

Идеята

Вмъкването и махането струват O(n)

Вмъкването на индекс i мести всичко от i до края с едно място надясно, отзад напред, за да не изтрие нищо. Махането мести всичко след i с едно наляво. Колкото по-близо до началото, толкова повече:

• В края: нищо не се мести. O(1), а с растежа O(1) амортизирано.
• Отпред: мести се всичко. O(n).
• По средата: средно половината. Пак O(n).

Затова n вмъквания отпред са O(n²), а n добавяния в края O(n). Поправката на количката е да добавяш в края, а да показваш отзад напред. Обхождането отзад е същото O(n):

const orderLines = ["Брашно 25 кг", "Захар 10 кг", "Олио 5 л", "Ориз 10 кг"];
const cart = [];
for (const line of orderLines) {
  cart.push(line);
}
const newestFirst = cart.toReversed();
console.log("Количката: " + newestFirst.join(", "));

Изход

Количката: Ориз 10 кг, Олио 5 л, Захар 10 кг, Брашно 25 кг

Виж го

Измери го: в края срещу отпред

Пусни двата начина върху едни и същи продукти. Броим записите на елементи в масива: новия, всяко преместване и всяко копиране при растеж. Вмъкването отпред при 100 000 не се пуска наистина: Bench го оценява по кривата.

• Добавяне в края O(n)
• Вмъкване отпред O(n²)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Добавяне в края	18	2016	26 376	231 064
Вмъкване отпред	63	501 516	50 021 376	≈ 5 002 137 600

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

class DynamicArray {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
    }
    this.items[index] = value;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`index ${index}, size ${this.length}`);
    }
  }
}

При 1000 продукта добавянето в края прави 2016 записа: 1000 нови и копията при растежа. Вмъкването отпред прави 501 516. При 10 000 разликата е 26 376 срещу 50 021 376.

По-точно, за любопитните

Същите числа на твоя език, с брояч на записите в класа:

class DynamicArray {
  constructor() {
    this.items = new Array(8);
    this.length = 0;
    this.writes = 0;
  }

  get capacity() {
    return this.items.length;
  }

  get(index) {
    this.#check(index, this.length);
    return this.items[index];
  }

  set(index, value) {
    this.#check(index, this.length);
    this.items[index] = value;
  }

  add(value) {
    this.insert(this.length, value);
  }

  insert(index, value) {
    this.#check(index, this.length + 1);
    if (this.length === this.items.length) {
      this.#grow();
    }
    for (let i = this.length; i > index; i--) {
      this.items[i] = this.items[i - 1];
      this.writes++;
    }
    this.items[index] = value;
    this.writes++;
    this.length++;
  }

  removeAt(index) {
    this.#check(index, this.length);
    const removed = this.items[index];
    for (let i = index; i < this.length - 1; i++) {
      this.items[i] = this.items[i + 1];
    }
    this.length--;
    this.items[this.length] = undefined;
    return removed;
  }

  #grow() {
    const bigger = new Array(this.items.length * 2);
    for (let i = 0; i < this.length; i++) {
      bigger[i] = this.items[i];
      this.writes++;
    }
    this.items = bigger;
  }

  #check(index, limit) {
    if (index < 0 || index >= limit) {
      throw new RangeError(`index ${index}, size ${this.length}`);
    }
  }
}

for (const n of [10, 1000, 100000]) {
  const cart = new DynamicArray();
  for (let i = 0; i < n; i++) {
    cart.add(String(1001 + i));
  }
  console.log(`в края, n = ${n}: ${cart.writes} записа`);
}
for (const n of [10, 1000]) {
  const cart = new DynamicArray();
  for (let i = 0; i < n; i++) {
    cart.insert(0, String(1001 + i));
  }
  console.log(`отпред, n = ${n}: ${cart.writes} записа`);
}

Изход

в края, n = 10: 18 записа
в края, n = 1000: 2016 записа
в края, n = 100000: 231064 записа
отпред, n = 10: 63 записа
отпред, n = 1000: 501516 записа

Пробвай

Намери грешката

Колега е пренаписал insert. Три продукта, после още един отпред, и количката излиза така:

const cart = new DynamicArray();
cart.add("Хляб");
cart.add("Мляко");
cart.add("Кафе");
cart.insert(0, "Сирене");
for (let i = 0; i < cart.length; i++) {
  console.log(`${i}: ${cart.get(i)}`);
}

Изход

0: Сирене
1: Хляб
2: Хляб
3: Хляб

На кой ред е грешката?

Избери реда с грешката.

1class DynamicArray {2 constructor() {3 this.items = new Array(8);4 this.length = 0;5 }67 get capacity() {8 return this.items.length;9 }1011 get(index) {12 this.#check(index, this.length);13 return this.items[index];14 }1516 set(index, value) {17 this.#check(index, this.length);18 this.items[index] = value;19 }2021 add(value) {22 this.insert(this.length, value);23 }2425 insert(index, value) {26 this.#check(index, this.length + 1);27 if (this.length === this.items.length) {28 this.#grow();29 }30 for (let i = index; i < this.length; i++) {31 this.items[i + 1] = this.items[i];32 }33 this.items[index] = value;34 this.length++;35 }3637 removeAt(index) {38 this.#check(index, this.length);39 const removed = this.items[index];40 for (let i = index; i < this.length - 1; i++) {41 this.items[i] = this.items[i + 1];42 }43 this.length--;44 this.items[this.length] = undefined;45 return removed;46 }4748 #grow() {49 const bigger = new Array(this.items.length * 2);50 for (let i = 0; i < this.length; i++) {51 bigger[i] = this.items[i];52 }53 this.items = bigger;54 }5556 #check(index, limit) {57 if (index < 0 || index >= limit) {58 throw new RangeError(`index ${index}, size ${this.length}`);59 }60 }61}

Провери

Пробвай

Попълни

removeAt затваря дупката, като мести всеки елемент след нея с едно място наляво. Откъде идва елементът на място i?

removeAt(index) {
  this.#check(index, this.length);
  const removed = this.items[index];
  for (let i = index; i < this.length - 1; i++) {
    this.items[i] = this.items[];
  }
  this.length--;
  this.items[this.length] = undefined;
  return removed;
}

Провери

Идеята

Да се свива ли

Количката е имала 10 000 продукта, после клиентът е махнал почти всички. Масивът още държи 16 384 места. Дали да се свие?

Ако се свива наполовина, щом размерът падне под половината, има капан. Масив с 16 места и 9 елемента: махане, и той става 8 места, пълен. Добавяне, и пак 16 места. Редувай двете точно на тази граница, и всяка операция копира всичко: O(n).

Затова свиването чака по-дълго: наполовина, когато е пълен до една четвърт. След свиване масивът е наполовина пълен, и до следващото копиране има поне n/4 операции. Цената остава O(1) амортизирано.

Вградените списъци решават различно:

• Java ArrayList не се свива сам, има trimToSize();
• C# List<T> не се свива сам, има TrimExcess();
• Python (CPython) се свива сам под половината;
• JavaScript (V8) свива паметта на масива, когато голяма част от нея е празна, например след pop или length = 0. Не е обещано от езика, решава го двигателят.

Свиването спестява памет, но струва копиране. Ако масивът скоро пак ще расте, по-евтино е да не се свива.

Идеята

Защо масивът е бърз и на практика: кешът

Процесорът не чете паметта по един байт. Той взима цял ред от 64 байта и го пази в кеша, малка и много бърза памет до себе си. Четенето от кеша е десетки пъти по-бързо от четенето от основната памет.

Масивът е един блок. Когато четеш място 0, съседите му идват в същия ред и следващите четения са от кеша. Процесорът забелязва и че четеш поред, и тегли следващите редове предварително. Затова обхождането на масив е бързо не само на хартия, а и на часовника.

Важно е какво стои в местата: - V8 пази масив само от малки цели числа като самите числа едно до друго, а масив с обекти или текст като референции към тях. Масив с дупки или смесени типове става по-бавен. За числа едно до друго има Int32Array и Float64Array.

Следващият урок, „Свързан списък“, е обратното: всеки елемент е отделен обект някъде в паметта. Там вмъкването отпред е O(1), но кешът не помага.

Упражнение

Масив, който се свива

Реши задачата в редактора си.

Свиване при една четвърт. Смени растежа на класа с метод #resize(places), който прави масив с толкова места и копира елементите. insert го вика с двойно повече места, когато масивът е пълен. removeAt го вика с наполовина, когато размерът стане една четвърт от местата, но никога под 8 места.

Добави 20 продукта и отпечатай размера и местата. После махай от края, докато останат 2, и отпечатвай размера и местата при всяка смяна на местата:

Изход

20 / 32
8 / 16
4 / 8

Още задачи

• indexOf и remove. Добави indexOf(value), който връща индекса или -1, и remove(value), който маха първото срещане. Колко струва всеки?
• Махане от началото без местене. Опашка от поръчки маха винаги първия. Пази индекс head на първия зает вместо да местиш всички. Какво става, когато head стигне края на масива? (Подсказка: продължи от началото.)
• Пълни на парчета. Внеси 50 000 реда наведнъж: събери ги в края и обърни масива веднъж. Колко записа са това?

Тест

Провери се

1. Динамичен масив има 1000 елемента. Колко елемента мести вмъкването на индекс 0? А на индекс 990?

1000 и 10001 и 11000 и 10

2. Защо четенето по индекс е O(1) и при милион елемента?

Масивът помни къде е всеки елемент в отделна таблицаЗащото масивът е подреденАдресът се смята: начало + индекс × размера на едно място

3. Масивът има капацитет 8 и размер 5. Какво става при get(6)?

Грешка за индекс извън границите, макар че място 6 съществуваВръща празно мястоМасивът расте до 16

4. Защо масивът се свива наполовина чак когато е пълен до една четвърт, а не до половината?

Защото паметта се освобождава само на четвъртиниПри граница „половината“ редуване на добавяне и махане точно там свива и разширява всеки път, и всяко копира всичкоЗащото свиването е бавно

5. Количката трябва да показва последно добавения продукт най-горе. Кое е бързото решение?

Вмъквай на индекс 0Добавяй в края и показвай отзад напредСортирай след всяко добавяне

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Big-O: как расте работата · Най-добър, среден и най-лош случай · Сложност по памет · Амортизирана сложност
• Продължава в: Свързан списък · Стек и опашка · Хеш таблица
• Задачи по темата: Структури от данни