«Плохие программисты беспокоятся о коде. Хорошие программисты беспокоятся о структурах данных и их взаимосвязях», — Линус Торвальдс
Оглавление
Глава 1: Разрыв в производительности
Глава 3: Бенчмаркинг и профилирование
Глава 4: Массивы и локальность кэша
Глава 5: Связанные списки — убийцы кэша
Глава 7: Хэш-таблицы и конфликты кэша
Глава 8: Динамические массивы и управление памятью
Глава 9: Двоичные деревья поиска
Глава 10: B-деревья и деревья, эффективно использующие кэш
Глава 11: Префиксные деревья и базисные деревья
Глава 12: Кучи и очереди с приоритетом
Споры о планировщике
Наша команда вела спор о структурах данных. Нам нужен был планировщик задач операционной системы реального времени, способный:
Вставлять новые задачи с приоритетом (O(log n))
Запрашивать задачу с наибольшим приоритетом (O(1))
Удалять задачу с наибольшим приоритетом (O(log n))
Кто-то предложил: «Давайте используем отсортированный массив». Но вставка будет занимать O(n) — придётся сдвигать элементы.
Кто-то ещё сказал: «Возьмём связанный список». Однако поиск наибольшего выполняется за O(n) — необходимо сканировать весь список.
Третий вспомнил о двоичном дереве поиска. Но из Главы 9 мы уже знаем, что BST ужасно ведут себя с кэшем.
Споры продолжались, пока кто-то не упомянул двоичные кучи. Покончить с разногласиями позволили результаты бенчмарка:
$ perf stat -e cache-misses,cycles ./scheduler_heap Performance counter stats: 45,000 cache-misses 1,200,000 cycles $ perf stat -e cache-misses,cycles ./scheduler_bst Performance counter stats: 180,000 cache-misses 4,800,000 cycles
Куча оказалась в 4 раза быстрее, чем красно-чёрное дерево, а промахов кэша при этом было в 4 раза меньше.
Почему? Кучи хранятся в массивах, поэтому имеют замечательную локальность кэша.
Что нам рассказывают в учебниках
Двоичная куча — это завершённое двоичное дерево, в котором каждый родительский элемент больше (или не меньше) своих дочерних элементов.
Пример max-heap:
90 / \ 70 50 / \ / \ 40 30 20 10
Свойства:
Завершённое дерево: заполнены все уровни, за исключением, возможно, последнего, который заполняется слева направо
Свойство кучи: родительский элемент ≥ дочернего (max-heap) или родительский ≤ дочернего (min-heap)
-
Операции:
Вставка: O(log n) — добавление в конец, пузырьковое поднятие вверх
Extract max: O(log n) — удаление корня, пузырьковое опускание вниз
Peek max: O(1) — просто чтение корня
Что говорят в учебниках:
Идеально подходит для очередей с приоритетом
Вставка и удаление за O(log n)
Доступ к max/min за O(1)
Простота реализации
Выглядит здорово! Но не всё так просто...
Проверка реальностью: кучи на основе массивов
Самое важное наблюдение: можно хранить двоичную кучу в массиве при помощи индексной арифметики.
Куча как массив:
Индекс: 0 1 2 3 4 5 6 Массив: [90][70][50][40][30][20][10] Дерево: 90 (индекс 0) / \ 70 50 (индексы 1, 2) / \ / \ 40 30 20 10 (индексы 3, 4, 5, 6)
Индексная арифметика:
Родительский элемент узла i: (i - 1) / 2
Левый дочерний элемент узла i: 2i + 1
Правый дочерний элемент узла i: 2i + 2
Никаких указателей! Только индексы массива.
Вот реализация, которую я использовал:
typedef struct { int *data; int size; int capacity; } heap_t; void heap_insert(heap_t *heap, int value) { // Добавление в конец heap->data[heap->size] = value; int i = heap->size; heap->size++; // Поднятие вверх while (i > 0) { int parent = (i - 1) / 2; if (heap->data[i] <= heap->data[parent]) break; // Обмен местами с родителем int temp = heap->data[i]; heap->data[i] = heap->data[parent]; heap->data[parent] = temp; i = parent; } } int heap_extract_max(heap_t *heap) { int max = heap->data[0]; // Перемещение последнего элемента в корень heap->size--; heap->data[0] = heap->data[heap->size]; // Опускание вниз int i = 0; while (2 * i + 1 < heap->size) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < heap->size && heap->data[left] > heap->data[largest]) { largest = left; } if (right < heap->size && heap->data[right] > heap->data[largest]) { largest = right; } if (largest == i) break; // Обмен местами с самым большим дочерним элементом int temp = heap->data[i]; heap->data[i] = heap->data[largest]; heap->data[largest] = temp; i = largest; } return max; }
Поведение кэша:
Все данные находятся в сплошном массиве
При пузырьковом поднятии/опускании доступ выполняется к соседним элементам
Превосходная пространственная локальность
Именно поэтому куча оказалась в 4 раза быстрее красно-чёрного дерева. Никакого следования по указателям, только индексация массива.
Результаты бенчмарков
Я сравнил планировщик на основе кучи с другими структурами данных:
Датасет: 10 000 задач со случайными приоритетами Тест: 100 000 операций вставок + извлечения max Красно-чёрное дерево: Такты на операцию: 4 800 Промахи кэша: 18,0 Двоичная куча (на основе массива): Такты на операцию: 1 200 Промахи кэша: 4,5 Ускорение: 4,0× Отсортированный массив: Вставка: 12 000 тактов (сдвиг за O(n)) Извлечение max: 100 тактов (извлечение из конца за O(1)) В среднем: 6 050 тактов на операцию
При такой рабочей нагрузке куча оказалась явным победителем.
Почему куча побеждает:
На основе массива: все данные находятся рядом, превосходная локальность кэша
Сбалансированные операции: и вставка, и извлечение максимального выполняются за O(log n)
Нет следования по указателям: просто индексация массивов
Почему проигрывает отсортированный массив:
Вставка за O(n), потому что нужно сдвигать элементы
При нагрузках с большим количеством вставок они преобладают
Оптимизация с учётом кэша: d-арные кучи
У двоичных куч есть проблема: с ростом кучи операции пузырькового поднятия и опускания разбрасываются по куче.
В случае кучи с 1 миллионом элементов:
Высота: log₂(1M) ≈ 20 уровней
Пузырьковое опускание: 20 промахов кэша (каждый уровень — это другая линия кэша)
Решение: использовать d-арную кучу, в которой каждый узел имеет d дочерних элементов, а не 2.
4-арная куча:
Индекс: 0 1 2 3 4 5 6 7 8 9 10 11 12 Массив: [90][70][60][50][40][65][55][45][30][35][25][20][15] Дерево: 90 (индекс 0) / | | \ 70 60 50 40 (индексы 1, 2, 3, 4) /|\ /|\ /|\ /|\ ... (индексы 5-20)
Индексная арифметика (d-арная куча):
Родитель узла i: (i - 1) / d
Первый дочерний элемент узла i: d × i + 1
Последний дочерний элемент узла i: d × i + d
Компромиссы:
Более короткое дерево: высота = logd(n), а не log₂(n)
Больше сравнений на уровень: необходимо сравнивать d дочерних элементов, а не 2
Улучшенное поведение кэша: меньше уровней = меньше промахов кэша
Я протестировал разные значения d:
Датасет: 1 000 000 элементов Тест: 100 000 операций вставки + извлечения максимального Двоичная куча (d=2): Высота: 20 уровней Такты на операцию: 2 400 Промахи кэша: 8,5 4-арная куча (d=4): Высота: 10 уровней Такты на операцию: 1 600 Промахи кэша: 4,2 Ускорение: 1,5× 8-арная куча (d=8): Высота: 7 уровней Такты на операцию: 1 400 Промахи кэша: 2,8 Ускорение: 1.,7× 16-арная куча (d=16): Высота: 5 уровней Такты на операцию: 1,500 Промахи кэша: 2.1 Ускорение: 1,6× (эффективность уменьшается)
Идеальный вариант: d=8 для большинства нагрузок. Уменьшает промахи кэша в три раза, при этом сравнений на уровень не так много.
Пример из реального мира: планировщик CFS ядра Linux
В Completely Fair Scheduler (CFS) ядра Linux используется красно-чёрное дерево, а не куча. Почему?
Потому что планировщику требуется не просто получение задачи с наивысшим приоритетом:
Запросы по диапазонам: находить все задачи с приоритетом > X
Произвольное удаление: удаление конкретной задачи (не просто максимальной)
Справедливое планирование: отслеживание виртуальной среды исполнения, а не только приоритета
Кучи неспособны делать это эффективно. Они оптимизированы под одну задачу: операции над очередями с приоритетом (вставка, извлечение максимального).
Но для более простых планировщиков (например, во встраиваемых RTOS) кучи подходят идеально.
Пример: во FreeRTOS используется просто планировщик на основе приоритетов со структурой, близкой к куче (хоть и реализованной в виде связанного списка из-за малого количества задач).
Когда использовать кучи
После выбора куч для нашего планировщика RTOS я понял, что это было верным решением:
1. Очереди с приоритетом
Если вам нужны:
Вставка с приоритетом: O(log n)
Получение максимального/минимального: O(1)
Удаление максимального/минимального: O(log n)
то используйте кучу. Это стандартная структура данных для очередей с приоритетом.
Примеры:
Планировщики задач
Очереди событий
Алгоритм кратчайшего пути Дейкстры
Код Хаффмана
2. Задачи Top-K
Нахождение K наибольших/наименьших элементов в потоке:
Хранение кучи минимальных размера K
Если новый элемент больше, чем минимальный в куче, то заменяем минимальный
Конечная куча содержит K наибольших элементов
Время: O(n log k) вместо O(n log n) полной сортировки
3. Хранение медианы
Хранение медианы потока при помощи двух куч:
Куча максимальных для меньшей половины
Куча минимальных для большей половины
Медиана — это корень большей кучи (или среднее от обоих корней)
Время: O(log n) на вставку, O(1) на получение медианы
4. Когда НЕ использовать кучи
Не используйте кучи для:
Произвольного удаления: удаления некорневого элемента выполняется за O(n)
Поиска: нахождение произвольного элемента выполняется за O(n)
Запросов по диапазонам: невозможно эффективно находить все элементы в диапазоне
Итераций по отсортированному: кучи не обеспечивают полностью отсортированный порядок
Для этого используйте сбалансированное BST или B-дерево.
Подведём итог
Спор о планировщике позволили разрешить числа. Двоичная куча обеспечила производительность в четыре раза выше, чем красно-чёрное дерево, при этом имея в четыре раза меньше промахов кэша. Благодаря тому, что куча основана на массиве, обеспечивается локальность кэша, недостижимая для деревьев на основе указателей.
Ключевые наблюдения:
Кучи основаны на массивах. Никаких указателей, никакого следования по указателям, только индексация массивов. Это обеспечивает превосходную локальность кэша.
Завершённые двоичные деревья идеально умещаются в массивы. Индексная арифметика (родитель = (i-1)/2, дочерний элемент = 2i+1 и 2i+2) проста и удобна для кэша.
d-арные кучи снижают промахи кэша. Увеличив коэффициент ветвления до 4 или 8, можно снизить высоту дерева и промахи кэша в 2-3 раза
Кучи предназначены для очередей с приоритетом. Если вам нужны вставки, извлечение максимального и поиск максимального, то кучи подходят идеально. Но они не позволяют эффективно выполнять произвольные удаления и запросы по диапазонам.
Важен баланс. У двоичных куч (d=2) меньше сравнений на уровень. У 8-арных куч (d=8) меньше промахов кэша. Оптимальный выбор зависит от конкретной нагрузки.
Показатели из нашего планировщика RTOS:
Красно-чёрное дерево: 4 800 тактов на операцию, 18,0 промахов кэша
Двоичная куча: 1 200 тактов на операцию, 4,5 промаха кэша
8-арная куча: 1 400 тактов на операцию, 2,8 промаха кэша
Очевидно, что для нашего планировщика оптимальной была двоичная куча. Она простая, быстрая и удобная для кэша.
В следующей главе мы поговорим о графах и их представлениях в памяти.