Разделяй и владей и дървото на рекурсията в Python

Проблем

Колко доставки са разменени

Куриерската фирма обещава на всеки клиент час за доставка. Така поръчките имат обещан ред: 1, 2, 3 и така нататък. Колите обаче карат както карат, и вечерта отчетът пита: колко далеч е днешният ред на доставките от обещания?

Мярката е броят на разменените двойки: поръчка 5 е доставена преди поръчка 3, макар че 3 е обещана по-рано. Такава двойка се казва инверсия. Ако доставките са точно по обещания ред, инверсиите са 0.

Първото решение проверява всяка двойка:

def count_pairs(ranks):
    inversions = 0
    for i in range(len(ranks)):
        for j in range(i + 1, len(ranks)):
            if ranks[i] > ranks[j]:
                inversions += 1
    return inversions

ranks = [4, 1, 7, 3, 8, 2, 6, 5]
print(f"Инверсии: {count_pairs(ranks)}")

Инверсии: 12

За 8 поръчки това са 28 двойки. За n поръчки са n(n − 1)/2, тоест O(n²). Фирмата прави 100 000 доставки на ден, а двойките са 4 999 950 000. Отчетът, който на теста е миг, вечер върви с минути.

Идеята

Раздели, преброй, сглоби

Подходът е разделяй и владей, като в merge sort: раздели доставките на първата и втората половина. Всяка разменена двойка е от един от три вида:

и двете поръчки са в първата половина;
и двете са във втората;
едната е в първата, другата във втората.

Първите два вида са същата задача, само че наполовина по-малка: рекурсията ги брои. Трудното е третият вид, двойките между половините. Ако проверяваш всяка, пак си на n².

Тук помага сливането. Нека двете половини вече са подредени. При сливане взимаш по-малкото от двете първи невзети числа. Когато по-малкото е отдясно, всяко невзето отляво е по-голямо от него, а е дошло по-рано, защото е от първата половина. Всяко от тях е една инверсия. Затова едно сравнение брои наведнъж колкото са невзетите отляво.

Така броенето „се качва“ на merge sort: същото делене, същото сливане и един ред повече.

Виж го

Броене при сливането

sort_count подрежда доставките на място и връща колко инверсии има в тях. Гледай последното сливане: всяко число отдясно, което слиза, брои невзетите отляво:

def sort_count(ranks):
    if len(ranks) <= 1:
        return 0
    mid = len(ranks) // 2
    left = ranks[:mid]
    right = ranks[mid:]
    a = sort_count(left)
    b = sort_count(right)
    cross = 0
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            ranks[k] = left[i]
            i += 1
        else:
            cross += len(left) - i
            ranks[k] = right[j]
            j += 1
        k += 1
    ranks[k:] = left[i:] + right[j:]
    return a + b + cross

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

sort_count получава 8 поръчки в реда, в който са дошли. Числото е мястото на поръчката в обещания ред.
mid = 4: първите четири доставки [4, 1, 7, 3] и последните четири [8, 2, 6, 5]. Всяка разменена двойка е или вътре в половина, или между двете.
Всяка половина вика sort_count за себе си: брои своите двойки (a = 3, b = 4) и се връща подредена.
Сега двойките между половините. i и j сочат първото невзето число. 1 < 2: лявото слиза, без инверсия.
2 отдясно е по-малко. Всяко невзето отляво ([3, 4, 7]) е по-голямо и е дошло по-рано: len(left) - i = 3 инверсии наведнъж.
Същото правило всеки път: 5 добавя 1, 6 добавя 1. cross = 5, след 7 сравнения.
Едната страна свърши. Остатъкът отива накрая без сравнение: той не добавя инверсии.
a + b + cross = 3 + 4 + 5 = 12. Проверката по двойки гледа всички 28 двойки; сливането намира същите 12 с общо 17 сравнения.

ranks = [4, 1, 7, 3, 8, 2, 6, 5]
print(f"Инверсии: {sort_count(ranks)}")
print(f"Подредени: {ranks}")

Инверсии: 12
Подредени: [1, 2, 3, 4, 5, 6, 7, 8]

Функцията подрежда масива, който получава. Ако ти трябва и редът на доставките, подай копие.

В Python функцията може да върне и двата резултата като кортеж, return merged, count. Тук подреждането е в самия списък: ranks[k:] = left[i:] + right[j:] слага остатъка накрая, защото едната от двете части е празна.

Пробвай

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

Двете половини, [2, 4, 6] и [1, 3, 5], вече са подредени, затова вътре в тях инверсии няма. Колко има между тях?

