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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

order_lines = ["Брашно 25 кг", "Захар 10 кг", "Олио 5 л", "Ориз 10 кг"]
cart = []
for line in order_lines:
    cart.insert(0, line)
print("Количката: " + ", ".join(cart))

Изход

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

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

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

Идеята

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

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

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

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

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

Виж го

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

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

class DynamicArray:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
        self.items[index] = value
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"index {index}, size {self.size}")

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

def insert(self, index, value):
    self._check(index, self.size + 1)
    if self.size == len(self.items):
        self._grow()
    for i in range(self.size, index, -1):
        self.items[i] = self.items[i - 1]
    self.items[index] = value
    self.size += 1

def remove_at(self, index):
    self._check(index, self.size)
    removed = self.items[index]
    for i in range(index, self.size - 1):
        self.items[i] = self.items[i + 1]
    self.size -= 1
    self.items[self.size] = None
    return removed

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

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

cart = DynamicArray()
cart.append("Хляб")
cart.append("Мляко")
cart.append("Кафе")
cart.append("Масло")
cart.append("Ябълки")
print(cart[3])
cart.insert(0, "Сирене")
cart.remove_at(2)
for i in range(len(cart)):
    print(f"{i}: {cart[i]}")
print("Места: " + str(cart.capacity))
try:
    cart[5]
except IndexError as e:
    print("Грешка: " + str(e))

Изход

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

__getitem__, __setitem__ и __len__ са специалните методи, благодарение на които пишеш cart[3] и len(cart) като при вградения list.

Пробвай

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

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

class DynamicArray:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
        self.items[index] = value
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"index {index}, size {self.size}")


cart = DynamicArray()
for i in range(8):
    cart.append(f"P{i + 1}")
cart.insert(0, "P0")
print("Продукти: " + str(len(cart)))
print("Места: " + str(cart.capacity))
print(str(cart[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):

order_lines = ["Брашно 25 кг", "Захар 10 кг", "Олио 5 л", "Ориз 10 кг"]
cart = []
for line in order_lines:
    cart.append(line)
newest_first = reversed(cart)
print("Количката: " + ", ".join(newest_first))

Изход

Количката: Ориз 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:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
        self.items[index] = value
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"index {index}, size {self.size}")

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

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

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

class DynamicArray:
    def __init__(self):
        self.items = [None] * 8
        self.size = 0
        self.writes = 0

    def __len__(self):
        return self.size

    @property
    def capacity(self):
        return len(self.items)

    def __getitem__(self, index):
        self._check(index, self.size)
        return self.items[index]

    def __setitem__(self, index, value):
        self._check(index, self.size)
        self.items[index] = value

    def append(self, value):
        self.insert(self.size, value)

    def insert(self, index, value):
        self._check(index, self.size + 1)
        if self.size == len(self.items):
            self._grow()
        for i in range(self.size, index, -1):
            self.items[i] = self.items[i - 1]
            self.writes += 1
        self.items[index] = value
        self.writes += 1
        self.size += 1

    def remove_at(self, index):
        self._check(index, self.size)
        removed = self.items[index]
        for i in range(index, self.size - 1):
            self.items[i] = self.items[i + 1]
        self.size -= 1
        self.items[self.size] = None
        return removed

    def _grow(self):
        bigger = [None] * (len(self.items) * 2)
        for i in range(self.size):
            bigger[i] = self.items[i]
            self.writes += 1
        self.items = bigger

    def _check(self, index, limit):
        if index < 0 or index >= limit:
            raise IndexError(f"index {index}, size {self.size}")


for n in [10, 1000, 100000]:
    cart = DynamicArray()
    for i in range(n):
        cart.append(str(1001 + i))
    print(f"в края, n = {n}: {cart.writes} записа")
for n in [10, 1000]:
    cart = DynamicArray()
    for i in range(n):
        cart.insert(0, str(1001 + i))
    print(f"отпред, n = {n}: {cart.writes} записа")

Изход

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

Пробвай

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

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

cart = DynamicArray()
cart.append("Хляб")
cart.append("Мляко")
cart.append("Кафе")
cart.insert(0, "Сирене")
for i in range(len(cart)):
    print(f"{i}: {cart[i]}")

Изход

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

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

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

1class DynamicArray:2 def __init__(self):3 self.items = [None] * 84 self.size = 056 def __len__(self):7 return self.size89 @property10 def capacity(self):11 return len(self.items)1213 def __getitem__(self, index):14 self._check(index, self.size)15 return self.items[index]1617 def __setitem__(self, index, value):18 self._check(index, self.size)19 self.items[index] = value2021 def append(self, value):22 self.insert(self.size, value)2324 def insert(self, index, value):25 self._check(index, self.size + 1)26 if self.size == len(self.items):27 self._grow()28 for i in range(index, self.size):29 self.items[i + 1] = self.items[i]30 self.items[index] = value31 self.size += 13233 def remove_at(self, index):34 self._check(index, self.size)35 removed = self.items[index]36 for i in range(index, self.size - 1):37 self.items[i] = self.items[i + 1]38 self.size -= 139 self.items[self.size] = None40 return removed4142 def _grow(self):43 bigger = [None] * (len(self.items) * 2)44 for i in range(self.size):45 bigger[i] = self.items[i]46 self.items = bigger4748 def _check(self, index, limit):49 if index < 0 or index >= limit:50 raise IndexError(f"index {index}, size {self.size}")

Провери

Пробвай

Попълни

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

def remove_at(self, index):
    self._check(index, self.size)
    removed = self.items[index]
    for i in range(index, self.size - 1):
        self.items[i] = self.items[]
    self.size -= 1
    self.items[self.size] = None
    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) се свива сам, когато размерът падне под половината от местата. Не е обещано от езика, решава го CPython.
• JavaScript (V8) понякога свива, по свои правила.

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

Идеята

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

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

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

Важно е какво стои в местата: - list винаги държи референции към обекти, дори за числа, а самите обекти са другаде в паметта. За много числа едно до друго има array от стандартната библиотека, а в анализа на данни се ползва NumPy.

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

Упражнение

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

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

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

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

Изход

20 / 32
8 / 16
4 / 8

Още задачи

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