Амортизирана сложност
Накратко: Амортизираната сложност е средната цена на операция в дълга поредица: добавянето в динамичен масив понякога копира всичко, но щом масивът расте с множител (например ×2), е средно O(1).
Проблем
Вносът, който копира всичко
Магазинът внася поръчките от стара система по една. Някой е написал вноса така, че при всяка поръчка масивът става с едно място по-голям:
def import_orders(n): orders = [] copies = 0 for i in range(n): copies += len(orders) orders = orders + [100000 + i] return copiesИзглежда невинно: един ред на поръчка. Но всеки нов масив е копие на стария плюс едно място. Програмата брои копиранията:
for n in [1000, 10000]: print(f"{n} поръчки: {import_orders(n)} копирания")1000 поръчки: 499500 копирания10000 поръчки: 49995000 копиранияПри 10 пъти повече поръчки копиранията са 100 пъти повече. При 100 000 поръчки са 4 999 950 000, и вносът, който на теста трае миг, сега върви с минути. А list.append на същите 100 000 поръчки свършва веднага, макар че и той понякога копира целия масив. Как?
Идеята
Списъкът не расте с едно място
Отвътре списъкът е масив с повече места, отколкото елементи. Когато се напълни, прави нов, по-голям масив и копира всичко в него:
cart = ["Хляб", "Мляко", "Кафе", "Масло"]cart.append("Сирене")cart.remove("Мляко")print(cart)print("Продукти:", len(cart))Стъпка по стъпка, с думи
- cart сочи обект list. Вътре има брояч ob_size и масив ob_item с 4 места.
- Продуктите от кода заемат местата един по един. Масивът е пълен: 4 от 4.
- Няма място. append заделя масив с 8 места и елементите отиват в него.
- ob_item вече сочи новия масив. „Сирене“ влиза на първото свободно място.
- remove маха „Мляко“, а всичко след него се мести с едно място наляво. Дупка не остава.
- Отвън се вижда само списък с четири продукта. Колко места има отвътре, решава CPython: езикът не го обещава.
Тайната е колко по-голям е новият масив. Ако е с едно място повече, всяко добавяне след пълния масив копира всичко, както вносът горе. Ако е два пъти по-голям, следващото копиране идва чак след още толкова добавяния.
Виж го
Свой масив, който се удвоява
Ето същият механизъм, написан на ръка, с брояч на копиранията. Масивът започва с едно място:
class OrderList: def __init__(self): self.items = [None] self.size = 0 self.copies = 0
def add(self, order): if self.size == len(self.items): bigger = [None] * (len(self.items) * 2) for i in range(self.size): bigger[i] = self.items[i] self.copies += 1 self.items = bigger self.items[self.size] = order self.size += 1for n in [9, 1000]: orders = OrderList() for i in range(n): orders.add(100000 + i) print(f"{n} поръчки: {orders.copies} копирания, 2n = {2 * n}")9 поръчки: 15 копирания, 2n = 181000 поръчки: 1023 копирания, 2n = 2000class OrderList: def __init__(self): self.items = [None] self.size = 0 self.copies = 0
def add(self, order): if self.size == len(self.items): bigger = [None] * (len(self.items) * 2) for i in range(self.size): bigger[i] = self.items[i] self.copies += 1 self.items = bigger self.items[self.size] = order self.size += 1
orders = OrderList()for i in range(9): orders.add(100000 + i)Стъпка по стъпка, с думи
- Масивът започва с едно място, а size е 0. Броим само копиранията на стари елементи.
- Първата поръчка: има място, add я записва. Копирания: 0.
- Втората: масивът е пълен. Нов масив с 2 места, а старата поръчка се копира в него: 1 копиране.
- Третата: пак е пълно, 4 места и 2 копирания. Четвъртата влиза без копиране.
- Петата копира 4, деветата 8. Копиранията растат, но между тях идват все повече добавяния без копиране.
- 9 добавяния, 1 + 2 + 4 + 8 = 15 копирания, под 2n = 18. Разпределени по всички добавяния, са под 2 на добавяне: O(1) амортизирано.
Добавяне, което намери масива пълен, копира всичко: 1, 2, 4, 8, 16 … Но след него идват толкова добавяния без копиране, колкото е копирало. Сборът 1 + 2 + 4 + … + 2ᵏ е винаги под 2 · 2ᵏ, а последното копиране 2ᵏ е под n. Значи копиранията са под 2n, колкото и да е голямо n.
Идеята
Амортизирана сложност
Едно добавяне може да струва O(n): онова, което копира всичко. Но n добавяния струват общо под 3n операции: n записа и под 2n копирания. Разделено на n, това е под 3 на добавяне: O(1).
Цената, разпределена по цяла поредица от операции, се казва амортизирана сложност. Добавянето в края на списък е O(1) амортизирано.
Това не е „средно при случаен вход“. Обещанието важи за всяка поредица добавяния, без късмет: скъпите са рядко и винаги толкова рядко.
Пробвай
Предвиди изхода
Пет поръчки в масив, който започва с едно място и се удвоява. Колко копирания?
class OrderList: def __init__(self): self.items = [None] self.size = 0 self.copies = 0
def add(self, order): if self.size == len(self.items): bigger = [None] * (len(self.items) * 2) for i in range(self.size): bigger[i] = self.items[i] self.copies += 1 self.items = bigger self.items[self.size] = order self.size += 1
for n in [5]: orders = OrderList() for i in range(n): orders.add(100000 + i) print(f"{n} поръчки: {orders.copies} копирания")Виж го
С едно място повече: O(n²)
Същият клас, само че новият масив е с едно място повече:
bigger = [None] * (len(self.items) + 1)for n in [9, 1000]: orders = OrderList() for i in range(n): orders.add(100000 + i) print(f"{n} поръчки: {orders.copies} копирания")9 поръчки: 36 копирания1000 поръчки: 499500 копиранияПри 1000 поръчки удвояването копира 1023 пъти, а растежът с едно място 499 500 пъти: 1 + 2 + … + 999. Пусни двата растежа и виж кривите. Броим само копиранията:
- Растеж ×2: копирания
O(n) - Растеж +1: копирания
O(n²)
| Алгоритъм | n = 10 | n = 1000 | n = 100 000 |
|---|---|---|---|
| Растеж ×2: копирания | 15 | 1023 | 131 071 |
| Растеж +1: копирания | 45 | 499 500 | ≈ 4 995 000 000 |
Удвояването расте като права: O(n) общо, O(1) на добавяне. Растежът с едно място расте като парабола: O(n²) общо, O(n) на добавяне.
Пробвай
Попълни
Колко места има новият масив, за да е добавянето O(1) амортизирано?
if self.size == len(self.items):
bigger = [None] * ()Новият масив е два пъти по-голям от стария. Така следващото растене идва чак след още толкова добавяния, колкото са елементите сега.
Пробвай
Намери грешката
Колега е сменил удвояването, „за да не хаби памет“. На 1000 поръчки тестът минава бързо, а нощният внос на 100 000 се влачи:
for n in [1000, 100000]: orders = OrderList() for i in range(n): orders.add(100000 + i) print(f"{n} поръчки: {orders.copies} копирания")1000 поръчки: 4510 копирания100000 поръчки: 49951000 копиранияПри 100 пъти повече поръчки копиранията са 10 000 пъти повече. На кой ред е грешката?
Избери реда с грешката.
Масивът расте със 100 места наведнъж. Това отлага растенето, но не го прави рядко: на всеки 100 добавяния идва копиране на всичко досега, и сборът пак е квадратичен, около n²/200. Растежът трябва да е умножение (×2, ×1,5), а не прибавяне, колкото и голямо да е прибавеното.
Идеята
Как расте всеки език
Нито един език не удвоява точно, но всеки умножава:
-
Java
ArrayList: ×1,5; -
C#
List<T>: ×2; - Python (CPython 3.12): новото е n + n/8 + 6, закръглено надолу до кратно на 4. Това е около ×1,125. Езикът не го обещава, решава го CPython.
- JavaScript (V8): около ×1,5.
Всеки множител над 1 дава O(1) амортизирано. Колкото е по-малък, толкова повече копирания (при ×1,5 са под 3n, при ×1,125 под 9n) и толкова по-малко празни места след растене. Изборът е размяна между време и памет, както в урока „Сложност по памет“.
Колко места има списъкът при всяко растене, за 1000 добавяния:
import sys
def places(items): return (sys.getsizeof(items) - sys.getsizeof([])) // 8
orders = []seen = []for i in range(1000): orders.append(100000 + i) if not seen or seen[-1] != places(orders): seen.append(places(orders))print("Местата при всяко растене:", " ".join(str(p) for p in seen))Местата при всяко растене: 4 8 16 24 32 40 52 64 76 92 108 128 148 172 200 232 268 308 352 400 456 520 592 672 760 860 972 1100По-точно, за любопитните
O(1) амортизирано не значи, че всяко добавяне е бързо. Добавянето, което копира, е O(n). В повечето програми това не се усеща, но в програма, която не бива да спира (каса, игра, обработка на звук), едно добавяне на милионния елемент може да е бавното. Ако знаеш колко ще са елементите, задай местата отначало: [None] * n. Тогава списъкът не копира никога.
[None] * n прави списък с n елемента None, а след това пишеш по индекс, не с append.Сметката за ×2 има и друг вид: всяко добавяне „плаща“ 2 копирания напред и ги спестява. Когато масивът с k елемента се напълни, последните k/2 добавяния са спестили k, точно колкото струва копирането. Спестеното никога не става отрицателно, затова сборът е под 2n.
Упражнение
Растеж като в Java
Реши задачата в редактора си.
Растеж с половината. Смени растежа на OrderList така, че новият масив да има старите места плюс половината (поне едно място повече). Преброй копиранията при 1000 и при 100 000 поръчки. Под 2n ли са? А под 3n?
1000 поръчки: 2137 копирания, 2n = 2000100000 поръчки: 276521 копирания, 2n = 200000Още задачи
- Махане от края. Добави
removeLast. Кога масивът да се свива, така че махането също да е O(1) амортизирано? Пробвай „наполовина, когато е пълен до половината“ и редувай добавяне и махане точно на границата. После пробвай „наполовина, когато е пълен до една четвърт“. Защо второто е O(1) амортизирано, а първото не? - Колко места хаби. След 1000 добавяния с удвояване колко от местата са празни? А с растеж ×1,5?
Тест