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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

String[] orderLines = {"Брашно 25 кг", "Захар 10 кг", "Олио 5 л", "Ориз 10 кг"};
List<String> cart = new ArrayList<>();
for (String line : orderLines) {
    cart.add(0, line);
}
System.out.println("Количката: " + cart);

Изход

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

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

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

Идеята

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

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

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

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

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

Виж го

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

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

class DynamicArray {
    private String[] items = new String[8];
    private int size = 0;

    int size() {
        return size;
    }

    int capacity() {
        return items.length;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        return items[index];
    }

    void set(int index, String value) {
        Objects.checkIndex(index, size);
        items[index] = value;
    }

    void add(String value) {
        insert(size, value);
    }

    void insert(int index, String value) {
        Objects.checkIndex(index, size + 1);
        if (size == items.length) {
            grow();
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    String removeAt(int index) {
        Objects.checkIndex(index, size);
        String removed = items[index];
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void grow() {
        String[] bigger = new String[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[i];
        }
        items = bigger;
    }
}

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

void insert(int index, String value) {
    Objects.checkIndex(index, size + 1);
    if (size == items.length) {
        grow();
    }
    for (int i = size; i > index; i--) {
        items[i] = items[i - 1];
    }
    items[index] = value;
    size++;
}

String removeAt(int index) {
    Objects.checkIndex(index, size);
    String removed = items[index];
    for (int i = index; i < size - 1; i++) {
        items[i] = items[i + 1];
    }
    size--;
    items[size] = null;
    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, а последното място получава null: старата референция иначе пази продукта жив в паметта.
7. get(5): място 5 го има (капацитетът е 8), но не е в количката. Проверката сверява с размера и хвърля IndexOutOfBoundsException.
8. Четенето по индекс е един скок. Вмъкването и махането местят всичко след индекса: отпред това са всички n, O(n). В края не се мести нищо.

DynamicArray cart = new DynamicArray();
cart.add("Хляб");
cart.add("Мляко");
cart.add("Кафе");
cart.add("Масло");
cart.add("Ябълки");
System.out.println(cart.get(3));
cart.insert(0, "Сирене");
cart.removeAt(2);
for (int i = 0; i < cart.size(); i++) {
    System.out.println(i + ": " + cart.get(i));
}
System.out.println("Места: " + cart.capacity());
try {
    cart.get(5);
} catch (IndexOutOfBoundsException e) {
    System.out.println("Грешка: " + e.getMessage());
}

Изход

Масло
0: Сирене
1: Хляб
2: Кафе
3: Масло
4: Ябълки
Места: 8
Грешка: Index 5 out of bounds for length 5

Objects.checkIndex(index, size) хвърля IndexOutOfBoundsException, ако индексът е отрицателен или не е по-малък от size. Така проверява и ArrayList.

Пробвай

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

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

class DynamicArray {
    private String[] items = new String[8];
    private int size = 0;

    int size() {
        return size;
    }

    int capacity() {
        return items.length;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        return items[index];
    }

    void set(int index, String value) {
        Objects.checkIndex(index, size);
        items[index] = value;
    }

    void add(String value) {
        insert(size, value);
    }

    void insert(int index, String value) {
        Objects.checkIndex(index, size + 1);
        if (size == items.length) {
            grow();
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    String removeAt(int index) {
        Objects.checkIndex(index, size);
        String removed = items[index];
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void grow() {
        String[] bigger = new String[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[i];
        }
        items = bigger;
    }
}

DynamicArray cart = new DynamicArray();
for (int i = 1; i <= 8; i++) {
    cart.add("P" + i);
}
cart.insert(0, "P0");
System.out.println("Продукти: " + cart.size());
System.out.println("Места: " + cart.capacity());
System.out.println(cart.get(8));

Отговор

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

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

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

Провери

Идеята

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

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

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

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

String[] orderLines = {"Брашно 25 кг", "Захар 10 кг", "Олио 5 л", "Ориз 10 кг"};
List<String> cart = new ArrayList<>();
for (String line : orderLines) {
    cart.add(line);
}
List<String> newestFirst = cart.reversed();
System.out.println("Количката: " + newestFirst);

Изход

Количката: [Ориз 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 {
    private String[] items = new String[8];
    private int size = 0;

    int size() {
        return size;
    }

    int capacity() {
        return items.length;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        return items[index];
    }

    void set(int index, String value) {
        Objects.checkIndex(index, size);
        items[index] = value;
    }

    void add(String value) {
        insert(size, value);
    }

    void insert(int index, String value) {
        Objects.checkIndex(index, size + 1);
        if (size == items.length) {
            grow();
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
        }
        items[index] = value;
        size++;
    }

    String removeAt(int index) {
        Objects.checkIndex(index, size);
        String removed = items[index];
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void grow() {
        String[] bigger = new String[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[i];
        }
        items = bigger;
    }
}

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

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

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

class DynamicArray {
    private String[] items = new String[8];
    private int size = 0;
    long writes = 0;

    int size() {
        return size;
    }

    int capacity() {
        return items.length;
    }

    String get(int index) {
        Objects.checkIndex(index, size);
        return items[index];
    }

    void set(int index, String value) {
        Objects.checkIndex(index, size);
        items[index] = value;
    }

    void add(String value) {
        insert(size, value);
    }

    void insert(int index, String value) {
        Objects.checkIndex(index, size + 1);
        if (size == items.length) {
            grow();
        }
        for (int i = size; i > index; i--) {
            items[i] = items[i - 1];
            writes++;
        }
        items[index] = value;
        writes++;
        size++;
    }

    String removeAt(int index) {
        Objects.checkIndex(index, size);
        String removed = items[index];
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1];
        }
        size--;
        items[size] = null;
        return removed;
    }

    private void grow() {
        String[] bigger = new String[items.length * 2];
        for (int i = 0; i < size; i++) {
            bigger[i] = items[i];
            writes++;
        }
        items = bigger;
    }
}

for (int n : new int[] {10, 1000, 100000}) {
    DynamicArray cart = new DynamicArray();
    for (int i = 0; i < n; i++) {
        cart.add(String.valueOf(1001 + i));
    }
    System.out.println("в края, n = " + n + ": " + cart.writes + " записа");
}
for (int n : new int[] {10, 1000}) {
    DynamicArray cart = new DynamicArray();
    for (int i = 0; i < n; i++) {
        cart.insert(0, String.valueOf(1001 + i));
    }
    System.out.println("отпред, n = " + n + ": " + cart.writes + " записа");
}

Изход

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

Пробвай

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

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

DynamicArray cart = new DynamicArray();
cart.add("Хляб");
cart.add("Мляко");
cart.add("Кафе");
cart.insert(0, "Сирене");
for (int i = 0; i < cart.size(); i++) {
    System.out.println(i + ": " + cart.get(i));
}

Изход

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

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

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

1class DynamicArray {2 private String[] items = new String[8];3 private int size = 0;45 int size() {6 return size;7 }89 int capacity() {10 return items.length;11 }1213 String get(int index) {14 Objects.checkIndex(index, size);15 return items[index];16 }1718 void set(int index, String value) {19 Objects.checkIndex(index, size);20 items[index] = value;21 }2223 void add(String value) {24 insert(size, value);25 }2627 void insert(int index, String value) {28 Objects.checkIndex(index, size + 1);29 if (size == items.length) {30 grow();31 }32 for (int i = index; i < size; i++) {33 items[i + 1] = items[i];34 }35 items[index] = value;36 size++;37 }3839 String removeAt(int index) {40 Objects.checkIndex(index, size);41 String removed = items[index];42 for (int i = index; i < size - 1; i++) {43 items[i] = items[i + 1];44 }45 size--;46 items[size] = null;47 return removed;48 }4950 private void grow() {51 String[] bigger = new String[items.length * 2];52 for (int i = 0; i < size; i++) {53 bigger[i] = items[i];54 }55 items = bigger;56 }57}

Провери

Пробвай

Попълни

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

String removeAt(int index) {
    Objects.checkIndex(index, size);
    String removed = items[index];
    for (int i = index; i < size - 1; i++) {
        items[i] = items[];
    }
    size--;
    items[size] = null;
    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) понякога свива, по свои правила.

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

Идеята

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

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

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

Важно е какво стои в местата: - int[] държи самите числа едно до друго. String[] и ArrayList<String> държат референции един до друг, а самите обекти са другаде в паметта. Обхождането на референциите е бързо, но всяко четене на обект може да е скок.

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

Упражнение

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

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

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

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

Изход

20 / 32
8 / 16
4 / 8

Още задачи

• indexOf и remove. Добави indexOf(String value), който връща индекса или -1, и remove(String 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: как расте работата · Най-добър, среден и най-лош случай · Сложност по памет · Амортизирана сложност
• Продължава в: Свързан списък · Стек и опашка · Хеш таблица
• Задачи по темата: Структури от данни