Сложност по памет в Python

Проблем

Износът, който изяжда паметта

Всяка нощ услуга изнася логовете на магазина за деня в архив. За да продължи след срив оттам, докъдето е стигнала, след всеки ред тя записва checkpoint. Само че checkpoint-ът е копие на целия файл досега:

def export_logs(logs):
    file = []
    checkpoints = []
    for line in logs:
        file.append(line)
        checkpoints.append(file.copy())
    return sum(len(saved) for saved in checkpoints)

Колко места държат копията? Програмата ги брои:

for n in [5, 1000]:
    logs = [f"ред {i}" for i in range(1, n + 1)]
    print(f"{n} реда: {export_logs(logs)} места")

5 реда: 15 места
1000 реда: 500500 места

При 1000 реда са 500 500 места. Логовете за един ден са 100 000 реда, а това са 5 000 050 000 места. Всяко място пази референция от 4 до 8 байта: между 20 и 40 GB само за копията. На теста с 1000 реда всичко минава, а нощем износът спира с MemoryError.

Идеята

Паметта също е цена

Досега броеше операциите. Паметта се брои по същия начин: колко места заделя алгоритъмът сам, освен входа, който получава. Това е паметта на алгоритъма (на английски space complexity). И тя се казва с Big-O:

O(1): няколко променливи, колкото и да е голям входът;
O(n): копие на входа, помощен списък, set с всички елементи;
O(n²): копие на копието при всяка стъпка, като в износа.

Входът не се брои, защото го има и без алгоритъма. Не се брои и резултатът, който задачата иска: файлът с n реда е работата на износа. Броят се копията, които той прави по пътя.

Виж го

Копията остават

file = []
checkpoint = 0
for line in logs:
    file.append(line)
    checkpoint = len(file)

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

file е файлът, който износът пише, а logs има 4 реда. checkpoints пази откъде да продължи след срив.
Ред 1 отива във файла. Checkpoint-ът е копие на целия файл: 1 място.
Ред 2. Новият checkpoint копира двата реда, а старият остава в списъка: 1 + 2 = 3 места.
След 4 реда паметта държи 1 + 2 + 3 + 4 = 10 места. След n реда са n(n + 1)/2: пет милиарда при 100 000 реда.
За да продължиш след срив, ти трябва само докъде си стигнал. Копията изчезват, остава едно число.
Всеки ред сменя числото: checkpoint = 4. Допълнителната памет е 1 място, колкото и да са редовете.

Всяко копие е нов списък в паметта, а старите никой не изтрива: списъкът checkpoints ги пази. Затова местата растат като 1 + 2 + 3 + … + n. За да продължи след срив, на износа му трябва само докъде е стигнал:

def export_logs(logs):
    file = []
    checkpoint = 0
    for line in logs:
        file.append(line)
        checkpoint = len(file)
    return checkpoint

for n in [5, 1000]:
    logs = [f"ред {i}" for i in range(1, n + 1)]
    print(f"{n} реда, checkpoint: {export_logs(logs)}")

5 реда, checkpoint: 5
1000 реда, checkpoint: 1000

Файлът е същият, а допълнителната памет е едно число: O(1) вместо O(n²).

Пробвай

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

Износът с копията получава 6 реда. Колко места държат checkpoint-ите?

def export_logs(logs):
    file = []
    checkpoints = []
    for line in logs:
        file.append(line)
        checkpoints.append(file.copy())
    return sum(len(saved) for saved in checkpoints)


for n in [6]:
    logs = [f"ред {i}" for i in range(1, n + 1)]
    print(f"{n} реда: {export_logs(logs)} места")

Отговор

6 реда: 6 места

6 реда: 36 места

6 реда: 21 места

Виж го

Копие или на място

Администраторът иска най-новите логове първи. Има два начина. Единият прави нов списък в обратен ред, а другият разменя елементите в самия списък: първия с последния, втория с предпоследния, докато двата края се срещнат.

def newest_first(logs):
    result = []
    for i in range(len(logs) - 1, -1, -1):
        result.append(logs[i])
    return result


def reverse_in_place(logs):
    left = 0
    right = len(logs) - 1
    while left < right:
        logs[left], logs[right] = logs[right], logs[left]
        left += 1
        right -= 1

