Плъзгащ прозорец в Java

Проблем

Оборотът за последните 365 дни

Таблото на магазина показва за всеки ден оборота за последните 365 дни. Историята е 10 години: 3650 дни. Кодът смята всеки прозорец наново: за всеки ден събира 365-те дни преди него.

static long adds = 0;

static int[] recompute(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    for (int start = 0; start + k <= sales.length; start++) {
        int sum = 0;
        for (int d = start; d < start + k; d++) {
            adds++;
            sum += sales[d];
        }
        sums[start] = sum;
    }
    return sums;
}

int[] sales = new int[3650];
for (int d = 0; d < sales.length; d++) {
    sales[d] = (d * 37) % 101 * 10 + 500;
}
int[] sums = recompute(sales, 365);
int best = Arrays.stream(sums).max().getAsInt();
System.out.println("Прозорци: " + sums.length);
System.out.println("Събирания: " + adds);
System.out.println("Най-добрите 365 дни: " + best + " €");

Прозорци: 3286
Събирания: 1199390
Най-добрите 365 дни: 366050 €

3286 прозореца по 365 събирания: 1 199 390. Това е n·k: при 1000 продукта с по една графика стават 1,2 милиарда събирания всяка нощ.

А два съседни прозореца се различават само по два дни. Останалите 364 се събират отново и отново.

Идеята

Плъзни прозореца: +нов ден, −стар ден

Сумата за дни 2–8 е сумата за дни 1–7, плюс ден 8, минус ден 1. Ден 8 влиза в прозореца, ден 1 излиза. Дните между тях не се пипат.

Затова:

първият прозорец се събира веднъж: k събирания;
всеки следващ е предишният + новият ден − най-старият: две операции, колкото и да е голям прозорецът.

Това се казва плъзгащ прозорец (sliding window): прозорец с фиксирана дължина, който се мести с един елемент, а резултатът за него се обновява от предишния. Вместо (n − k + 1) · k операции стават k + 2(n − k). Това е O(n), а не O(n·k).

Прозорецът е два указателя в една посока, като в предния урок: началото и краят му. Тук разстоянието между тях е винаги k.

Виж го

Седмицата се плъзга

Продажбите за 12 дни и сумата за всеки 7 последователни дни. Средното за седмицата е сумата, разделена на 7.

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}

int[] sales = {820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850};
int[] sums = slide(sales, 7);
for (int d = 0; d < sums.length; d++) {
    System.out.println("Дни " + (d + 1) + "–" + (d + 7) + ": " + sums[d] + " €");
}

Дни 1–7: 5430 €
Дни 2–8: 5500 €
Дни 3–9: 5470 €
Дни 4–10: 5540 €
Дни 5–11: 5560 €
Дни 6–12: 5830 €

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}

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

Първият прозорец: дни 1–7. Седемте дни се събират един по един: 7 събирания, 5430 €.
Ден 8 влиза: +890 €. Ден 1 излиза: −820 €. Дни 2–8: 5500 €, с две операции вместо 7.
Ден 9 влиза: +610 €. Ден 2 излиза: −640 €. Дни 3–9: 5470 €, с две операции вместо 7.
Ден 10 влиза: +980 €. Ден 3 излиза: −910 €. Дни 4–10: 5540 €, с две операции вместо 7.
Ден 11 влиза: +720 €. Ден 4 излиза: −700 €. Дни 5–11: 5560 €, с две операции вместо 7.
Ден 12 влиза: +850 €. Ден 5 излиза: −580 €. Дни 6–12: 5830 €, с две операции вместо 7.
6 прозореца за 17 операции: 7 за първия и по 2 за всеки следващ. Наново всеки път биха били 6 · 7 = 42.

Масивът със сумите е с дължина sales.length - k + 1: толкова са прозорците. Прозорецът, който свършва в ден i, е на място i - k + 1.

Пробвай

Предвиди

Продажбите за пет дни и прозорец от 3 дни. Какво печата програмата?

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}

int[] sales = {820, 640, 910, 700, 580};
int[] sums = slide(sales, 3);
System.out.println(sums[sums.length - 1]);

Отговор

Пробвай

Попълни

Ден i влиза в прозореца. Кой ден излиза?

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[];
        sums[i - k + 1] = sum;
    }
    return sums;
}

Пробвай

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

