Два указателя в Python

Проблем

Подаръчната карта и всички двойки

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

checks = 0


def all_pairs(prices, card):
    global checks
    for i in range(len(prices)):
        for j in range(i + 1, len(prices)):
            checks += 1
            if prices[i] + prices[j] == card:
                return (i, j)
    return None

Ценоразписът е 1000 продукта по 2, 4, …, 2000 €, а картата е за 2001 €. Сборът на две четни цени никога не е нечетен, значи двойка няма. Това е най-лошият случай: циклите стигат до края.

n = 1000
prices = [2 * (i + 1) for i in range(n)]
card = 2 * n + 1
pair = all_pairs(prices, card)
print("Двойка: " + ("няма" if pair is None else "има"))
print(f"Проверки: {checks}")

Двойка: няма
Проверки: 499500

Почти половин милион проверки за 1000 продукта. Двойките са n(n − 1) / 2, затова това е O(n²): при 100 000 продукта стават около 5 милиарда.

А ценоразписът е подреден по цена, и циклите не се възползват от това.

Идеята

Единият отляво, другият отдясно

Сложи един пръст на най-евтината цена, а друг на най-скъпата. Пръстите са индекси: lo и hi. Събери двете цени:

ако сборът е колкото картата, готово;
ако е малко, евтината цена отпада: дори с най-скъпата, която още е в играта, не стига. lo отива една цена надясно;
ако е много, скъпата отпада: тя е много дори с най-евтината. hi отива една цена наляво.

Всяка стъпка изхвърля една цена завинаги, и никоя двойка с отговора не се губи. Когато lo и hi се срещнат, цените са свършили. Най-много n − 1 стъпки: O(n).

Това се казва два указателя (two pointers): два индекса, които вървят по масива, а всяко сравнение казва кой от тях да мръдне. Тук те вървят един към друг. Познаваш идеята от двоичното търсене, където lo и hi пазят обхвата. Там всяка проба изхвърля половината, тук изхвърля една цена.

Условието е същото: масивът трябва да е подреден. Само тогава „надясно е по-скъпо“ е вярно.

Виж го

lo и hi в ценоразписа

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None

prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
pair = find_pair(prices, 50)
if pair is None:
    print("Няма двойка за 50 €")
else:
    lo, hi = pair
    print(f"{prices[lo]} € + {prices[hi]} €")

19 € + 31 €

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None

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

Ценоразписът е подреден: 10 цени. Картата е 50 €. lo е на най-евтината цена, hi на най-скъпата.
3 € + 36 € = 39 € < 50 €: малко е. На 3 € не стига дори най-скъпата цена, значи 3 € отпада: lo отива надясно.
5 € + 36 € = 41 € < 50 €: малко е. На 5 € не стига дори най-скъпата цена, значи 5 € отпада: lo отива надясно.
8 € + 36 € = 44 € < 50 €: малко е. На 8 € не стига дори най-скъпата цена, значи 8 € отпада: lo отива надясно.
12 € + 36 € = 48 € < 50 €: малко е. На 12 € не стига дори най-скъпата цена, значи 12 € отпада: lo отива надясно.
15 € + 36 € = 51 € > 50 €: много е. С 36 € е много дори с най-евтината цена, значи 36 € отпада: hi отива наляво.
15 € + 31 € = 46 € < 50 €: малко е. На 15 € не стига дори най-скъпата цена, значи 15 € отпада: lo отива надясно.
19 € + 31 € = 50 €: точно колкото картата. findPair връща индексите 5 и 8.
7 сбора вместо 45 двойки. Всяка стъпка изхвърля една цена завинаги, затова стъпките са най-много n − 1.

Функцията връща кортеж с двата индекса, а когато двойка няма, None. Сборът е в total, не в sum: sum е вградена функция и не е добре да я скриваш с променлива.

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

Защо не се губи двойка. Да кажем, че отговорът е двойката на индекси i и j, i < j. Докато lo ≤ i и hi ≥ j, указателите не могат да прескочат отговора:

ако lo < i, сборът на lo и hi е най-много сборът на i и hi. Ако е малко, lo с право отива надясно, без да мине i;
ако hi > j, по същия начин hi с право отива наляво, без да мине j.