logs = ["09:00 вход", "09:05 количка", "09:07 плащане"]
newest = newest_first(logs)
print("Копие:    " + ", ".join(newest))
print("Оригинал: " + ", ".join(logs))
reverse_in_place(logs)
print("На място: " + ", ".join(logs))

Копие:    09:07 плащане, 09:05 количка, 09:00 вход
Оригинал: 09:00 вход, 09:05 количка, 09:07 плащане
На място: 09:07 плащане, 09:05 количка, 09:00 вход

Копието иска n нови места, но оригиналът остава непокътнат. Промяната на място (in place) иска едно място за размяната, но старият ред го няма. Кое е по-добре, зависи от това дали някой друг още чете оригинала.

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

Вградените функции правят същия избор, и името не винаги го казва:

logs = ["09:00 вход", "09:05 количка", "09:07 плащане"]
copy = logs[::-1]
logs.reverse()
print("На място: " + ", ".join(logs))
print("Копие:    " + ", ".join(copy))

На място: 09:07 плащане, 09:05 количка, 09:00 вход
Копие:    09:07 плащане, 09:05 количка, 09:00 вход

logs.reverse() обръща на място, а logs[::-1] прави копие. Всеки срез logs[a:b] е копие: logs[1:] в рекурсия копира почти целия списък при всяко извикване. reversed(logs) не копира, а само чете отзад напред.

Копието е плитко: новият списък пази референции към същите текстове, а не нови текстове. Затова местата се броят по едно на елемент.

Пробвай

Попълни

Довърши размяната на двата края:

logs[left], logs[right] = logs[right],

Виж го

Рекурсията също държи памет

Списък не е единственото, което заема място. Всяко извикване на функция пази своите параметри и локални променливи в стека от извиквания, докато не върне. Ето броене на грешките в лога с рекурсия и с цикъл:

def errors_from(logs, i):
    if i == len(logs):
        return 0
    here = 1 if logs[i].startswith("ERROR") else 0
    return here + errors_from(logs, i + 1)

def errors(logs):
    count = 0
    for line in logs:
        if line.startswith("ERROR"):
            count += 1
    return count

small = make_logs(500)
big = make_logs(1_000_000)
print(f"500 реда: {errors_from(small, 0)} грешки")
try:
    print(f"1000000 реда: {errors_from(big, 0)} грешки")
except RecursionError:
    print("1000000 реда: RecursionError")
print(f"С цикъл: {errors(big)} грешки")

500 реда: 5 грешки
1000000 реда: RecursionError
С цикъл: 10000 грешки

Рекурсията не прави нито един списък, но при n реда в стека стоят n незавършени извиквания: O(n) памет. Стекът е малък, и милион извиквания не се събират. Цикълът има една променлива count: O(1).

Python спира рекурсията още при около 1000 извиквания (sys.getrecursionlimit()). Това е предпазител: истинският стек би стигнал за повече, но не за милион.

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

Колко дълбоко може да стигне рекурсията, зависи от размера на стека и от големината на една рамка. Границата се вдига със sys.setrecursionlimit, но тогава истинският стек на процеса може да свърши и Python да падне без съобщение.

Когато рекурсивното извикване е последното действие на функцията (без here + след него), някои езици го превръщат в цикъл (tail call). Java, C#, Python и Node не го правят, затова в тях дълбочината винаги струва памет.

Идеята

Време срещу памет

Магазинът проверява дали две поръчки от деня имат един и същ номер. Първият начин сравнява всяка двойка. Вторият помни видените номера в set:

def has_duplicate_loops(orders):
    for i in range(len(orders)):
        for j in range(i + 1, len(orders)):
            if orders[i] == orders[j]:
                return True
    return False

def has_duplicate_set(orders):
    seen = set()
    for order in orders:
        if order in seen:
            return True
        seen.add(order)
    return False

today = [100512, 100513, 100514, 100512]
print(has_duplicate_loops(today), has_duplicate_set(today))

True True

Двата дават един отговор, но плащат различно:

вложените цикли: O(1) памет и O(n²) време;
set-ът: O(n) памет (до n номера) и O(n) време.