Първата сума е вярна, а след нея числата скачат нагоре и надолу:

int[] sales = {820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720, 850};
int[] sums = slide(sales, 7);
for (int d = 0; d < sums.length; d++) {
    System.out.println("Дни " + (d + 1) + "–" + (d + 7) + ": " + sums[d] + " €");
}

Дни 1–7: 5430 €
Дни 2–8: 5560 €
Дни 3–9: 5280 €
Дни 4–10: 5650 €
Дни 5–11: 5390 €
Дни 6–12: 5520 €

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

Виж го

Измери: наново срещу плъзгане

Същите 10 години и прозорец от 365 дни, а функцията брои събиранията и изважданията:

static long ops = 0;

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        ops++;
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        ops++;
        sum += sales[i];
        ops++;
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}

int[] sales = new int[3650];
for (int d = 0; d < sales.length; d++) {
    sales[d] = (d * 37) % 101 * 10 + 500;
}
int[] sums = slide(sales, 365);
int best = Arrays.stream(sums).max().getAsInt();
System.out.println("Прозорци: " + sums.length);
System.out.println("Операции: " + ops);
System.out.println("Най-добрите 365 дни: " + best + " €");

Прозорци: 3286
Операции: 6935
Най-добрите 365 дни: 366050 €

6935 операции вместо 1 199 390, и най-добрите 365 дни са същите. Пусни двата начина в браузъра:

Всеки прозорец наново (K = 365) O(n)
Плъзгане: +нов −стар O(n)

Алгоритъм	n = 1000	n = 3650	n = 10 000	n = 100 000
Всеки прозорец наново (K = 365)	232 140	1 199 390	3 517 140	36 367 140
Плъзгане: +нов −стар	1635	6935	19 635	199 635

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

static int[] slide(int[] sales, int k) {
    int[] sums = new int[sales.length - k + 1];
    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += sales[i];
    }
    sums[0] = sum;
    for (int i = k; i < sales.length; i++) {
        sum += sales[i];
        sum -= sales[i - k];
        sums[i - k + 1] = sum;
    }
    return sums;
}

Двете криви са успоредни: прозорецът е винаги 365 дни, затова и двете растат с n. Разликата е множителят. Наново струва k на ден, плъзгането струва 2 на ден, колкото и да е голям прозорецът. При прозорец от 30 дни плъзгането е 15 пъти по-бързо, при 365 дни около 180 пъти.

Идеята

Прозорец с променлива дължина

Маркетингът пита: кой е най-дългият период от поредни дни, в който разходът за реклама е общо до 400 €? Сега дължината на прозореца не е дадена. Тя е отговорът.

Прозорецът има два края, left и right:

right върви напред и добавя нов ден;
ако сумата мине бюджета, left върви напред и маха дни отляво, докато сумата пак е до бюджета;
след това прозорецът е допустим, и дължината му е кандидат за най-дълга.

static int longestWithin(int[] spend, int budget) {
    int best = 0;
    int sum = 0;
    int left = 0;
    for (int right = 0; right < spend.length; right++) {
        sum += spend[right];
        while (sum > budget) {
            sum -= spend[left];
            left++;
        }
        best = Math.max(best, right - left + 1);
    }
    return best;
}

int[] spend = {120, 80, 200, 40, 60, 90, 30, 150, 70, 20, 250, 60};
System.out.println("Най-дълъг период до 400 €: " + longestWithin(spend, 400) + " дни");

Най-дълъг период до 400 €: 5 дни

Вътре има цикъл в цикъла, но това е O(n), не O(n²). left никога не се връща назад: всеки ден влиза в прозореца веднъж и излиза най-много веднъж. Общо най-много 2n премествания.

Това работи, защото разходите не са отрицателни: по-дълъг прозорец никога не е по-евтин. Ако има връщания (отрицателни числа), махането на ден отляво може да увеличи сумата и правилото „свий, докато стане до бюджета“ вече не е вярно.

Виж го

Без повторен знак: прозорец с множество

Друг прозорец с променлива дължина: най-дългото парче от ред в лога, в което никой знак не се повтаря. Такива парчета издават случайни токени, които не бива да стоят в лога. Прозорецът пази знаците си в множество. Когато новият знак вече е вътре, left маха знаци отляво, докато повторението изчезне:

