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

Проблем

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

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

static long exportLogs(List<String> logs) {
    List<String> file = new ArrayList<>();
    List<List<String>> checkpoints = new ArrayList<>();
    for (String line : logs) {
        file.add(line);
        checkpoints.add(new ArrayList<>(file));
    }
    long places = 0;
    for (List<String> saved : checkpoints) {
        places += saved.size();
    }
    return places;
}

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

for (int n : new int[] {5, 1000}) {
    List<String> logs = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        logs.add("ред " + i);
    }
    System.out.println(n + " реда: " + exportLogs(logs) + " места");
}

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

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

Идеята

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

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

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

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

Виж го

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

List<String> file = new ArrayList<>();
int checkpoint = 0;
for (String line : logs) {
    file.add(line);
    checkpoint = file.size();
}

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

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. За да продължи след срив, на износа му трябва само докъде е стигнал:

static int exportLogs(List<String> logs) {
    List<String> file = new ArrayList<>();
    int checkpoint = 0;
    for (String line : logs) {
        file.add(line);
        checkpoint = file.size();
    }
    return checkpoint;
}

for (int n : new int[] {5, 1000}) {
    List<String> logs = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        logs.add("ред " + i);
    }
    System.out.println(n + " реда, checkpoint: " + exportLogs(logs));
}

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

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

Пробвай

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

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

static long exportLogs(List<String> logs) {
    List<String> file = new ArrayList<>();
    List<List<String>> checkpoints = new ArrayList<>();
    for (String line : logs) {
        file.add(line);
        checkpoints.add(new ArrayList<>(file));
    }
    long places = 0;
    for (List<String> saved : checkpoints) {
        places += saved.size();
    }
    return places;
}

for (int n : new int[] {6}) {
    List<String> logs = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        logs.add("ред " + i);
    }
    System.out.println(n + " реда: " + exportLogs(logs) + " места");
}

Отговор

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

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

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

Виж го

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

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

static List<String> newestFirst(List<String> logs) {
    List<String> result = new ArrayList<>();
    for (int i = logs.size() - 1; i >= 0; i--) {
        result.add(logs.get(i));
    }
    return result;
}

static void reverseInPlace(List<String> logs) {
    int left = 0;
    int right = logs.size() - 1;
    while (left < right) {
        String saved = logs.get(left);
        logs.set(left, logs.get(right));
        logs.set(right, saved);
        left++;
        right--;
    }
}

List<String> logs = new ArrayList<>(List.of("09:00 вход", "09:05 количка", "09:07 плащане"));
List<String> newest = newestFirst(logs);
System.out.println("Копие:    " + String.join(", ", newest));
System.out.println("Оригинал: " + String.join(", ", logs));
reverseInPlace(logs);
System.out.println("На място: " + String.join(", ", logs));

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

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

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

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

List<String> logs = new ArrayList<>(List.of("09:00 вход", "09:05 количка", "09:07 плащане"));
List<String> view = logs.reversed();
List<String> copy = new ArrayList<>(view);
Collections.reverse(logs);
System.out.println("На място: " + String.join(", ", logs));
System.out.println("Копие:    " + String.join(", ", copy));

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

Collections.reverse обръща на място. logs.reversed() (от Java 21) не копира нищо: това е изглед, който чете същия списък отзад напред. Копие става чак с new ArrayList<>(...). Същото важи за subList: изглед, не копие.

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

Пробвай

Попълни

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

String saved = logs.get(left);
logs.set(left, logs.get(right));
logs.set(right, );

Първо стойността отляво се пази в saved, защото следващият ред я презаписва. После тя отива на мястото отдясно.

Виж го

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

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

static int errorsFrom(List<String> logs, int i) {
    if (i == logs.size()) {
        return 0;
    }
    int here = logs.get(i).startsWith("ERROR") ? 1 : 0;
    return here + errorsFrom(logs, i + 1);
}

static int errors(List<String> logs) {
    int count = 0;
    for (String line : logs) {
        if (line.startsWith("ERROR")) {
            count++;
        }
    }
    return count;
}

List<String> small = makeLogs(500);
List<String> big = makeLogs(1_000_000);
System.out.println("500 реда: " + errorsFrom(small, 0) + " грешки");
try {
    System.out.println("1000000 реда: " + errorsFrom(big, 0) + " грешки");
} catch (StackOverflowError e) {
    System.out.println("1000000 реда: StackOverflowError");
}
System.out.println("С цикъл: " + errors(big) + " грешки");

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

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

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

Колко дълбоко може да стигне рекурсията, зависи от размера на стека и от големината на една рамка. В Java стекът на нишка е 1 MB по подразбиране и се сменя с -Xss (проверката на сайта пуска програмите с 8 MB, и пак не стига). StackOverflowError е Error, не Exception: тук го хващаме, за да видиш името, а в истински код рекурсията се пренаписва като цикъл.

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

Идеята

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

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

static boolean hasDuplicateLoops(int[] orders) {
    for (int i = 0; i < orders.length; i++) {
        for (int j = i + 1; j < orders.length; j++) {
            if (orders[i] == orders[j]) {
                return true;
            }
        }
    }
    return false;
}

static boolean hasDuplicateSet(int[] orders) {
    Set<Integer> seen = new HashSet<>();
    for (int order : orders) {
        if (!seen.add(order)) {
            return true;
        }
    }
    return false;
}

int[] today = {100512, 100513, 100514, 100512};
System.out.println(hasDuplicateLoops(today) + " " + hasDuplicateSet(today));

true true

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

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

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

static long comparisonsLoops(int[] orders) {
    long count = 0;
    for (int i = 0; i < orders.length; i++) {
        for (int j = i + 1; j < orders.length; j++) {
            count++;
            if (orders[i] == orders[j]) {
                return count;
            }
        }
    }
    return count;
}

static long checksSet(int[] orders) {
    Set<Integer> seen = new HashSet<>();
    long count = 0;
    for (int order : orders) {
        count++;
        if (!seen.add(order)) {
            return count;
        }
    }
    return count;
}

for (int n : new int[] {10, 1000}) {
    int[] orders = new int[n];
    for (int i = 0; i < n; i++) {
        orders[i] = 100000 + i;
    }
    System.out.println(n + " поръчки: " + comparisonsLoops(orders) + " сравнения с цикли, " + checksSet(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-а струва повече от едно число в масив: в HashSet<Integer> около 40–50 байта (обект Integer и запис в таблицата). Затова „O(n) памет“ при 10 милиона поръчки са стотици MB, не 40.

Пробвай

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

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

static boolean hasDuplicateSet(int[] orders) {
    for (int order : orders) {
        Set<Integer> seen = new HashSet<>();
        if (!seen.add(order)) {
            return true;
        }
    }
    return false;
}

int[] today = {100512, 100513, 100514, 100512};
System.out.println(hasDuplicateSet(today));

false

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

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

Упражнение

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

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

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

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

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

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

static List<String> lastLines(List<String> logs, int k) {
    ArrayDeque<String> recent = new ArrayDeque<>();
    for (String line : logs) {
        recent.addLast(line);
        if (recent.size() > k) {
            recent.removeFirst();
        }
    }
    return new ArrayList<>(recent);
}

Още задачи

Средната дължина без копие. Сметни средната дължина на ред в лога с 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. Кое не се брои в допълнителната памет на функцията?Стекът на рекурсията ѝВходът, който функцията получаваКопието на входа, което функцията прави

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

Бисквитки