Това е честа размяна: памет срещу време. Колко сравнения и проверки правят двата, когато повторение няма (най-лошият случай):

def comparisons_loops(orders):
    count = 0
    for i in range(len(orders)):
        for j in range(i + 1, len(orders)):
            count += 1
            if orders[i] == orders[j]:
                return count
    return count


def checks_set(orders):
    seen = set()
    count = 0
    for order in orders:
        count += 1
        if order in seen:
            return count
        seen.add(order)
    return count

for n in [10, 1000]:
    orders = [100000 + i for i in range(n)]
    print(f"{n} поръчки: {comparisons_loops(orders)} сравнения с цикли, {checks_set(orders)} проверки със set")

10 поръчки: 45 сравнения с цикли, 10 проверки със set
1000 поръчки: 499500 сравнения с цикли, 1000 проверки със set

Вложени цикли, без памет O(n²)
Set с видените номера, n места O(n)

Алгоритъм	n = 10	n = 1000	n = 100 000
Вложени цикли, без памет	45	499 500	≈ 4 995 000 000
Set с видените номера, n места	10	1000	100 000

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

При 100 000 поръчки циклите правят почти 5 милиарда сравнения, а set-ът 100 000 проверки и пази 100 000 номера. Когато паметта я има, set-ът печели. Когато я няма (малко устройство, огромен вход), или подреждаш номерата (тогава повторените са един до друг), или четеш на части.

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

Една проверка в set-а броим за една операция. Тя е O(1) средно, защото set-ът е hash таблица: номерът става число, а числото казва в коя кофа да гледа. Едно място в set-а струва повече от едно число в масив: в set около 30–60 байта (запис в таблицата и обектът int). Затова „O(n) памет“ при 10 милиона поръчки са стотици MB, не 40.

Пробвай

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

Колегата е пренаписал проверката със set, но тя никога не намира повторение:

def has_duplicate_set(orders):
    for order in orders:
        seen = set()
        if order in seen:
            return True
        seen.add(order)
    return False

today = [100512, 100513, 100514, 100512]
print(has_duplicate_set(today))

False

Номер 100512 е два пъти, а отговорът е „не“. На кой ред е грешката?

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

Упражнение

Последните три реда

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

Последните редове. Когато нещо се счупи, админът иска само последните k реда от лога. Напиши last_lines(logs, k), която ги връща, като държи в паметта най-много k реда, а не целия лог: O(k) памет. Пусни я с 1000 реда („ред 1“ … „ред 1000“) и k = 3.

ред 998
ред 999
ред 1000

Едно възможно решение

Пази опашка: всеки нов ред влиза отзад, а когато редовете станат повече от k, най-старият излиза отпред.

from collections import deque


def last_lines(logs, k):
    recent = deque(maxlen=k)
    for line in logs:
        recent.append(line)
    return list(recent)

deque(maxlen=k) сам изхвърля най-стария ред, когато стане пълен.

Още задачи

Средната дължина без копие. Сметни средната дължина на ред в лога с O(1) допълнителна памет: без нов списък с дължините.
Грешките по час. Преброй грешките за всеки час (09, 10…). Колко памет иска твоето решение, ако часовете са 24, а редовете милион?
Повторените номера. Върни не само „има или няма“, а всички повторени номера. Колко памет иска решението със set, и може ли без него?

Тест

Провери се

1. Функция прави нов списък с n лога в обратен ред. Колко допълнителна памет иска?O(1)O(n)O(n²)

2. Износът пази след всеки ред копие на целия файл досега. Колко места държи паметта при n реда?n2nn(n + 1)/2, тоест O(n²)

3. Рекурсивна функция без нито един списък се вика 1 000 000 пъти една в друга. Колко памет иска?O(n): всяко извикване стои в стека, докато не върнеНикаква, паметта е само за обектиO(1), защото няма списъци

4. Търсиш повторен номер в 10 000 000 поръчки на сървър с няколко GB свободна памет. Кое избираш?Вложените цикли, защото не искат паметSet-а: O(n) памет, но O(n) време вместо O(n²)Все едно е

5. Кое не се брои в допълнителната памет на функцията?Стекът на рекурсията ѝВходът, който функцията получаваКопието на входа, което функцията прави

Сложност по памет

Бисквитки