Времева сложност: броене на стъпки в Python

Проблем

Отчетът, който не свършва

Всеки месец онлайн магазинът пуска отчет за продажбите. Една от проверките в него търси двойни плащания: едно и също плащане, минало два пъти заради повторно натиснат бутон. Функцията сравнява всяко плащане с всяко след него:

def double_payments(ids):
    found = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                found += 1
    return found

ids = [100231, 100232, 100233, 100232, 100234]
print("Двойни плащания: " + str(double_payments(ids)))

Двойни плащания: 1

Преди година поръчките бяха 1 000 на месец и отчетът беше готов за 2 секунди. Днес са 100 000. Отчетът тръгва вечерта и сутринта още не е свършил. Кодът не е пипан. Данните са 100 пъти повече, а времето не е 100 пъти повече, а много повече.

Защо? И как можеше да се знае предварително, без да чакаш цяла нощ?

Идеята

Секундите лъжат, стъпките не

Колко секунди трае една програма, зависи от много неща извън нея:

машината: лаптопът и сървърът дават различни числа;
натоварването: същият отчет е по-бавен, докато сървърът обслужва и клиентите;
езика: една и съща сметка е няколко пъти по-бавна на Python, отколкото на Java или C#.

Затова се мери друго: колко пъти програмата прави своята основна операция. Тук това е едно сравнение на два номера. Броят им не зависи нито от машината, нито от езика, а само от алгоритъма и от входа. Това се казва брой операции (или брой стъпки).

Броят операции не казва секундите. Казва нещо по-полезно: колко пъти повече работа идва, когато данните растат.

Виж го

Броим стъпките

Слагаш брояч до сравнението. Всяко сравнение е една стъпка:

steps = 0


def double_payments(ids):
    global steps
    found = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            steps += 1
            if ids[i] == ids[j]:
                found += 1
    return found

Отчетът се пуска върху 10, 1 000 и 2 000 плащания с различни номера:

for n in [10, 1000, 2000]:
    ids = [100000 + k for k in range(n)]
    steps = 0
    double_payments(ids)
    print(f"n = {n}: {steps} стъпки")

n = 10: 45 стъпки
n = 1000: 499500 стъпки
n = 2000: 1999000 стъпки

Първото плащане се сравнява с n − 1 други, второто с n − 2 и така до последното, което няма с кого. Сборът е

n(n − 1) / 2

При 1 000 плащания това са 499 500 стъпки. При 100 000 са 4 999 950 000: 10 010 пъти повече за 100 пъти повече данни. Ако двете секунди отиваха почти изцяло за сравненията, сега отиват над пет часа и половина. Отговорът беше в кода още преди година: трябваше да преброиш.

Виж го

Защо почти ×4

steps = 0


def double_payments(ids):
    global steps
    found = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            steps += 1
            if ids[i] == ids[j]:
                found += 1
    return found

steps = 0


def double_payments(ids):
    global steps
    found = 0
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            steps += 1
            if ids[i] == ids[j]:
                found += 1
    return found

steps = 0


def double_payments(ids):
    global steps
    seen = set()
    found = 0
    for payment in ids:
        steps += 1
        if payment in seen:
            found += 1
        else:
            seen.add(payment)
    return found

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

Четири плащания. Външният цикъл взима първото, i = 0: то ще се сравни с всяко плащане след него.
j минава плащанията след i. Всяко сравнение е една стъпка и клетката на двойката светва: steps = 1, 2, 3.
i се мести напред, а j тръгва пак от i + 1. Двойките са 3 + 2 + 1 = 6: триъгълник.
Двойно повече плащания: 8. Стъпките не са 12, а 28.
28 = 6 стари двойки + 6 двойки от новите + 16 двойки ново със старо. Почти ×4: при 1 000 → 2 000 плащания стъпките са 499 500 → 1 999 000.
Поправката минава веднъж и помни номерата в seen: 8 плащания, 8 стъпки. Тук двойно повече плащания значи двойно повече стъпки.

Удвояването не е само „още толкова плащания“. Старите 6 двойки остават. Идват 6 двойки между новите плащания. И още 16: всяко от 4-те нови с всяко от 4-те стари. Общо 28. Частта „ново със старо“ е квадрат и тя расте най-бързо. Затова при голямо n удвояването дава почти точно ×4.

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

Сметката за всяко n: при 2n плащания двойките са 2n(2n − 1) / 2 = 4 · n(n − 1) / 2 + n. Тоест четири пъти старите двойки и още n. При n = 4 това е 4 · 6 + 4 = 28, а при n = 1 000 е 4 · 499 500 + 1 000 = 1 999 000. Добавката n е малка пред останалото, и колкото по-голямо е n, толкова по-малка.

Пробвай

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

Два вложени цикъла. Първият минава 4 склада и за всеки 3 часа за доставка. Вторият минава всяка двойка от 4 склада. Какво печата програмата?

