Префиксни суми в Python

Проблем

Таблото, което сумира всеки път

Таблото на магазина показва оборота за избран период: „от ден 120 до ден 340“, „последните 30 дни“, „тази седмица срещу миналата“. Управителите го отварят по много пъти на ден, а всяка графика пита за десетки периоди. Кодът сумира дните на всеки период наново:

def range_sum(revenue, a, b):
    total = 0
    for day in range(a, b + 1):
        total += revenue[day]
    return total

Хиляда дни оборот и хиляда заявки:

revenue = revenue_of(1000)
queries = queries_of(1000)
total = 0
additions = 0
for a, b in queries:
    total += range_sum(revenue, a, b)
    additions += b - a + 1
print(f"заявки: {len(queries)}")
print(f"сбор на отговорите: {total}")
print(f"събирания: {additions}")

заявки: 1000
сбор на отговорите: 68412493
събирания: 248794

248 794 събирания за хиляда отговора. Дните между две заявки не се сменят, а кодът ги събира пак и пак. Колкото по-дълги са периодите и колкото повече са заявките, толкова по-бавно става таблото.

Откъде са дните и заявките

Оборотът и заявките са по формула, за да ги построят еднакво програмите на четирите езика и сравнението в браузъра по-долу:

def revenue_of(n):
    return [50 + (i * 37) % 451 for i in range(n)]


def queries_of(n):
    queries = []
    for k in range(n):
        a = (k * 7919) % n
        queries.append((a, a + (k * 4231) % (n - a)))
    return queries

Идеята

Сборът на всичко вляво

Сметни веднъж, за всеки ден, оборота от началото до този ден. Това е префиксна сума (prefix sum): prefix[k] е сборът на първите k дни.

prefix[0] = 0: сборът на нито един ден;
prefix[k + 1] = prefix[k] + revenue[k]: всяко място е предишното плюс един ден.

Масивът е с едно място повече от дните. После всеки период е разлика на две числа. Оборотът от ден a до ден b е дните от 0 до b минус дните от 0 до a − 1:

prefix[b + 1] − prefix[a]

Строенето е n събирания, веднъж. Всяка заявка след това е две четения и едно изваждане, независимо дали периодът е два дни или две години: O(1) на заявка вместо O(n).

Виж го

Префиксите ден по ден

def build_prefix(revenue):
    prefix = [0] * (len(revenue) + 1)
    for i, amount in enumerate(revenue):
        prefix[i + 1] = prefix[i] + amount
    return prefix


def range_sum(prefix, a, b):
    return prefix[b + 1] - prefix[a]

revenue = [120, 80, 150, 90, 200, 60, 110, 140]
prefix = build_prefix(revenue)
print("prefix:", prefix)
print(f"дни 2–5: {range_sum(prefix, 2, 5)}")

prefix: [0, 120, 200, 350, 440, 640, 700, 810, 950]
дни 2–5: 500

def build_prefix(revenue):
    prefix = [0] * (len(revenue) + 1)
    for i, amount in enumerate(revenue):
        prefix[i + 1] = prefix[i] + amount
    return prefix


def range_sum(prefix, a, b):
    return prefix[b + 1] - prefix[a]

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

8 дни оборот. prefix има 9 места: prefix[0] = 0 е сборът на нито един ден.
prefix[1] = prefix[0] + revenue[0] = 0 + 120 = 120: дни 0–0.
prefix[2] = prefix[1] + revenue[1] = 120 + 80 = 200: дни 0–1.
prefix[3] = prefix[2] + revenue[2] = 200 + 150 = 350: дни 0–2.
prefix[4] = prefix[3] + revenue[3] = 350 + 90 = 440: дни 0–3.
prefix[5] = prefix[4] + revenue[4] = 440 + 200 = 640: дни 0–4.
prefix[6] = prefix[5] + revenue[5] = 640 + 60 = 700: дни 0–5.
prefix[7] = prefix[6] + revenue[6] = 700 + 110 = 810: дни 0–6.
prefix[8] = prefix[7] + revenue[7] = 810 + 140 = 950: дни 0–7.
8 събирания, веднъж. Сега заявката: оборотът от ден 2 до ден 5. prefix[6] = 700 € е дни 0–5.
prefix[2] = 200 € е дни 0–1, частта преди периода. Махаме я.
700 − 200 = 500 €: дни 2–5 с две четения и едно изваждане, колкото и дълъг да е периодът.
Строенето струва n събирания веднъж, а всяка заявка след това струва едно изваждане.

