Зачем нужны структуры данных и алгоритмы

← назад к разделу

Почти любая программа что-то хранит и что-то с этим делает: список товаров в корзине, сообщения в чате, точки на карте. Вопрос, который встаёт всегда, — как разложить эти данные, чтобы с ними было удобно и быстро работать. От ответа зависит, будет ли поиск нужной записи мгновенным или программа задумается на секунды, влезет ли всё в память и легко ли добавить новый элемент. Ответ на этот вопрос и дают структуры данных и алгоритмы. Этот раздел — маршрут по ним с нуля, от массива до графа.

Что такое структура данных и алгоритм

Структура данных — это способ организации данных в памяти (или на диске). Массив, связанный список, стек, дерево, хеш-таблица — всё это разные способы разложить одни и те же данные. Каждый способ по-своему хорош: один быстро ищет, другой быстро вставляет, третий экономит память.

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

• вставить новый элемент;
• найти нужный элемент;
• удалить элемент;
• перебрать все элементы по очереди;
• отсортировать элементы по порядку.

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

Три роли структур данных

Где это вообще пригодится? Условно — три большие области.

Хранение реальных данных. Данные о людях, товарах, заказах, операциях. Классическая аналогия — картотека с карточками: каждая карточка описывает одну сущность (человека, товар), а вся стопка — базу. Как только карточек становится много, возникают те самые вопросы: как быстро найти нужную, как добавить новую, как отсортировать по алфавиту. Реальные базы данных сложнее картотеки, но идея та же.

Инструментарий программиста. Не все структуры видит пользователь. Многие нужны самой программе как рабочий инструмент: стек, чтобы разобрать выражение или откатить действие; очередь, чтобы обработать задачи по порядку; приоритетная очередь, чтобы всегда доставать самое срочное. Это вспомогательные структуры «под капотом».

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

Базовые термины

Несколько слов, которые встречаются постоянно; проще договориться о них сразу.

• Запись (record) — логический блок, описывающий одну сущность целиком: одного человека, один товар, один заказ. В картотеке это одна карточка, а в коде — обычно объект класса.
• Поле (field) — отдельная часть записи: имя, адрес, телефон. В объекте это его переменная.
• Ключ (key) — поле, по которому ищут запись. Например, ищем сотрудника по фамилии — фамилия здесь ключ. У одних и тех же данных ключей может быть несколько: сегодня ищем по фамилии, завтра — по телефону.

Эти термины помогают говорить об операциях единообразно: «найти запись по ключу», «вставить запись», «удалить по ключу» — независимо от того, какая структура внутри.

Обзор: какая структура для чего

Главная мысль всего раздела: идеальной структуры нет — у каждой свои сильные и слабые стороны. Выбор всегда компромисс. Вот карта с высоты птичьего полёта; сейчас термины могут быть незнакомы — к каждому вернёмся в своей статье.

Запоминать таблицу не нужно — она станет очевидной по мере чтения.

Как измеряют «быстро» и «медленно»

Слова «быстро» и «медленно» скоро станут точными. Скорость алгоритма измеряют не в секундах (они зависят от железа), а в том, как растёт число операций с ростом объёма данных — это называют O-нотацией. Поиск в массиве перебором на миллионе элементов делает до миллиона шагов; двоичный поиск в упорядоченном массиве — около двадцати. Эту разницу и описывает O-нотация; подробно разберём её в статье про массивы и двоичный поиск.

Как это сделано в Java

Хорошая новость: почти всё из таблицы выше в Java уже написано — эти структуры лежат в стандартной библиотеке коллекций (Java Collections Framework). Свой связанный список или своё дерево в рабочем коде приходится писать редко. Но выбирать приходится каждый день, и цена ошибки ровно та же: взяли неподходящую структуру — получили медленный код там, где мог быть быстрый. Поэтому в статьях раздела у каждой структуры есть блок про её готовую реализацию: какой класс, что у него внутри и где он подводит. Вот карта целиком:

Разницу видно на десятке строк: положим одни и те же записи в ArrayList и в HashMap и поищем последнюю.

живой пример

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Lookup {
    public static void main(String[] args) {
        System.out.println(find(10));
        System.out.println(find(1000));
    }

    static String find(int size) {
        List<String> list = new ArrayList<>();
        Map<String, Integer> map = new HashMap<>();
        for (int i = 1; i <= size; i++) {
            list.add("key-" + i);
            map.put("key-" + i, i);
        }
        String target = "key-" + size;
        int compared = 0;
        for (String key : list) {
            compared++;
            if (key.equals(target)) break;
        }
        return size + " записей: перебор списка — " + compared
                + " сравнений, HashMap вернул " + map.get(target) + " сразу";
    }
}

Записей стало в сто раз больше — список ищет в сто раз дольше, а хеш-таблице всё равно. Это и есть O(N) против O(1).

Грабля, общая для всех. В Java тип переменной и настоящая структура — разные вещи. За объявлением List<String> items может стоять и ArrayList, и LinkedList, а items.get(i) стоит у них O(1) и O(N) соответственно. Тип говорит, что с данными можно делать; сколько это стоит, знает только конкретный класс. Поэтому, читая чужой код, смотрите на строчку с new, а не на объявление.

Коротко

• Структура данных — способ организации данных; алгоритм — шаги операций над ними (вставка, поиск, удаление, перебор, сортировка).
• Структуры нужны для трёх вещей: хранить реальные данные, служить инструментом программисту, моделировать задачи из мира.
• Базовый словарь — запись, поле, ключ — позволяет говорить об операциях единообразно.
• Идеальной структуры нет: каждая быстра в одном и медленна в другом, выбор — всегда компромисс под задачу.
• «Быстро» измеряют O-нотацией — тем, как растёт число операций с объёмом данных.

Что почитать дальше

• Математика для O-нотации — степени и логарифмы, если школьная математика подзабылась.
• Массивы, двоичный поиск и O-нотация — первая структура раздела и первая мерка скорости.
• Простая сортировка: пузырёк, выбор, вставка — три учебных алгоритма, на которых видно, откуда берётся O(N²).
• Как выбрать структуру данных — итог раздела: та же таблица, но уже с пониманием, почему так.