def sort_count(ranks):
    if len(ranks) <= 1:
        return 0
    mid = len(ranks) // 2
    left = ranks[:mid]
    right = ranks[mid:]
    a = sort_count(left)
    b = sort_count(right)
    cross = 0
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            ranks[k] = left[i]
            i += 1
        else:
            cross += len(left) - i
            ranks[k] = right[j]
            j += 1
        k += 1
    ranks[k:] = left[i:] + right[j:]
    return a + b + cross


ranks = [2, 4, 6, 1, 3, 5]
print(f"Инверсии: {sort_count(ranks)}")

Отговор

Инверсии: 15

Инверсии: 6

Инверсии: 3

Идеята

Дървото на рекурсията

Колко струва това? Нарисувай извикванията като дърво. Най-горе е извикването с всичките n поръчки. Под него са двете, които то прави, с по n/2. Под всяко от тях още две, и така до дъното.

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

Сега събери по нива. Най-горе работата е n. На следващото ниво са две извиквания по n/2: пак n. После четири по n/4: пак n. Нивата са колко пъти n се дели на две до 1, около log₂ n. Значи цената е нивата по работата на ниво: n · log₂ n.

Това се казва дърво на рекурсията. То е начинът да преброиш цената на всяко „разделяй и владей“: не гадаеш, а събираш ниво по ниво.

Виж го

Три дървета, три цени

Същото броене за три функции на 8 поръчки. Двоичното търсене от урока за него, написано с рекурсия. Броенето чрез сливане. И трета функция, която също дели, но лошо: първите n − 1 поръчки рекурсивно, а последната сравнява с всички преди нея.

def sort_count(ranks):
    if len(ranks) <= 1:
        return 0
    mid = len(ranks) // 2
    left = ranks[:mid]
    right = ranks[mid:]
    a = sort_count(left)
    b = sort_count(right)
    cross = 0
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            ranks[k] = left[i]
            i += 1
        else:
            cross += len(left) - i
            ranks[k] = right[j]
            j += 1
        k += 1
    ranks[k:] = left[i:] + right[j:]
    return a + b + cross

def find(ranks, target, lo, hi):
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if ranks[mid] == target:
        return mid
    if ranks[mid] < target:
        return find(ranks, target, mid + 1, hi)
    return find(ranks, target, lo, mid - 1)

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

Всяка кутия е едно извикване, а числото в нея е колко поръчки получава. find поглежда средата веднъж: работа 1.
После вика себе си за ЕДНАТА половина: 8 → 4 → 2 → 1. Един клон, и всяко ниво прави 1.
4 нива × 1 = 4. Нивата са колко пъти n се дели на две до 1, около log₂ n: O(log n).
sort_count вика себе си за ДВЕТЕ половини. Сливането най-горе минава всичките 8 поръчки, двете под него 4 + 4 = 8.
На всяко ниво извикванията са два пъти повече, а поръчките на всяко са наполовина: работата на ниво остава 8. Извикванията с една поръчка само се връщат: 0.
3 нива × 8 = 24: log₂ n нива по n, O(n log n). При 100 000 поръчки това са 17 нива, не 100 000.
count_slow също дели, но лошо: първите n − 1 поръчки и последната. Рекурсията продължава с n − 1: 8 → 7 → 6 …
На всяко ниво последната поръчка се сравнява с всички преди нея: 7, 6, … 1. 8 нива, и 7 + 6 + 5 + … + 1 = 28: точно 28-те двойки, O(n²).
Цената е формата на дървото: нивата по работата на ниво. Деленето наполовина дава log n нива, отделянето по едно дава n нива. Не стига да делиш: половините трябва да са равни.

sorted_ranks = [1, 2, 3, 4, 5, 6, 7, 8]
print("find:", find(sorted_ranks, 8, 0, len(sorted_ranks) - 1))
ranks = [4, 1, 7, 3, 8, 2, 6, 5]
print("count_slow:", count_slow(ranks, len(ranks)))
print("sort_count:", sort_count(ranks))

find: 7
count_slow: 12
sort_count: 12

Формата на дървото решава:

Един клон, половината: log₂ n нива по малко работа. O(log n).
Два клона, половините: log₂ n нива по n. O(n log n).
Един клон, едно по-малко: n нива по n. O(n²). Това е проверката по двойки, само че написана с рекурсия.

Същото става в quick sort с лош пивот: при подреден вход пивотът отделя една цена, а другите n − 1 остават в една част. Дървото е верига от n нива, и сложността е n².

Виж го

Измери го: по двойки срещу чрез сливане

Пусни двете върху едни и същи доставки. При двойките броим проверените двойки, при сливането сравненията. По двойки при 100 000 не се пуска наистина: Bench го оценява по кривата.