В сцената prefix[k] стои на границата между ден k − 1 и ден k. Така се вижда, че той е сборът на всичко вляво от границата, а един период е разликата между две граници.

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

Готовото в езиците.

itertools.accumulate дава префиксите като итератор. С initial=0 започва с нулата отпред, точно като build_prefix:

from itertools import accumulate

revenue = [120, 80, 150, 90]
print(list(accumulate(revenue, initial=0)))

[0, 120, 200, 350, 440]

Препълване. В Python цялото число няма горна граница, затова и най-големият префикс е точен. В Java и C# масивът се прави long, защото последният префикс (оборотът за години, в центове) минава границата на int.

Пробвай

Предвиди prefix

Три дни оборот: 30, 50 и 20 €.

revenue = [30, 50, 20]
prefix = build_prefix(revenue)
print("prefix:", prefix)

Отговор

prefix: [0, 30, 80, 100]

prefix: [30, 80, 100]

prefix: [0, 30, 50, 20]

Пробвай

Попълни

Оборотът от ден a до ден b включително:

return prefix[] - prefix[a]

Идеята

Нулата отпред

Защо масивът е с едно място повече? Може и без: prefix[k] да е сборът на дни 0 до k, включително. Тогава периодът от a до b е prefix[b] − prefix[a − 1]. Но при a = 0 няма място a − 1, и всяка заявка иска проверка „ако a е 0“.

Нулата отпред маха тази проверка. Цената е едно място в масива, а капанът е, че индексите се изместват с едно: prefix[k] е сборът на дни преди k, не до k. Затова тук грешката с единица (off-by-one) е най-честата, както при двоичното търсене.

Пробвай

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

Някой е написал префиксите без нулата отпред. Заявката за дни 2–5 трябва да даде 500 €:

revenue = [120, 80, 150, 90, 200, 60, 110, 140]
prefix = build_prefix(revenue)
print(f"дни 2–5: {range_sum(prefix, 2, 5)}")

дни 2–5: 350

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

Виж го

Измери: сумиране наново срещу префиксите

Същите хиляда заявки, с префиксите:

revenue = revenue_of(1000)
queries = queries_of(1000)
prefix = build_prefix(revenue)
operations = len(revenue)
total = 0
for a, b in queries:
    total += range_sum(prefix, a, b)
    operations += 1
print(f"заявки: {len(queries)}")
print(f"сбор на отговорите: {total}")
print(f"събирания и изваждания: {operations}")

заявки: 1000
сбор на отговорите: 68412493
събирания и изваждания: 2000

Сборът на отговорите е същият, а работата е 2000 операции вместо 248 794: хиляда събирания за prefix и по едно изваждане на заявка. Пусни двата начина в браузъра. n е и броят дни, и броят заявки:

Сумиране наново за всяка заявка O(n²)
Префиксни суми O(n)

Алгоритъм	n = 10	n = 1000	n = 100 000
Сумиране наново за всяка заявка	10	248 794	≈ 2 487 940 000
Префиксни суми	20	2000	200 000

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

def build_prefix(revenue):
    prefix = [0] * (len(revenue) + 1)
    for i, amount in enumerate(revenue):
        prefix[i + 1] = prefix[i] + amount
    return prefix


def range_sum(prefix, a, b):
    return prefix[b + 1] - prefix[a]

Сумирането наново е O(n) на заявка, O(n²) за n заявки. С префиксите е O(n) веднъж и O(1) на заявка. Цената е памет: един масив с n + 1 числа.

Двумерни префиксни суми: поръчките по ден и час

Топлинната карта на поръчките е таблица: редовете са дни от седмицата, колоните са часове. Въпросът е „колко поръчки има във вторник и сряда от 10 до 13 ч“, тоест сборът в правоъгълник.

p[r][c] е сборът на правоъгълника от горния ляв ъгъл до ред r − 1 и колона c − 1, пак с нули отпред (ред 0 и колона 0). Всяко място е клетката плюс горния и левия правоъгълник. Ъгълът между тях е броен два пъти, затова се маха веднъж:

def build_prefix_2d(orders):
    rows, cols = len(orders), len(orders[0])
    p = [[0] * (cols + 1) for _ in range(rows + 1)]
    for r in range(rows):
        for c in range(cols):
            p[r + 1][c + 1] = orders[r][c] + p[r][c + 1] + p[r + 1][c] - p[r][c]
    return p


def rect(p, r1, c1, r2, c2):
    return p[r2 + 1][c2 + 1] - p[r1][c2 + 1] - p[r2 + 1][c1] + p[r1][c1]