full = 0
for i in range(4):
    for j in range(3):
        full += 1
pairs = 0
for i in range(4):
    for j in range(i + 1, 4):
        pairs += 1
print(full, pairs)

Отговор

7 4

12 6

12 16

Пробвай

Попълни

Отчетът трябва да сравни всяка двойка точно веднъж и да не сравнява плащане със самото себе си. Откъде тръгва вътрешният цикъл?

def double_payments(ids):
    found = 0
    for i in range(len(ids)):
        for j in range(, len(ids)):
            if ids[i] == ids[j]:
                found += 1
    return found

Виж го

Поправката: едно минаване

Не е нужно всяко плащане да се сравнява с всяко. Достатъчно е да помниш номерата, които вече си видял. Множеството (set) пази тези номера и казва дали даден номер е в него, без да ги минава един по един.

steps = 0


def double_payments(ids):
    global steps
    seen = set()
    found = 0
    for payment in ids:
        steps += 1
        if payment in seen:
            found += 1
        else:
            seen.add(payment)
    return found

payment in seen пита множеството дали номерът е в него. Името не е id, защото id е вградена функция в Python.

for n in [10, 1000, 2000]:
    ids = [100000 + k for k in range(n)]
    steps = 0
    double_payments(ids)
    print(f"n = {n}: {steps} стъпки")

n = 10: 10 стъпки
n = 1000: 1000 стъпки
n = 2000: 2000 стъпки

Стъпките са колкото плащанията. Двойно повече плащания значи двойно повече стъпки. Пусни двата отчета един до друг:

Всяка двойка поръчки O(n²)
Отчетът с множество (set) O(n)

Алгоритъм	n = 10	n = 1000	n = 2000	n = 4000	n = 100 000
Всяка двойка поръчки	45	499 500	1 999 000	7 998 000	≈ 4 998 750 000
Отчетът с множество (set)	10	1000	2000	4000	100 000

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

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

Коя е основната операция? Тази, която се повтаря най-много и от която зависи времето. В бавния отчет това е сравнението във вътрешния цикъл. Увеличаването на i и j и проверката дали цикълът е свършил също се повтарят, но колкото сравненията, не повече. Затова броят им не сменя картината и не се брои отделно.

Проверката в множеството една стъпка ли е? Не съвсем: зад множеството стои hash таблица, която смята hash на номера и гледа в една кофа. Средно това е една и съща малка работа, колкото и номера да има вътре. Как става, ще видиш в модула „Структури от данни“. Тук я броим за една стъпка, както я брои и Bench.

Секундите на различните езици. Броят стъпки е еднакъв, а времето не е. Python изпълнява всяка стъпка от цикъла през интерпретатора и е десетки пъти по-бавен на стъпка от Java и C#. 1 999 000 стъпки тук отнемат около десета от секундата, в Java няколко милисекунди. Ако отчетът трябва да е бърз, първо се сменя алгоритъмът, а чак после езикът.

Упражнение

Продажбите по продукт

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

Колко стъпки. Отчетът за продажбите брои колко пъти е поръчан всеки от 50-те продукта. Поръчката е номерът на продукта (от 0 до 49):

def sales_by_product(orders, products):
    sales = [0] * products
    for p in range(products):
        for product in orders:
            if product == p:
                sales[p] += 1
    return sales

Добави брояч steps пред сравнението. Пусни функцията с 1 000 и с 2 000 поръчки, в които продуктът на поръчка k е k % 50, и изпечатай стъпките:

n = 1000: 50000 стъпки
n = 2000: 100000 стъпки

Цикълът е вложен, а стъпките растат само двойно. Защо?

Още задачи

Едно минаване. Направи отчета за продажбите с едно минаване по поръчките: sales[product] расте с едно за всяка поръчка. Колко стъпки са при 1 000 поръчки?
Отчетът на годината. Колко стъпки прави бавният отчет за двойни плащания за цяла година с по 100 000 плащания на месец? Сметни с n(n − 1) / 2, без да го пускаш.
Твоят код. Намери в свой код вложен цикъл и преброй стъпките за два размера на входа. Какво става, когато входът се удвои?

Тест

Провери се

1. Защо броим операции, а не секунди?Секундите зависят от машината, натоварването и езика, а броят операции зависи само от алгоритъма и входаСекундите са твърде малки, за да се мерятОперациите винаги траят точно една наносекунда

2. Отчетът сравнява всяко плащане с всяко след него. Плащанията стават двойно повече. Колко пъти повече са стъпките?Почти четири пътиДва пътиТолкова, колкото преди

3. Отчетът за продажбите минава всичките 50 продукта, а за всеки продукт минава всички поръчки. Поръчките стават двойно повече. Колко пъти повече са стъпките?50 пътиЧетири пътиДва пъти

4. Колко стъпки прави поправката с множеството при 100 000 плащания?50 000100 0004 999 950 000

Времева сложност: броене на стъпки

Бисквитки