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

Проблем

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

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

static long checks = 0;

static (int, int)? AllPairs(int[] prices, int card)
{
    for (int i = 0; i < prices.Length; i++)
    {
        for (int j = i + 1; j < prices.Length; j++)
        {
            checks++;
            if (prices[i] + prices[j] == card)
            {
                return (i, j);
            }
        }
    }
    return null;
}

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

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++)
{
    prices[i] = 2 * (i + 1);
}
int card = 2 * n + 1;
var pair = AllPairs(prices, card);
Console.WriteLine("Двойка: " + (pair == null ? "няма" : "има"));
Console.WriteLine("Проверки: " + 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 в ценоразписа

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
var pair = FindPair(prices, 50);
if (pair is (int lo, int hi))
{
    Console.WriteLine($"{prices[lo]} € + {prices[hi]} €");
}
else
{
    Console.WriteLine("Няма двойка за 50 €");
}

19 € + 31 €

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

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

Ценоразписът е подреден: 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.

Функцията връща кортеж (int, int)?: двата индекса, а когато двойка няма, null. pair is (int lo, int hi) проверява, че има стойност, и я разделя на двете части.

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

Защо не се губи двойка. Да кажем, че отговорът е двойката на индекси 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 €. Какво печата програмата?

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
var pair = FindPair(prices, 43);
if (pair is (int lo, int hi))
{
    Console.WriteLine($"{prices[lo]} € + {prices[hi]} €");
}
else
{
    Console.WriteLine("Няма двойка за 43 €");
}

Отговор

19 € + 24 €

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

12 € + 31 €

Пробвай

Попълни

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

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            ;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

Пробвай

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

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

int[] prices = [3, 5, 8, 12, 15, 19, 24, 27, 31, 36];
var pair = FindPair(prices, 50);
if (pair is (int lo, int hi))
{
    Console.WriteLine($"{prices[lo]} € + {prices[hi]} €");
}
else
{
    Console.WriteLine("Няма двойка за 50 €");
}

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

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

Виж го

Колко стъпки

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

static long steps = 0;

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        steps++;
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

int n = 1000;
int[] prices = new int[n];
for (int i = 0; i < n; i++)
{
    prices[i] = 2 * (i + 1);
}
int card = 2 * n + 1;
var pair = FindPair(prices, card);
Console.WriteLine("Двойка: " + (pair == null ? "няма" : "има"));
Console.WriteLine("Стъпки: " + 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 не пускаме, за да не замръзне страницата.

static (int, int)? FindPair(int[] prices, int card)
{
    int lo = 0;
    int hi = prices.Length - 1;
    while (lo < hi)
    {
        int sum = prices[lo] + prices[hi];
        if (sum == card)
        {
            return (lo, hi);
        }
        else if (sum < card)
        {
            lo++;
        }
        else
        {
            hi--;
        }
    }
    return null;
}

Всички двойки над 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] вече не е петият продукт от каталога. Ако ти трябват продуктите, подреди двойки (цена, продукт) или обекти по цена.

int[] prices = [27, 3, 36, 15, 8, 31, 19, 5, 24, 12];
Array.Sort(prices);
Console.WriteLine("[" + string.Join(", ", prices) + "]");
var pair = FindPair(prices, 50);
if (pair is (int lo, int hi))
{
    Console.WriteLine($"{prices[lo]} € + {prices[hi]} €");
}
else
{
    Console.WriteLine("Няма двойка за 50 €");
}

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

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

Виж го

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

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

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

static int[] Merge(int[] a, int[] b)
{
    int[] result = new int[a.Length + b.Length];
    int i = 0;
    int j = 0;
    int k = 0;
    while (i < a.Length && j < b.Length)
    {
        if (a[i] <= b[j])
        {
            result[k++] = a[i++];
        }
        else
        {
            result[k++] = b[j++];
        }
    }
    while (i < a.Length)
    {
        result[k++] = a[i++];
    }
    while (j < b.Length)
    {
        result[k++] = b[j++];
    }
    return result;
}

int[] web = [1003, 1007, 1012, 1020];
int[] phone = [1001, 1009, 1010, 1031, 1044];
Console.WriteLine("[" + string.Join(", ", Merge(web, phone)) + "]");

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

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

static int Unique(int[] prices)
{
    if (prices.Length == 0)
    {
        return 0;
    }
    int write = 1;
    for (int read = 1; read < prices.Length; read++)
    {
        if (prices[read] != prices[write - 1])
        {
            prices[write] = prices[read];
            write++;
        }
    }
    return write;
}

int[] prices = [5, 5, 8, 12, 12, 12, 19, 24, 24];
int k = Unique(prices);
Console.WriteLine("Различни цени: " + k);
Console.WriteLine("[" + string.Join(", ", prices[..k]) + "]");

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

Масивът в C# е с фиксирана дължина: функцията връща колко са различните, а програмата показва само тях (prices[..k]).

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

Виж го

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

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

static bool IsMirror(string code)
{
    int lo = 0;
    int hi = code.Length - 1;
    while (lo < hi)
    {
        if (code[lo] != code[hi])
        {
            return false;
        }
        lo++;
        hi--;
    }
    return true;
}

Console.WriteLine(IsMirror("AB7CC7BA"));
Console.WriteLine(IsMirror("AB7CD7BA"));

True
False

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

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

string code = "AB7CC7BA";
Console.WriteLine(code == new string(code.Reverse().ToArray()));

True

code.Reverse() е LINQ: минава по знаците отзад напред, а new string(… .ToArray()) ги събира в нов низ.

Отговорът е същият и пак е 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)

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

Бисквитки