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

Проблем

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

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

static long ExportLogs(List<string> logs)
{
    var file = new List<string>();
    var checkpoints = new List<List<string>>();
    foreach (string line in logs)
    {
        file.Add(line);
        checkpoints.Add(new List<string>(file));
    }
    long places = 0;
    foreach (List<string> saved in checkpoints)
    {
        places += saved.Count;
    }
    return places;
}

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

foreach (int n in new[] { 5, 1000 })
{
    var logs = new List<string>();
    for (int i = 1; i <= n; i++)
    {
        logs.Add("ред " + i);
    }
    Console.WriteLine(n + " реда: " + ExportLogs(logs) + " места");
}

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

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

Идеята

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

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

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

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

Виж го

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

var file = new List<string>();
int checkpoint = 0;
foreach (string line in logs)
{
    file.Add(line);
    checkpoint = file.Count;
}

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

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)
{
    var file = new List<string>();
    int checkpoint = 0;
    foreach (string line in logs)
    {
        file.Add(line);
        checkpoint = file.Count;
    }
    return checkpoint;
}

foreach (int n in new[] { 5, 1000 })
{
    var logs = new List<string>();
    for (int i = 1; i <= n; i++)
    {
        logs.Add("ред " + i);
    }
    Console.WriteLine(n + " реда, checkpoint: " + ExportLogs(logs));
}

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

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

Пробвай

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

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

static long ExportLogs(List<string> logs)
{
    var file = new List<string>();
    var checkpoints = new List<List<string>>();
    foreach (string line in logs)
    {
        file.Add(line);
        checkpoints.Add(new List<string>(file));
    }
    long places = 0;
    foreach (List<string> saved in checkpoints)
    {
        places += saved.Count;
    }
    return places;
}

foreach (int n in new[] { 6 })
{
    var logs = new List<string>();
    for (int i = 1; i <= n; i++)
    {
        logs.Add("ред " + i);
    }
    Console.WriteLine(n + " реда: " + ExportLogs(logs) + " места");
}

Отговор

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

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

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

Виж го

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

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

static List<string> NewestFirst(List<string> logs)
{
    var result = new List<string>();
    for (int i = logs.Count - 1; i >= 0; i--)
    {
        result.Add(logs[i]);
    }
    return result;
}

static void ReverseInPlace(List<string> logs)
{
    int left = 0;
    int right = logs.Count - 1;
    while (left < right)
    {
        (logs[left], logs[right]) = (logs[right], logs[left]);
        left++;
        right--;
    }
}

var logs = new List<string> { "09:00 вход", "09:05 количка", "09:07 плащане" };
List<string> newest = NewestFirst(logs);
Console.WriteLine("Копие:    " + string.Join(", ", newest));
Console.WriteLine("Оригинал: " + string.Join(", ", logs));
ReverseInPlace(logs);
Console.WriteLine("На място: " + string.Join(", ", logs));

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

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

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

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

var logs = new List<string> { "09:00 вход", "09:05 количка", "09:07 плащане" };
List<string> copy = Enumerable.Reverse(logs).ToList();
logs.Reverse();
Console.WriteLine("На място: " + string.Join(", ", logs));
Console.WriteLine("Копие:    " + string.Join(", ", copy));

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

List<T>.Reverse() обръща на място. Enumerable.Reverse от LINQ не прави нищо, докато не го прочетеш, а ToList() прави копието. GetRange също копира.

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

Пробвай

Попълни

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

(logs[left], logs[right]) = (logs[right], );

Виж го

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

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

static int ErrorsFrom(List<string> logs, int i)
{
    if (i == logs.Count)
    {
        return 0;
    }
    int here = logs[i].StartsWith("ERROR") ? 1 : 0;
    return here + ErrorsFrom(logs, i + 1);
}

static int Errors(List<string> logs)
{
    int count = 0;
    foreach (string line in logs)
    {
        if (line.StartsWith("ERROR"))
        {
            count++;
        }
    }
    return count;
}

List<string> small = MakeLogs(500);
List<string> big = MakeLogs(1_000_000);
Console.WriteLine("500 реда: " + ErrorsFrom(small, 0) + " грешки");
Console.WriteLine("С цикъл: " + Errors(big) + " грешки");

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

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

В C# препълването на стека не може да се хване с catch: процесът спира със съобщение „Stack overflow.“ Затова програмата горе не вика рекурсията с милион реда. При 1 000 000 реда услугата пада.

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

Колко дълбоко може да стигне рекурсията, зависи от размера на стека и от големината на една рамка. В .NET стекът на главната нишка е около 1 MB под Windows и 8 MB под Linux.

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

Идеята

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

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

static bool 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 bool HasDuplicateSet(int[] orders)
{
    var seen = new HashSet<int>();
    foreach (int order in orders)
    {
        if (!seen.Add(order))
        {
            return true;
        }
    }
    return false;
}

int[] today = { 100512, 100513, 100514, 100512 };
Console.WriteLine(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)
{
    var seen = new HashSet<int>();
    long count = 0;
    foreach (int order in orders)
    {
        count++;
        if (!seen.Add(order))
        {
            return count;
        }
    }
    return count;
}

foreach (int n in new[] { 10, 1000 })
{
    int[] orders = new int[n];
    for (int i = 0; i < n; i++)
    {
        orders[i] = 100000 + i;
    }
    Console.WriteLine(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<int> около 12–16 байта (стойността, хешът и връзката към следващия). Затова „O(n) памет“ при 10 милиона поръчки са стотици MB, не 40.

Пробвай

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

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

static bool HasDuplicateSet(int[] orders)
{
    foreach (int order in orders)
    {
        var seen = new HashSet<int>();
        if (!seen.Add(order))
        {
            return true;
        }
    }
    return false;
}

int[] today = { 100512, 100513, 100514, 100512 };
Console.WriteLine(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)
{
    var recent = new Queue<string>();
    foreach (string line in logs)
    {
        recent.Enqueue(line);
        if (recent.Count > k)
        {
            recent.Dequeue();
        }
    }
    return new List<string>(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. Кое не се брои в допълнителната памет на функцията?Стекът на рекурсията ѝВходът, който функцията получаваКопието на входа, което функцията прави

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

Бисквитки