Инверсии по двойки O(n²)
Инверсии чрез сливане O(n log n)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Инверсии по двойки	45	499 500	49 995 000	≈ 4 999 500 000
Инверсии чрез сливане	21	8693	120 553	1 536 329

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

def sort_count(ranks):
    if len(ranks) <= 1:
        return 0
    mid = len(ranks) // 2
    left = ranks[:mid]
    right = ranks[mid:]
    a = sort_count(left)
    b = sort_count(right)
    cross = 0
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            ranks[k] = left[i]
            i += 1
        else:
            cross += len(left) - i
            ranks[k] = right[j]
            j += 1
        k += 1
    ranks[k:] = left[i:] + right[j:]
    return a + b + cross

При 1000 доставки двойките са 499 500, а сравненията 8693. При 100 000 сливането прави 1 536 329 сравнения срещу 4 999 950 000 двойки: над 3000 пъти по-малко. А инверсиите са същите, 2 504 458 463.

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

Същите числа на твоя език. Доставките са разбъркани с малък генератор със семе, затова са еднакви при всяко пускане, на всеки език и в Bench:

checks = 0
comparisons = 0


def deliveries(n):
    ranks = list(range(1, n + 1))
    x = 2026
    for k in range(n - 1, 0, -1):
        x = x * 48271 % 2147483647
        j = x % (k + 1)
        ranks[k], ranks[j] = ranks[j], ranks[k]
    return ranks


def count_pairs(ranks):
    global checks
    inversions = 0
    for i in range(len(ranks)):
        for j in range(i + 1, len(ranks)):
            checks += 1
            if ranks[i] > ranks[j]:
                inversions += 1
    return inversions


def sort_count(ranks):
    global comparisons
    if len(ranks) <= 1:
        return 0
    mid = len(ranks) // 2
    left = ranks[:mid]
    right = ranks[mid:]
    a = sort_count(left)
    b = sort_count(right)
    cross = 0
    i = j = k = 0
    while i < len(left) and j < len(right):
        comparisons += 1
        if left[i] <= right[j]:
            ranks[k] = left[i]
            i += 1
        else:
            cross += len(left) - i
            ranks[k] = right[j]
            j += 1
        k += 1
    ranks[k:] = left[i:] + right[j:]
    return a + b + cross


for n in [10, 1000]:
    checks = 0
    inv = count_pairs(deliveries(n))
    print(f"по двойки, n = {n}: {checks} проверки, {inv} инверсии")
for n in [10, 1000, 100000]:
    comparisons = 0
    inv = sort_count(deliveries(n))
    print(f"чрез сливане, n = {n}: {comparisons} сравнения, {inv} инверсии")

по двойки, n = 10: 45 проверки, 14 инверсии
по двойки, n = 1000: 499500 проверки, 249193 инверсии
чрез сливане, n = 10: 21 сравнения, 14 инверсии
чрез сливане, n = 1000: 8693 сравнения, 249193 инверсии
чрез сливане, n = 100000: 1536329 сравнения, 2504458463 инверсии

В Python цялото число няма горна граница, затова 2,5-те милиарда инверсии не са проблем. В Java и C# същият брояч трябва да е long: int стига до 2 147 483 647 и прехвърля без грешка.

Пробвай

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

Колега е преписал функцията. За 8-те доставки от сцената тя казва 5 вместо 12:

ranks = [4, 1, 7, 3, 8, 2, 6, 5]
print(f"Инверсии: {sort_count(ranks)}")
print(f"Подредени: {ranks}")

Инверсии: 5
Подредени: [1, 2, 3, 4, 5, 6, 7, 8]

На кой ред е грешката?

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

Пробвай

Попълни

Дясното число е по-малко и слиза. С колко расте cross?

def sort_count(ranks):
    if len(ranks) <= 1:
        return 0
    mid = len(ranks) // 2
    left = ranks[:mid]
    right = ranks[mid:]
    a = sort_count(left)
    b = sort_count(right)
    cross = 0
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            ranks[k] = left[i]
            i += 1
        else:
            cross += 
            ranks[k] = right[j]
            j += 1
        k += 1
    ranks[k:] = left[i:] + right[j:]
    return a + b + cross

Упражнение

Отчетът за деня

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

Разменени двойки. Прочети реда на доставките (обещаните номера, разделени с интервал) и отпечатай колко двойки са разменени и от колко общо. Ползвай sort_count от урока.

3 1 2 6 4 5 10 7 9 8

Разменени двойки: 8 от 45

Още задачи