Когато lo стигне i и hi стигне j, сборът е точно картата. Ако двойките са няколко, указателите намират най-външната: тази с най-евтината цена.

Пробвай

Предвиди коя двойка

Картата е 43 €. В ценоразписа има две двойки с такъв сбор: 12 € + 31 € и 19 € + 24 €. Какво печата програмата?

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None


prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
pair = find_pair(prices, 43)
if pair is None:
    print("Няма двойка за 43 €")
else:
    lo, hi = pair
    print(f"{prices[lo]} € + {prices[hi]} €")

Отговор

12 € + 31 €

Няма двойка за 43 €

19 € + 24 €

Пробвай

Попълни

Сборът е по-малък от картата. Кой указател мърда и накъде?

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            
        else:
            hi -= 1
    return None

Пробвай

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

Картата е 50 €, а 19 € + 31 € е в ценоразписа. Функцията казва, че двойка няма:

prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
pair = find_pair(prices, 50)
if pair is None:
    print("Няма двойка за 50 €")
else:
    lo, hi = pair
    print(f"{prices[lo]} € + {prices[hi]} €")

Няма двойка за 50 €

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

Виж го

Колко стъпки

Същият ценоразпис от 1000 продукта и картата за 2001 €, а функцията брои стъпките на цикъла:

steps = 0


def find_pair(prices, card):
    global steps
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        steps += 1
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None

n = 1000
prices = [2 * (i + 1) for i in range(n)]
card = 2 * n + 1
pair = find_pair(prices, card)
print("Двойка: " + ("няма" if pair is None else "има"))
print(f"Стъпки: {steps}")

Двойка: няма
Стъпки: 999

999 стъпки вместо 499 500 проверки. Двете функции дават един и същ отговор, а при 100 000 продукта разликата е 99 999 стъпки срещу около 5 милиарда.

Пусни ги в браузъра. Третата крива е за неподреден ценоразпис: първо merge sort, после двата указателя.

Всички двойки O(n²)
Два указателя (подреден списък) 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
Два указателя (подреден списък)	9	999	9999	99 999
Подреди, после два указателя	31	9692	130 424	1 636 539

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

def find_pair(prices, card):
    lo = 0
    hi = len(prices) - 1
    while lo < hi:
        total = prices[lo] + prices[hi]
        if total == card:
            return (lo, hi)
        elif total < card:
            lo += 1
        else:
            hi -= 1
    return None

Всички двойки над 10 000 не пускаме: те са ≈. Подреждането струва повече от самите указатели, но кривата му е O(n log n) и пак е далеч под O(n²).

Идеята

Подреден ли е списъкът

Двата указателя искат подреден масив. Когато не е:

Подреди първо. Подреждането е O(n log n), указателите O(n), общо O(n log n). При 100 000 цени това са около 1,6 милиона операции срещу около 5 милиарда. Подреждането печели почти винаги.
Ако търсиш много пъти в същия списък (всеки клиент с различна карта), подреждаш веднъж, и всяко търсене после е O(n).
Индексите се сменят. След подреждане prices[5] вече не е петият продукт от каталога. Ако ти трябват продуктите, подреди двойки (цена, продукт) или обекти по цена.

prices = [27, 3, 36, 15, 8, 31, 19, 5, 24, 12]
prices.sort()
print(prices)
pair = find_pair(prices, 50)
if pair is None:
    print("Няма двойка за 50 €")
else:
    lo, hi = pair
    print(f"{prices[lo]} € + {prices[hi]} €")

[3, 5, 8, 12, 15, 19, 24, 27, 31, 36]
19 € + 31 €

Има и начин без подреждане: минаваш веднъж по цените и пазиш видените в множество. За всяка цена питаш дали картата − цената вече е видяна. Това е O(n) средно, с hash таблица и с n допълнителна памет. Двата указателя са без допълнителна памет, но искат подреден масив.

Виж го

Същата идея: сливане и повторения

Двата указателя не винаги вървят един към друг. Понякога вървят в една посока.

Сливане на два подредени списъка. Поръчките от сайта и от телефона са номерирани от един брояч, но се пазят поотделно, всеки списък подреден. Отчетът за деня иска един подреден списък. i върви по първия, j по втория, и всеки път по-малкият номер отива в резултата. Това е сливането от merge sort:

def merge(a, b):
    result = []
    i = 0
    j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result

web = [1003, 1007, 1012, 1020]
phone = [1001, 1009, 1010, 1031, 1044]
print(merge(web, phone))

[1001, 1003, 1007, 1009, 1010, 1012, 1020, 1031, 1044]

Повторенията на място. Цените от импорта са подредени, но с повторения, а филтърът трябва да покаже всяка цена веднъж. read чете всяка цена, а write е мястото на следващата нова. Всичко преди write е готово и без повторения:

def unique(prices):
    if not prices:
        return 0
    write = 1
    for read in range(1, len(prices)):
        if prices[read] != prices[write - 1]:
            prices[write] = prices[read]
            write += 1
    return write

prices = [5, 5, 8, 12, 12, 12, 19, 24, 24]
k = unique(prices)
del prices[k:]
print(f"Различни цени: {k}")
print(prices)

Различни цени: 5
[5, 8, 12, 19, 24]

Списъкът в Python може да се скъси на място: del prices[k:] маха всичко след първите k.

И двете са O(n): всеки указател минава по веднъж.

Виж го

Огледален промокод

Кампанията „Огледален код“ приема само промокодове, които се четат еднакво от двете страни. Указателите тръгват от двата края и сравняват знак по знак, докато се срещнат:

def is_mirror(code):
    lo = 0
    hi = len(code) - 1
    while lo < hi:
        if code[lo] != code[hi]:
            return False
        lo += 1
        hi -= 1
    return True

print(is_mirror("AB7CC7BA"))
print(is_mirror("AB7CD7BA"))

True
False

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

Същото се пише и на един ред, като сравниш кода с обърнато копие:

code = "AB7CC7BA"
print(code == code[::-1])

True

code[::-1] е срез с крачка −1: нов низ със същата дължина.

Отговорът е същият и пак е O(n). Разликата: копието е още n знака памет и винаги се прави цялото, а указателите спират на първата разлика. За промокод от 8 знака това е без значение. За проверка на милиони редове в лог вече има значение.

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

Упражнение

Най-близо до картата

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

Най-близо до картата. Точна двойка невинаги има. Тогава магазинът предлага двата продукта, които заедно са най-близо до картата, без да я надминат. Ценоразписът е 3, 5, 8, 12, 15, 19, 24, 27, 31 и 36 €, картата е 45 €. С двата указателя: ако сборът е до картата, запомни го, ако е по-добър от досегашния, и мръдни lo. Иначе мръдни hi.

Най-близо до 45 €: 8 € + 36 € = 44 €

Още задачи

Огледален код с тирета. Промокодовете се печатат с тирета: AB7-CC-7BA. Пропускай тиретата: всеки указател ги прескача, преди да сравнява.
По две на курс. Пратките са подредени по тегло, а един курс носи най-много две пратки до 30 кг общо. Колко курса трябват най-малко? Сложи най-леката с най-тежката, ако се събират, иначе най-тежката тръгва сама.
Общи продукти. Два подредени списъка с номера на продукти: от склада и от поръчката. Намери кои номера има и в двата, с два указателя в една посока.

Тест

Провери се

1. Ценоразписът е подреден. lo е на 8 €, hi на 36 €, картата е 50 €. Сборът е 44 €. Какво правиш?Връщаш се към началотоhi отива налявоlo отива надясно: 8 € не стига дори с най-скъпата цена

2. Ценоразписът има 100 000 продукта, а двойка за картата няма. Колко сбора смятат двата указателя?Около 5 милиарда99 999Около 17, колкото двоичното търсене

3. Списъкът с цени не е подреден. Кое е най-бързото от трите?Всички двойки (O(n²)), защото подреждането струваПодреждаш (O(n log n)) и пускаш двата указателя (O(n))Двата указателя направо върху неподредения списък

4. Премахваш повторенията от подредения списък на място, с read и write. Кое е вярно?read минава по всеки елемент, а write показва докъде е готовата частТрябва нов списък със същата дължинаread и write вървят един към друг от двата края

5. Защо проверката на огледален промокод с два указателя е по-добра от сравнението с обърнато копие?Не прави копие и спира при първата разликаОбърнатото копие дава грешен отговорТя е O(log n)

Два указателя

Бисквитки