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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

string[] orderLines = { "Брашно 25 кг", "Захар 10 кг", "Олио 5 л", "Ориз 10 кг" };
var cart = new List<string>();
foreach (string line in orderLines)
{
    cart.Insert(0, line);
}
Console.WriteLine("Количката: " + string.Join(", ", cart));

Изход

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

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

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

Идеята

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

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

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

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

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

Виж го

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

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

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

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        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++;
    }

    public string RemoveAt(int index)
    {
        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;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

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

public void Insert(int index, string value)
{
    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++;
}

public string RemoveAt(int index)
{
    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. cart[3]: адресът е начало + 3 × 8 = 1024. Един скок, без да минава през другите: O(1) при всякакъв размер.
3. Insert(0, …): място 0 е заето. Всеки продукт се мести с едно място надясно, отзад напред, за да не се изтрие нищо: 5 премествания.
4. Чак сега „Сирене“ влиза на място 0, а размерът става 6.
5. RemoveAt(2) вади „Мляко“. Трите след него се местят с едно място наляво, за да затворят дупката: 3 премествания.
6. Размерът пада на 5, а последното място получава null: старата референция иначе пази продукта жив в паметта.
7. cart[5]: място 5 го има (капацитетът е 8), но не е в количката. Проверката сверява с размера и хвърля ArgumentOutOfRangeException.
8. Четенето по индекс е един скок. Вмъкването и махането местят всичко след индекса: отпред това са всички n, O(n). В края не се мести нищо.

var cart = new DynamicArray();
cart.Add("Хляб");
cart.Add("Мляко");
cart.Add("Кафе");
cart.Add("Масло");
cart.Add("Ябълки");
Console.WriteLine(cart[3]);
cart.Insert(0, "Сирене");
cart.RemoveAt(2);
for (int i = 0; i < cart.Count; i++)
{
    Console.WriteLine(i + ": " + cart[i]);
}
Console.WriteLine("Места: " + cart.Capacity);
try
{
    Console.WriteLine(cart[5]);
}
catch (ArgumentOutOfRangeException e)
{
    Console.WriteLine("Грешка: " + e.Message);
}

Изход

Масло
0: Сирене
1: Хляб
2: Кафе
3: Масло
4: Ябълки
Места: 8
Грешка: Specified argument was out of the range of valid values. (Parameter 'index')

this[int index] е индексатор: благодарение на него пишеш cart[3] като при масив. Така е направен и List<T>.

Пробвай

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

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

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

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        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++;
    }

    public string RemoveAt(int index)
    {
        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;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

var cart = new DynamicArray();
for (int i = 1; i <= 8; i++)
{
    cart.Add("P" + i);
}
cart.Insert(0, "P0");
Console.WriteLine("Продукти: " + cart.Count);
Console.WriteLine("Места: " + cart.Capacity);
Console.WriteLine(cart[8]);

Отговор

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

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

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

Провери

Идеята

Вмъкването и махането струват 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 кг" };
var cart = new List<string>();
foreach (string line in orderLines)
{
    cart.Add(line);
}
var newestFirst = Enumerable.Reverse(cart);
Console.WriteLine("Количката: " + string.Join(", ", 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;

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        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++;
    }

    public string RemoveAt(int index)
    {
        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;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

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

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

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

class DynamicArray
{
    private string[] items = new string[8];
    private int size = 0;
    public long Writes { get; private set; }

    public int Count => size;

    public int Capacity => items.Length;

    public string this[int index]
    {
        get
        {
            CheckIndex(index, size);
            return items[index];
        }
        set
        {
            CheckIndex(index, size);
            items[index] = value;
        }
    }

    public void Add(string value)
    {
        Insert(size, value);
    }

    public void Insert(int index, string value)
    {
        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++;
    }

    public string RemoveAt(int index)
    {
        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;
    }

    private void CheckIndex(int index, int limit)
    {
        if (index < 0 || index >= limit)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
}

foreach (int n in new[] { 10, 1000, 100000 })
{
    var cart = new DynamicArray();
    for (int i = 0; i < n; i++)
    {
        cart.Add((1001 + i).ToString());
    }
    Console.WriteLine($"в края, n = {n}: {cart.Writes} записа");
}
foreach (int n in new[] { 10, 1000 })
{
    var cart = new DynamicArray();
    for (int i = 0; i < n; i++)
    {
        cart.Insert(0, (1001 + i).ToString());
    }
    Console.WriteLine($"отпред, n = {n}: {cart.Writes} записа");
}

Изход

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

Пробвай

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

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

var cart = new DynamicArray();
cart.Add("Хляб");
cart.Add("Мляко");
cart.Add("Кафе");
cart.Insert(0, "Сирене");
for (int i = 0; i < cart.Count; i++)
{
    Console.WriteLine(i + ": " + cart[i]);
}

Изход

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

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

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

1class DynamicArray2{3 private string[] items = new string[8];4 private int size = 0;56 public int Count => size;78 public int Capacity => items.Length;910 public string this[int index]11 {12 get13 {14 CheckIndex(index, size);15 return items[index];16 }17 set18 {19 CheckIndex(index, size);20 items[index] = value;21 }22 }2324 public void Add(string value)25 {26 Insert(size, value);27 }2829 public void Insert(int index, string value)30 {31 CheckIndex(index, size + 1);32 if (size == items.Length)33 {34 Grow();35 }36 for (int i = index; i < size; i++)37 {38 items[i + 1] = items[i];39 }40 items[index] = value;41 size++;42 }4344 public string RemoveAt(int index)45 {46 CheckIndex(index, size);47 string removed = items[index];48 for (int i = index; i < size - 1; i++)49 {50 items[i] = items[i + 1];51 }52 size--;53 items[size] = null;54 return removed;55 }5657 private void Grow()58 {59 string[] bigger = new string[items.Length * 2];60 for (int i = 0; i < size; i++)61 {62 bigger[i] = items[i];63 }64 items = bigger;65 }6667 private void CheckIndex(int index, int limit)68 {69 if (index < 0 || index >= limit)70 {71 throw new ArgumentOutOfRangeException(nameof(index));72 }73 }74}

Провери

Пробвай

Попълни

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

public string RemoveAt(int index)
{
    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> не се свива сам. Capacity остава, докато не извикаш TrimExcess().
• Python (CPython) се свива сам под половината;
• JavaScript (V8) понякога свива, по свои правила.

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

Идеята

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

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

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

Важно е какво стои в местата: - int[] и List<int> държат самите числа едно до друго. string[] и List<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: как расте работата · Най-добър, среден и най-лош случай · Сложност по памет · Амортизирана сложност
• Продължава в: Свързан списък · Стек и опашка · Хеш таблица
• Задачи по темата: Структури от данни