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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В картотеке одна карточка описывает одного человека целиком: это запись (record), в коде обычно объект класса. Имя, адрес и телефон на карточке это её поля (field), в объекте его переменные. А то поле, по которому карточку ищут, называют ключом (key): ищем сотрудника по фамилии, значит фамилия ключ; у тех же данных ключей может быть несколько, сегодня фамилия, завтра телефон.

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

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

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

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

У выбора есть и вторая ось, которая в таблице спрятана в одном слове «память» напротив хеш-таблицы. Массив хранит только сами значения и лежит плотнее всех. Связанный список и дерево тратят на каждый элемент отдельный объект-узел с двумя-тремя ссылками, и это в несколько раз больше, чем занимает само значение. Хеш-таблица держит массив корзин заметно просторнее, чем данных, иначе ключи начинают сталкиваться, плюс узел на каждую запись.

Когда записей миллионы, разница между «четыре байта на число» и «сорок байт на число» становится разницей между «влезло в память» и «нет», и структуру выбирают не только по скорости операций. Цифры по каждой структуре есть в её статье, сводка в статье про выбор структуры.

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

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

Одно число на операцию при этом всегда с оговоркой, и её стоит замечать с первой таблицы. «Хеш-таблица ищет за O(1)» верно в среднем, на нормальных ключах; в худшем случае, когда ключи столпились в одной корзине, поиск дольше. «Быстрая сортировка за O(N·log N)» тоже в среднем, а на неудачных данных O(N²). А «вставка в массив за O(1)» верна амортизированно: почти всегда мгновенно, изредка дорогой переезд в больший массив. Поэтому рядом со сложностью в статьях раздела стоит пометка, какой случай имеется в виду, и для сервиса, где важна каждая задержка, смотрят на худший, а для пакетной обработки на средний.

Как это сделано в стандартной библиотеке

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) + " сразу";
    }
}

package main

import "fmt"

func main() {
	fmt.Println(find(10))
	fmt.Println(find(1000))
}

func find(size int) string {
	list := make([]string, 0, size)
	index := make(map[string]int, size)
	for i := 1; i <= size; i++ {
		key := fmt.Sprintf("key-%d", i)
		list = append(list, key)
		index[key] = i
	}
	target := fmt.Sprintf("key-%d", size)
	compared := 0
	for _, key := range list {
		compared++
		if key == target {
			break
		}
	}
	return fmt.Sprintf("%d записей: перебор среза — %d сравнений, map вернула %d сразу",
		size, compared, index[target])
}

function find(size) {
  const list = [];
  const index = new Map();
  for (let i = 1; i <= size; i++) {
    list.push(`key-${i}`);
    index.set(`key-${i}`, i);
  }
  const target = `key-${size}`;
  let compared = 0;
  for (const key of list) {
    compared++;
    if (key === target) break;
  }
  return `${size} записей: перебор массива — ${compared} сравнений, Map вернула ${index.get(target)} сразу`;
}

console.log(find(10));
console.log(find(1000));

def find(size: int) -> str:
    items = []
    index = {}
    for i in range(1, size + 1):
        items.append(f"key-{i}")
        index[f"key-{i}"] = i
    target = f"key-{size}"
    compared = 0
    for key in items:
        compared += 1
        if key == target:
            break
    return f"{size} записей: перебор списка — {compared} сравнений, dict вернул {index[target]} сразу"


print(find(10))
print(find(1000))

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

Коротко

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

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

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