Нарисувай дървото. Функция дели входа на три равни части и вика себе си за всяка, а работата ѝ извън извикванията е n. Нарисувай нивата: колко са и колко е работата на ниво? А ако частите са две, но работата на всяко извикване е n²?
Кои закъсняват най-много. За всяка поръчка преброй колко поръчки с по-голям номер са доставени преди нея. Сборът на тези числа е броят на инверсиите. Как да ги събереш по време на сливането? Подсказка: когато слиза число отдясно, за него се броят невзетите отляво.
Близо ли е до подредено. Преброй инверсиите в ред, който е почти подреден (две съседни поръчки разменени). Колко сравнения прави сливането? А insertion sort от простите сортирания върху същия вход?

По-точно

Мастър теоремата и другите езици

Дървото на рекурсията работи за всяко „разделяй и владей“. За най-честия вид има и готово правило.

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

Мастър теоремата, като интуиция. Функция, която дели входа на b равни части, вика себе си a пъти и прави работа f(n) извън извикванията, се описва като T(n) = a · T(n/b) + f(n). Нарисувай дървото и сравни работата горе с работата на дъното:

Работата е еднаква на всяко ниво. Умножаваш по броя нива, log n. Merge sort: T(n) = 2 · T(n/2) + n, по n на ниво, O(n log n). Двоичното търсене: T(n) = T(n/2) + 1, по 1 на ниво, O(log n).
Работата намалява надолу. Горното ниво решава. T(n) = 2 · T(n/2) + n² е O(n²): долните нива са n²/2, n²/4 и така нататък, а сборът им е под още едно n².
Работата расте надолу. Листата решават. Умножението на големи числа на Карацуба е T(n) = 3 · T(n/2) + n: три половини на всяко ниво, работата расте с 3/2 на ниво, и сложността е около n^1,58 вместо n² на училищното умножение.

Лошото делене T(n) = T(n − 1) + n изобщо не е от този вид: входът не се дели на b, а намалява с едно. Там теоремата не помага, но дървото помага: n нива по около n, O(n²).

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

Колко дълбоко отива рекурсията. Стекът от извиквания е толкова висок, колкото нивата на дървото. Броенето чрез сливане е 17 нива за 100 000 поръчки и се събира навсякъде. Лошото делене е n нива.

В Python това е проблем. Лимитът на рекурсията е 1000 нива, и функцията с n − 1 пада много преди бавното време да проличи:

def deliveries(n):
    ranks = list(range(1, n + 1))
    x = 2026
    for k in range(n - 1, 0, -1):
        x = x * 48271 % 2147483647
        j = x % (k + 1)
        ranks[k], ranks[j] = ranks[j], ranks[k]
    return ranks


def count_slow(ranks, n):
    if n <= 1:
        return 0
    inv = count_slow(ranks, n - 1)
    for i in range(n - 1):
        if ranks[i] > ranks[n - 1]:
            inv += 1
    return inv


def sort_count(ranks):
    if len(ranks) <= 1:
        return 0
    mid = len(ranks) // 2
    left = ranks[:mid]
    right = ranks[mid:]
    a = sort_count(left)
    b = sort_count(right)
    cross = 0
    i = j = k = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            ranks[k] = left[i]
            i += 1
        else:
            cross += len(left) - i
            ranks[k] = right[j]
            j += 1
        k += 1
    ranks[k:] = left[i:] + right[j:]
    return a + b + cross


ranks = deliveries(5000)
try:
    count_slow(ranks, len(ranks))
except RecursionError as e:
    print("count_slow:", type(e).__name__)
print("sort_count:", sort_count(ranks))

count_slow: RecursionError
sort_count: 6243322

Инверсиите като мярка. Броят инверсии между две подредби е мярка колко се различават: така се сравняват класирания, например резултатите на търсачка с оценките на хора. Insertion sort прави точно толкова размествания, колкото инверсии има входът. Затова е бърз за почти подреден вход и бавен за разбъркан.

Тест

Провери се

1. Дървото на рекурсията на една функция има log₂ n нива, а на всяко ниво работата е общо n. Колко е цената?O(log n)O(n)O(n log n)

2. Функцията вика себе си веднъж, за половината от входа, и прави постоянна работа. Колко е цената?O(n log n)O(log n)O(n)

3. Функцията дели входа на първите n − 1 и последния, вика себе си за n − 1 и сравнява последния с всички останали. Колко е цената?O(n²)O(n)O(n log n)

4. При сливането дясното число е по-малко, а отляво остават 3 невзети. Колко инверсии добавя това взимане?310

5. Защо в Java и C# броят на инверсиите е long, а не int?long е по-бърз от intЗащото сливането работи само с longПри 100 000 поръчки инверсиите могат да са около 2,5 милиарда, а int стига до около 2,1 милиарда

Разделяй и владей и дървото на рекурсията

Бисквитки