orders = [
    [3, 8, 12, 9, 5, 4],
    [2, 7, 14, 11, 6, 3],
    [4, 9, 15, 10, 7, 5],
    [1, 6, 11, 8, 4, 2],
]
p = build_prefix_2d(orders)
print(f"поръчки вт–ср от 10 до 13 ч: {rect(p, 1, 1, 2, 3)}")

поръчки вт–ср от 10 до 13 ч: 66

Заявката е същата идея: целият правоъгълник до долния десен ъгъл, минус лентата отгоре, минус лентата отляво, плюс ъгъла, който е махнат два пъти. Четири четения за правоъгълник от каквато и да е големина.

Идеята

Колко периода дават точно 50 €

Магазинът има дни на загуба: върнатите поръчки се вадят от оборота. Въпросът е колко периода от поредни дни имат печалба точно 50 €.

Всеки период от ден i до ден j е разлика на два префикса: prefix[j + 1] − prefix[i]. Тя е 50 точно когато prefix[i] = prefix[j + 1] − 50. Значи вървиш по дните, пазиш текущия префикс и питаш: колко пъти досега съм виждал префикс, равен на текущия минус 50? Отговорът се пази в речник префикс → колко пъти е виждан:

def count_periods(profit, target):
    seen = {0: 1}
    prefix = 0
    count = 0
    for p in profit:
        prefix += p
        count += seen.get(prefix - target, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

profit = [40, -10, 30, 20, -30, 50, -20, 30, 0, 20]
print(f"периоди с печалба 50 €: {count_periods(profit, 50)}")

периоди с печалба 50 €: 8

Едно минаване по дните и по едно търсене в hash таблица на ден: O(n). С два вложени цикъла по всички периоди би било O(n²). Речникът тук е брояч: колко пъти е видяна всяка стойност. Това е отделна техника, на нея е следващият урок.

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

seen започва с 0 → 1, защото префиксът преди първия ден е 0. Без него периодите, които започват от ден 0, не се броят.

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

Пробвай

Предвиди броя

Четири дни печалба: 20, 30, −30 и 30 €. Колко периода от поредни дни дават точно 50 €?

profit = [20, 30, -30, 30]
print(f"периоди с печалба 50 €: {count_periods(profit, 50)}")

Отговор

периоди с печалба 50 €: 2

периоди с печалба 50 €: 3

периоди с печалба 50 €: 1

Упражнение

Складът по дни

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

Доставено, продадено, наличност. Складът започва с 40 бройки от един продукт. За десет дни имаш два масива:

доставени: 0, 25, 0, 30, 10, 0, 40, 0, 15, 0;
продадени: 12, 8, 15, 9, 20, 11, 7, 18, 10, 14.

Построй префиксите на двата масива. За периодите дни 2–5, 0–9 и 6–8 отпечатай колко е доставено, колко е продадено и каква е наличността в края на последния ден. Всеки отговор трябва да е с няколко четения от префиксите, без цикъл по дните.

дни 2–5: доставени 40, продадени 55, наличност в края 30
дни 0–9: доставени 120, продадени 124, наличност в края 36
дни 6–8: доставени 55, продадени 35, наличност в края 50

Още задачи

Средна поръчка за период. Освен оборота имаш и броя поръчки по дни. Средната стойност на поръчка не се събира, но двете суми се събират. Как ще отговаряш на „средна поръчка от ден a до ден b“?
Най-добрата седмица. С префиксите намери седемте поредни дни с най-голям оборот. Колко операции прави това за 365 дни?
Топлинната карта. Добави към двумерните суми петък и събота и намери двучасовия прозорец с най-много поръчки за цялата седмица.

Тест

Провери се

1. Оборотът за четири дни е 10, 20, 30 и 40 €. Кой е prefix?[0, 10, 20, 30, 40][10, 30, 60, 100][0, 10, 30, 60, 100]

2. Кое дава оборота от ден a до ден b включително?prefix[b] − prefix[a]prefix[b + 1] − prefix[a + 1]prefix[b + 1] − prefix[a]

3. Вчерашният оборот се поправя заради върната поръчка. Какво става с prefix?Сменя се само едно мястоНищо: prefix не зависи от вчераСменят се всички места след този ден: поправката струва O(n)

4. В countPeriods речникът seen започва с 0 → 1. Защо?Без значение е, само ускоряваЗа да не е празенЗаради периодите, които започват от ден 0: за тях се търси префикс 0 отпреди първия ден

Префиксни суми

Бисквитки