static String longestUnique(String line) {
    Set<Character> seen = new HashSet<>();
    int bestStart = 0;
    int bestLen = 0;
    int left = 0;
    for (int right = 0; right < line.length(); right++) {
        char c = line.charAt(right);
        while (seen.contains(c)) {
            seen.remove(line.charAt(left));
            left++;
        }
        seen.add(c);
        if (right - left + 1 > bestLen) {
            bestLen = right - left + 1;
            bestStart = left;
        }
    }
    return line.substring(bestStart, bestStart + bestLen);
}

String line = "GET /cart?token=x9Kq2Lm7Pz&page=2";
String part = longestUnique(line);
System.out.println("Без повторен знак: " + part + " (" + part.length() + ")");

Без повторен знак: ?token=x9Kq2Lm7Pz&pag (21)

Проверката „има ли го“ в множеството е O(1) средно, с hash таблица. Затова и тук общото е O(n).

Set<Character> пази обвити Character, не char: seen.contains(c) обвива c автоматично.

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

Какво е „знак“. В Java, C# и JavaScript низът е от 16-битови единици (UTF-16). Емоджи като 🛒 е две такива единици, и прозорецът ще ги брои поотделно. В Python низът е от code points, и 🛒 е един знак. Лог с латиница и цифри е еднакъв на четирите езика.

Сумата да не прелее. int в Java стига до 2 147 483 647. Оборот за година в центове на голяма верига го минава: тогава сумата е long. Броячите в програмите горе са long по същата причина.

Сумата да не се разкриви. Ако продажбите са в евро с центове в double, всяко +нов −стар добавя мъничка грешка от закръгляне, а грешките се трупат: след хиляди стъпки сумата на прозореца вече не е точно сумата на дните му. Пази парите в центове, като цели числа. Ако числата са с плаваща запетая по природа (температури, времена), сметни прозореца наново на всеки няколко хиляди стъпки.

Средното и най-голямото. Плъзгащото се средно е сумата, разделена на k. Най-голямата стойност в прозореца не става с +нов −стар: максимумът не може да се „извади“. За нея има плъзгащ прозорец с опашка от двата края (deque), която пази кандидатите за максимум.

Упражнение

Най-краткият период с оборот поне 3500 €

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

Най-кратък период. Продажбите за 12 дни са 820, 640, 910, 700, 580, 1020, 760, 890, 610, 980, 720 и 850 €. Кой е най-краткият период от поредни дни с оборот поне 3500 €? Прозорецът расте надясно, а докато сумата е поне 3500 €, запомни дължината, ако е по-малка, и го свивай отляво.

Най-кратък период с поне 3500 €: 5 дни (от ден 1 до ден 5)

Още задачи

Най-добрата седмица. С плъзгането намери кои 7 поредни дни имат най-голям оборот и ги отпечатай.
Плъзгащо се средно. Отпечатай средните продажби за всеки 7 дни, закръглени до цент.
Различни клиенти за час. Поръчките са подредени по минута, всяка с номер на клиент. За всеки прозорец от 60 минути колко различни клиенти има? Пази в речник колко поръчки има всеки клиент в прозореца.

Тест

Провери се

1. Сумата за дни 1–7 е 5430 €. Ден 8 е 890 €, ден 1 е 820 €. Колко е сумата за дни 2–8?6320 €4610 €5500 €

2. n = 3650 дни, прозорец k = 365. Колко операции прави плъзгането?365 + 2 · 3285 = 69353286 · 365 = 1 199 3903650 · 365

3. В прозореца с бюджет лявата граница left никога не се връща назад. Колко пъти най-много се мести общо?n · k пътиn² пътиn пъти: всеки ден излиза от прозореца най-много веднъж

4. В разходите има и връщания: отрицателни числа. Работи ли още прозорецът „най-дълъг период до бюджета“?Да, ако бюджетът е отрицателенНе: махането на ден отляво вече може да увеличи сумата, затова „свий отляво, докато стане до бюджета“ не е вярноДа, без промяна

5. Сумите на прозореца са в евро с центове, в double. Защо е по-добре да пазиш центове в цяло число?Цяло число заема повече паметВсяко +нов −стар добавя мъничка грешка от закръгляне, а след хиляди стъпки тя се виждаdouble е по-бавен

Плъзгащ прозорец

Бисквитки