В предыдущем уроке мы увидели, как сильно меняется поведение программы, когда объем входных данных вырастает в сотни раз. Но почему один подход совершает миллионы холостых действий, а другой справляется за считаные мгновения?

Начинающие разработчики часто ищут ответ исключительно в алгоритме. Кажется, что достаточно найти какую-то особенную последовательность инструкций, и код сразу заработает с предельной скоростью. Однако алгоритм никогда не действует в вакууме. Он всегда обрабатывает конкретную информацию, а эта информация может располагаться в памяти компьютера совершенно по-разному.

Способ организации данных напрямую определяет, какие шаги процессор вообще может выполнить. Алгоритм и структура данных — это две неразделимые стороны единого инженерного решения. Попытка написать быстрый алгоритм для неподходящей структуры похожа на попытку разогнать гоночный автомобиль по вспаханному полю: двигатель работает на полную мощность, но среда не дает развить скорость.

Форма определяет действие

Чтобы увидеть эту связь в реальном мире, достаточно заглянуть в мастерскую автосервиса.

Когда слесарь сваливает пятьдесят гаечных ключей в один глубокий ящик вперемешку, у него остается единственный способ найти инструмент на четырнадцать: брать каждый попавшийся ключ вслепую, читать выбитый номер и откладывать в сторону неподходящие. Если нужный ключ лежит на самом дне, придется по очереди осмотреть все пятьдесят штук. Порядок действий (алгоритм поиска) жестко продиктован тем, как именно сложены инструменты (структурой хранения).

Если же на стене закреплен стенд с подписанными ячейками, где ключи развешаны строго по номерам, поиск меняется полностью. Взгляд сразу падает на сектор средних размеров, а рука тянется к ячейке с нужной цифрой. Человек находит инструмент за одно движение. Скорость выросла не потому, что мастер стал быстрее двигать руками. Изменилась организация предметов, и эта организация открыла принципиально новый способ действия.

В оперативной памяти компьютера действуют точно такие же законы.

Что такое структура данных

В коде на C# мы постоянно оперируем значениями: идентификаторами пользователей, строками текста, финансовыми транзакциями. Но сама по себе память компьютера — это просто гигантская последовательность пронумерованных байтов. Чтобы программа могла осмысленно работать со значениями, нам нужно договориться: как эти элементы расположены относительно друг друга, как они связаны между собой и какие операции с ними разрешены.

Каждая структура задает свои правила:

• Непрерывный блок ячеек памяти, где элементы лежат вплотную друг за другом, образует массив (array). Мы можем мгновенно прочитать любое значение по его порядковому номеру (индексу), но вставка нового элемента в середину потребует физического сдвига всех последующих соседей.
• Массив, элементы которого заранее упорядочены по возрастанию, дает возможность отсекать при поиске сразу половину неподходящих вариантов на каждом шаге.
• Таблица соответствий пар «ключ — значение», или словарь (dictionary / hash map), организует доступ через вычисление позиции по ключу, позволяя находить нужный объект без последовательного перебора всей коллекции.

Один набор значений — две разные стратегии

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

Перед нами восемь номеров билетов. Требуется выяснить, содержится ли среди них номер 61.

Вариант 1. Данные не упорядочены

Билеты записаны в список в том порядке, в котором их выдавала система:

Индекс:    [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
Значение:   74    19    93     8    42    61    88    35

Какую последовательность действий мы можем применить? Поскольку числа расположены хаотично, искомый номер может находиться абсолютно в любой ячейке.

1. Проверяем ячейку [0]: там лежит 74. Это не 61. Идем дальше.
2. Проверяем ячейку [1]: там 19. Снова не совпало.
3. Проверяем ячейку [2]: там 93. Мимо.
4. Проверяем ячейку [3]: там 8. Не то.
5. Проверяем ячейку [4]: там 42. Снова мимо.
6. Проверяем ячейку [5]: там 61. Значение найдено, поиск завершен.

Этот подход называется линейным поиском (linear search). Нам потребовалось шесть шагов. Если бы мы искали номер 35, пришлось бы проверить все восемь элементов. Если бы билета вообще не было в списке, мы были бы обязаны честно просмотреть весь массив до самого конца, чтобы убедиться в его отсутствии.

Для восьми элементов это незаметно. Но если в списке хранится миллион записей, в худшем случае программе придется выполнить ровно миллион сравнений.

Вариант 2. Данные упорядочены по возрастанию

Изменим форму хранения. Договоримся, что элементы в массиве всегда отсортированы от меньшего к большему:

Индекс:    [0]   [1]   [2]   [3]   [4]   [5]   [6]   [7]
Значение:    8    19    35    42    61    74    88    93

Количество элементов осталось прежним, сами значения не изменились. Однако теперь коллекция обладает важным свойством: для любого элемента все числа слева от него строго меньше, а все числа справа — больше.

Это свойство позволяет применить двоичный поиск (binary search):

1. Мы не начинаем с края. Мы сразу берем элемент в середине массива — например, ячейку [3] со значением 42.
2. Сравниваем: число 61 больше или меньше, чем 42? Больше.
3. Это сравнение дает ключевой результат: нам больше незачем проверять ячейки [0], [1], [2] и [3]. Мы точно знаем, что числа 8, 19, 35 и 42 меньше искомого. Одним действием мы выбросили из рассмотрения целую половину массива!
4. Теперь поиск продолжается только в правой части: [61, 74, 88, 93]. Снова смотрим в середину этого диапазона — на ячейку [5] со значением 74.
5. Сравниваем: 61 меньше, чем 74. Значит, правее 74 искать нечего. Отбрасываем 74, 88 и 93.
6. Остается единственный кандидат — ячейка [4] со значением 61. Цель найдена.

Нам потребовалось три шага вместо шести.

Если увеличить размер коллекции до миллиона элементов, линейный поиск потребует до миллиона проверок. Двоичный поиск на упорядоченном массиве найдет нужное значение максимум за двадцать шагов, потому что каждое сравнение делит оставшуюся область поиска пополам.

Обратите внимание: двоичный поиск принципиально невозможно запустить на неотсортированном списке. Алгоритм полностью опирается на взаимное расположение элементов в структуре данных.

Закон сохранения усилий: цена порядка

Увидев разницу между миллионом операций и двадцатью, легко прийти к мысли: почему бы не хранить абсолютно все коллекции в отсортированном виде?

Сравним две частые операции: поиск и добавление нового элемента.

В неупорядоченный список добавить новое значение предельно просто. Пришел новый билет с номером 50 — мы дописываем его в конец массива за одно действие. Однако расплатой за эту простоту становится медленный линейный поиск.

В упорядоченном массиве добавление становится тяжелой процедурой. Мы не можем записать число 50 в конец, ведь это разрушит порядок возрастания и сделает двоичный поиск невозможным. Программе придется:

1. Найти позицию, куда должно встать число 50 (между 42 и 61).
2. Сдвинуть вправо на одну ячейку все последующие элементы: 61, 74, 88 и 93, чтобы освободить место.
3. Записать 50 в освободившуюся ячейку с индексом 4.

Если в массиве хранится миллион элементов, вставка нового числа в самое начало потребует перемещения в памяти всех миллиона соседних ячеек.

Выбор между структурами зависит от характера нагрузки:

• Если приложение редко добавляет новые записи, но выполняет тысячи поисковых запросов в секунду (как каталог товаров или телефонная книга), выгодно потратить ресурсы на сортировку и использовать двоичный поиск.
• Если система ежесекундно записывает непрерывный поток данных с датчиков, а поиск выполняет редко при авариях, выгоднее складывать элементы подряд без сортировки, не тратя время процессора на сдвиги памяти.

Как структура диктует реализацию на C#

Посмотрим, как эти два подхода выражаются в коде. Логика каждого метода прямо следует из свойств структуры данных, с которой он работает.

public class SearchDemonstration
{
    // Поиск в неупорядоченном списке:
    // единственная доступная стратегия — последовательный проход по всем ячейкам.
    public static int LinearSearch(List<int> numbers, int target)
    {
        for (int i = 0; i < numbers.Count; i++)
        {
            if (numbers[i] == target)
            {
                return i; // Элемент найден, возвращаем его индекс
            }
        }

        return -1; // Просмотрели весь список, элемента нет
    }

    // Поиск в упорядоченном массиве:
    // порядок элементов позволяет динамически сжимать границы поиска.
    public static int BinarySearch(int[] sortedNumbers, int target)
    {
        int left = 0;
        int right = sortedNumbers.Length - 1;

        while (left <= right)
        {
            // Вычисляем середину текущего диапазона
            int middle = left + (right - left) / 2;

            if (sortedNumbers[middle] == target)
            {
                return middle; // Точное совпадение
            }

            if (sortedNumbers[middle] < target)
            {
                // Искомое значение больше середины — отбрасываем левую часть
                left = middle + 1;
            }
            else
            {
                // Искомое значение меньше середины — отбрасываем правую часть
                right = middle - 1;
            }
        }

        return -1; // Границы сомкнулись, число в массиве отсутствует
    }
}

Обратите внимание на вычисление середины в BinarySearch: выражение left + (right - left) / 2 математически эквивалентно (left + right) / 2, но защищает программу от переполнения целочисленного типа int, если сумма двух больших индексов превысит максимально допустимое значение.

Метод BinarySearch полагается на то, что массив гарантированно отсортирован. Если передать в него хаотичный список чисел, метод вернет неверный ответ из-за нарушения контракта между алгоритмом и структурой.

В стандартной библиотеке .NET уже есть готовые реализации вроде Array.BinarySearch() и метода экземпляра List<T>.BinarySearch(). В практических проектах надежнее использовать готовые библиотечные инструменты, однако инженер должен понимать механику их работы, чтобы не вызывать двоичный поиск там, где нарушены условия его применения.

Переносимость идей между языками

Конкретные классы C# — массивы int[], списки List<T>, словари Dictionary<TKey, TValue> — это реализация общих концепций на платформе .NET.

Когда вы переходите в другой стек технологий, вы встречаете другие имена, но те же самые структуры данных:

• Непрерывный список переменной емкости в C# называется List<T>, в Java — ArrayList, в Python — list, а в JavaScript — Array.
• Хеш-таблица с быстрым поиском по ключу в C# представлена классом Dictionary<TKey, TValue>, в Java — HashMap, в Python — dict, а в JavaScript — Map.

Если вы понимаете физическое устройство непрерывного массива и причину дороговизны вставки в его середину, это знание работает одинаково в любой среде разработки. Синтаксис объявления коллекции изменится, но стоимость базовых операций в памяти останется прежней.

Скрытая стоимость короткого кода

Компактная библиотечная запись ничего не говорит о количестве работы внутри неё. Например, наличие идентификатора в коллекции легко проверить одной строкой LINQ:

// Синтаксически кратко, но выполняет скрытый линейный поиск по всей коллекции
var exists = usersList.Any(u => u.Id == targetId);

Если поиск по идентификатору выполняется часто, данные выгоднее заранее организовать в Dictionary<int, User>. Для редкой проверки в маленьком списке обычный Any может оказаться проще и вполне достаточен. Выбор определяется не длиной записи, а размером коллекции и частотой требуемых операций.