Многие студенты, впервые сталкиваясь с описанием какой-нибудь хитроумной штуки, вроде алгоритма Кнута – Морриса – Пратта или красно-чёрных деревьев, тут же задаются вопросами: «К чему такие сложности? И это, кроме авторов учебников, кому-нибудь нужно?». Лучший способ доказать пользу алгоритмов – это примеры из жизни. Причём, в идеале – конкретные примеры применения широко известных алгоритмов в современных, повсеместно используемых, программных продуктах.
Посмотрим, что можно обнаружить в коде ядра Linux, браузера Chromium и ещё в некоторых проектах.
Практически любой большой программный продукт не обходится без собственных реализаций известных алгоритмов. Вот небольшой список алгоритмов, которые нашли применение в ядре Linux. В некоторых случаях мы приводим выдержки из комментариев к их реализации.
1. Связный список, двусвязный список, неблокирующий связный список (lock-free linked list).
2. B+-дерево. Обратите внимание на комментарии. В них есть ценные идеи, подсказанные практикой.
3. Список с учётом приоритета элементов (priority sorted list). Подобная структура данных используется, например, в реализации мьютексов и драйверов.
4. Красно-чёрные деревья применяются в подсистемах планирования, для управления виртуально памятью, для отслеживания дескрипторов файлов, записей в директориях и в других случаях.
5. Деревья интервалов (interval tree).
6. Деревья остатков (radix tree) используются для управления памятью, в механизмах поиска NSF и в сетевых подсистемах.
Типичный пример использования деревьев остатков – хранение указателей на структуры, описывающие страницы памяти.
7. Очередь с приоритетом (priority heap) нашла применение в механизме распределения ресурсов (control groups).
8. Хэш-функции, в комментариях к реализации которых даются ссылки на работы Дональда Кнута и на исследование Чака Левера.
9. В некоторых местах, например, в коде этого драйвера, задействуются собственные хэш-функции.
10. Хэш-таблицы используются для реализации индексных дескрипторов (inode), для проверок целостности файловой системы и в других случаях.
11. Битовые массивы применяются для работы с флагами, прерываниями и так далее. Подробности о них можно найти в четвёртом томе «Искусства программирования» Д. Кнута.
12. Семафоры, циклические блокировки (spin lock).
13. Двоичный поиск используется при обработке прерываний, поиске в кэше и в других случаях.
14. Двоичный поиск по B-деревьям (binary search with B-trees).
15. Поиск в глубину (depth first search) и вариант алгоритма, используемый в конфигурации директории.
16. Поиск в ширину (breadth first search) применяется для проверки корректности блокировки во время выполнения кода.
17. Сортировка слиянием на связных списках используется в подсистеме сборки мусора, для управления файловой системой и в других случаях.
18. Сортировка пузырьком. Удивительно, но она тоже используется.
19. Алгоритм поиска подстроки в строке Кнута-Морриса-Пратта.
20. Алгоритм поиска подстроки в строке Бойера-Мура (Boyer-Moore) с пояснениями и рекомендациями, касающимися возможных альтернатив.
Теоретической основой реализации алгоритма Бойера-Мура стали следующие источники.
» A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977.
» Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004.
Посмотрим, что интересного можно найти в коде Chromium.
1. Косое дерево (splay tree).
2. Диаграммы Вороного задействованы в демонстрационном примере.
3. Алгоритм Брезенхэма (Bresenham) используется в подсистеме управления вкладками (tabs).
А вот некоторые алгоритмы и структуры данных, которые есть в коде сторонних разработчиков, включённом в Chromium.
4. Двоичные деревья.
5. Красно-чёрные деревья.
Джулиан Уокер о красно-чёрных деревьях:
6. АВЛ-деревья (AVL tree).
7. Алгоритм поиска строки Рабина – Карпа (Rabin – Karp) используется для сжатия данных.
8. Вычисление количества слов, допускаемых ациклическим конечным автоматом.
9. Фильтр Блума (Bloom), реализованный Apple Inc.
10. Алгоритм Брезенхэма.
Полагаем, на библиотечные реализации алгоритмов полезно обратить внимание. Создатели языков программирования, очевидно, считают, что это стоит потраченных времени и сил. К тому же, такие стандартные решения, тщательно протестированные, испытанные на практике множеством разработчиков, обычно предпочтительнее аналогичных «самописных». Хотя, конечно, всё зависит от потребностей программиста и от особенностей конкретного алгоритма или структуры данных.
1. Если рассматривать, например, языки C и Java, то в первом случае можно встретить больше самостоятельных реализаций базовых вещей, во втором, благодаря обширному стандартному API, подобное встречается реже. В C++-библиотеке STL можно найти реализацию списков, стеков, очередей, карт, векторов и алгоритмов для сортировки, поиска и работы с кучей.
2. Java API включает в себя реализацию огромного количества структур данных и алгоритмов.
3. Библиотека Boost C++ содержит алгоритмы наподобие поиска подстроки в строке Бойера-Мура и Кнута-Морриса-Пратта.
Это интересные эвристические алгоритмы. Реализация каждого из них зависит от потребностей системы и может опираться на разные структуры данных.
1. Алгоритм вытеснения элементов, которые не использовались дольше всего (Last Recently Used, LRU) можно реализовать различными способами. В ядре Linux имеется реализация, основанная на списках.
2. Среди других похожих алгоритмов можно выделить следующие. Это – алгоритм «первым вошёл – первым вышел» (First In First Out, FIFO), алгоритм вытеснения наименее часто используемых элементов (Last Frequently Used, LFU), алгоритм распределения нагрузки распределённой вычислительной системы методом перебора и упорядочения её элементов по круговому циклу (Round Robin, RR).
3. В системе VAX/VMS применялся один из вариантов FIFO.
4. «Часовой» алгоритм (Clock) Ричарда Карра нашёл применение в Linux для организации замещения страниц памяти.
5. Процессор Intel i860 использует политику случайного замещения.
6. Алгоритм кэширования с адаптивным замещением (Adaptive Replacement Cache, ARC) применяется в некоторых контроллерах хранилищ данных IBM и до возникновения проблемы с патентом, использовался в PostgreSQL.
7. Алгоритм двойников для выделения памяти (buddy memory allocation), описанный Д. Кнутом в первом томе «Искусства программирования», применяется в ядре Linux, в параллельной системе выделения памяти jemalloc, используемой в FreeBSD и в Facebook.
1. Утилиты grep и awk реализуют алгоритм Томсона-Мак-нотона-Ямады (Thompson-McNaughton-Yamada) для построения недетерминированных конечных автоматов на основе регулярных выражений. Такой подход даже более эффективен, чем реализация соответствующих механизмов в Perl
2. В tsort применяется топологическая сортировка (topological sort).
3. В коде утилиты fgrep можно обнаружить алгоритм поиска подстрок в строке Ахо – Корасик (Aho-Corasick).
4. Утилита GNU grep реализует алгоритм Бойера-Мура.
5. В crypt(1) из Unix имеется вариант алгоритма шифрования, применявшийся в машине Enigma.
6. Утилита Unix diff, созданная Дугласом Макилроем (Doug McIlroy), основана на прототипе, написанном совместно с Джеймсом Хантом (James Hunt), обладает более высокой производительностью, чем стандартный алгоритм динамического программирования, используемый для вычисления расстояния Левенштейна (Levenshtein distance).
1. Восходящий алгоритм синтаксического разбора (Look-Ahead LR parser, LALR). Реализован в yacc и bison.
2. Алгоритмы вычисления доминаторов (dominators) используются в большинстве оптимизирующих компиляторов, основанных на SSA.
3. Утилиты lex и flex компилируют регулярные выражения в NFA.
1. Алгоритмы сжатия Лемпеля-Зива для графического формата GIF реализованы в различных приложениях для обработки изображений – от простой *nix-утилиты convert до гораздо более сложных программных комплексов.
2. Алгоритм кодирования длин серий (run-length encoding, RLE) применяется при создании PCX-файлов (используется во всем известном Paintbrush), сжатых BMP и TIFF-файлов.
3. Вейвлет-сжатие – это основа невероятно распространённого формата JPEG 2000. Каждый цифровой фотоаппарат, который умеет сохранять снимки в формате JPEG 2000, является «носителем» этого алгоритма.
4. Алгоритм коррекции ошибок Рида-Соломона задействован в ядре Linux. Кроме того, он используется при хранении информации на CD-дисках, в устройствах для чтения штрих-кодов. Да что там говорить, его, вместе с алгоритмом свёртки, использовали для передачи изображений с космического аппарата
С 2000-го года время выполнения алгоритмов, решающих задачу выполнимости булевых формул, постоянно уменьшалось. Всё дело в применении новых подходов к решению таких задач. В частности, речь идёт об алгоритме управляемого конфликтами обучения дизъюнктам (Conflict Driven Clause Learning). Он является комбинацией алгоритма распространения булевых ограничений (Boolean Constraint propagation) из работы Дэвиса, Логемана и Лавленда (Davis, Logemann, Loveland) с методикой обучения дизъюнктам, которая берёт начало в технике программирования ограничениями (constraint programming) и в исследованиях, посвящённых искусственному интеллекту.
Применения подобных алгоритмов (SAT-решателей) весьма обширны. Например – это автоматическое доказательство теорем, тестирование аппаратного и программного обеспечения. IBM, Intel и многие другие компании имеют собственные реализации SAT-решателей. Многие менеджеры пакетов так же использует подобный алгоритм для разрешения зависимостей.
Существует великое множество алгоритмов и примеров их практического применения. Хочется верить, наш рассказ о некоторых из них убедил тех, кто задавался вопросом: «Зачем это всё?», в том, что алгоритмы стоят того, чтобы потратить время на знакомство с ними. А если алгоритмы и структуры данных – ваши давние друзья, надеемся, вы нашли здесь что-нибудь новое и полезное для себя.
Посмотрим, что можно обнаружить в коде ядра Linux, браузера Chromium и ещё в некоторых проектах.
Структуры данных и алгоритмы в ядре Linux
Практически любой большой программный продукт не обходится без собственных реализаций известных алгоритмов. Вот небольшой список алгоритмов, которые нашли применение в ядре Linux. В некоторых случаях мы приводим выдержки из комментариев к их реализации.
1. Связный список, двусвязный список, неблокирующий связный список (lock-free linked list).
2. B+-дерево. Обратите внимание на комментарии. В них есть ценные идеи, подсказанные практикой.
Сравнительно простая реализация B+-деревьев. Я написал её, когда разбирался с тем, как такие деревья работают. Потом довёл код до ума, чтобы им можно было пользоваться.
Тут применяется один нестандартный приём, которого не найти в книгах. А именно, значения возрастают справа налево, а не так, как принято в классической реализации – слева направо. Все занятые ячейки в узле расположены слева, все незанятые содержат значение NUL. При выполнении большинства действий производится однократный обход всех ячеек и остановка на первой ячейке, которая содержит NUL.
3. Список с учётом приоритета элементов (priority sorted list). Подобная структура данных используется, например, в реализации мьютексов и драйверов.
4. Красно-чёрные деревья применяются в подсистемах планирования, для управления виртуально памятью, для отслеживания дескрипторов файлов, записей в директориях и в других случаях.
5. Деревья интервалов (interval tree).
6. Деревья остатков (radix tree) используются для управления памятью, в механизмах поиска NSF и в сетевых подсистемах.
Типичный пример использования деревьев остатков – хранение указателей на структуры, описывающие страницы памяти.
7. Очередь с приоритетом (priority heap) нашла применение в механизме распределения ресурсов (control groups).
Простая очередь с приоритетом на основе двоичной кучи. Поддерживает только вставку элементов, размер задаётся при создании и не меняется в ходе работы. Реализация основана на описании, которое можно найти в Главе 7 первого издания книги «Алгоритмы: построение и анализ», Т. Кормена, Ч. Лейзерсона и Р. Ривеста.
8. Хэш-функции, в комментариях к реализации которых даются ссылки на работы Дональда Кнута и на исследование Чака Левера.
Дональд Кнут рекомендует использовать в мультипликативном хешировании простые числа, делящие некий интервал в соответствии с правилом золотого сечения. Верхняя граница интервала является максимальным целым числом, представленным машинным словом. Чак Левер подтверждает эффективность такого подхода.
9. В некоторых местах, например, в коде этого драйвера, задействуются собственные хэш-функции.
Хэш-функция, использующая алгоритм кольцевого хеширования (rotating hash). Глава 6.4. третьего тома «Искусства программирования» Д. Кнута.
10. Хэш-таблицы используются для реализации индексных дескрипторов (inode), для проверок целостности файловой системы и в других случаях.
11. Битовые массивы применяются для работы с флагами, прерываниями и так далее. Подробности о них можно найти в четвёртом томе «Искусства программирования» Д. Кнута.
12. Семафоры, циклические блокировки (spin lock).
13. Двоичный поиск используется при обработке прерываний, поиске в кэше и в других случаях.
14. Двоичный поиск по B-деревьям (binary search with B-trees).
15. Поиск в глубину (depth first search) и вариант алгоритма, используемый в конфигурации директории.
Производится модифицированный проход поиска в глубину по дереву пространства имён, начинающийся (и заканчивающийся) в узле, заданном параметром start_handle. Функция-callback вызывается всякий раз, когда удаётся найти узел, соответствующий параметру, задающему тип. Если callback возвращает ненулевое значение, поиск немедленно прекращается и это значение возвращается туда, откуда был вызван поиск.
16. Поиск в ширину (breadth first search) применяется для проверки корректности блокировки во время выполнения кода.
17. Сортировка слиянием на связных списках используется в подсистеме сборки мусора, для управления файловой системой и в других случаях.
18. Сортировка пузырьком. Удивительно, но она тоже используется.
19. Алгоритм поиска подстроки в строке Кнута-Морриса-Пратта.
Реализован алгоритм сравнения строк Кнута-Морриса-Пратта, время его исполнения линейно зависит от входных данных. Подробности можно найти в книге «Алгоритмы: построение и анализ» Т. Кормена, Ч. Лейзерсона, Р. Ривеста и К. Штайна, в разделе «Алгоритм Кнута-Морриса-Пратта».
20. Алгоритм поиска подстроки в строке Бойера-Мура (Boyer-Moore) с пояснениями и рекомендациями, касающимися возможных альтернатив.
Теоретической основой реализации алгоритма Бойера-Мура стали следующие источники.
» A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977.
» Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004.
Структуры данных и алгоритмы в веб-браузере Chromium
Посмотрим, что интересного можно найти в коде Chromium.
1. Косое дерево (splay tree).
Дерево, кроме прочего, параметризуется аллокатором. Память под списки выделяется либо в зоне ускоренного доступа (реализуется в классе Zone, обратите внимание на zone.h), либо в обычном свободном пространстве.
2. Диаграммы Вороного задействованы в демонстрационном примере.
3. Алгоритм Брезенхэма (Bresenham) используется в подсистеме управления вкладками (tabs).
А вот некоторые алгоритмы и структуры данных, которые есть в коде сторонних разработчиков, включённом в Chromium.
4. Двоичные деревья.
5. Красно-чёрные деревья.
Джулиан Уокер о красно-чёрных деревьях:
Красно-чёрные деревья — интересная тема. Предполагается, что они проще AVL-деревьев (их непосредственного конкурента), и на первый взгляд так оно и есть. Всё дело в быстрой и простой вставке новых элементов. Однако, если вникнуть в алгоритмы удаления элементов, красно-чёрные деревья преподносят немало сюрпризов. В то же время, в противовес дополнительным сложностям, и вставку, и удаление элементов можно реализовать так, чтобы они выполнялись за один проход.
6. АВЛ-деревья (AVL tree).
7. Алгоритм поиска строки Рабина – Карпа (Rabin – Karp) используется для сжатия данных.
8. Вычисление количества слов, допускаемых ациклическим конечным автоматом.
9. Фильтр Блума (Bloom), реализованный Apple Inc.
10. Алгоритм Брезенхэма.
Алгоритмы в стандартных библиотеках популярных языков программирования
Полагаем, на библиотечные реализации алгоритмов полезно обратить внимание. Создатели языков программирования, очевидно, считают, что это стоит потраченных времени и сил. К тому же, такие стандартные решения, тщательно протестированные, испытанные на практике множеством разработчиков, обычно предпочтительнее аналогичных «самописных». Хотя, конечно, всё зависит от потребностей программиста и от особенностей конкретного алгоритма или структуры данных.
1. Если рассматривать, например, языки C и Java, то в первом случае можно встретить больше самостоятельных реализаций базовых вещей, во втором, благодаря обширному стандартному API, подобное встречается реже. В C++-библиотеке STL можно найти реализацию списков, стеков, очередей, карт, векторов и алгоритмов для сортировки, поиска и работы с кучей.
2. Java API включает в себя реализацию огромного количества структур данных и алгоритмов.
3. Библиотека Boost C++ содержит алгоритмы наподобие поиска подстроки в строке Бойера-Мура и Кнута-Морриса-Пратта.
Алгоритмы выделения ресурсов и планирования
Это интересные эвристические алгоритмы. Реализация каждого из них зависит от потребностей системы и может опираться на разные структуры данных.
1. Алгоритм вытеснения элементов, которые не использовались дольше всего (Last Recently Used, LRU) можно реализовать различными способами. В ядре Linux имеется реализация, основанная на списках.
2. Среди других похожих алгоритмов можно выделить следующие. Это – алгоритм «первым вошёл – первым вышел» (First In First Out, FIFO), алгоритм вытеснения наименее часто используемых элементов (Last Frequently Used, LFU), алгоритм распределения нагрузки распределённой вычислительной системы методом перебора и упорядочения её элементов по круговому циклу (Round Robin, RR).
3. В системе VAX/VMS применялся один из вариантов FIFO.
4. «Часовой» алгоритм (Clock) Ричарда Карра нашёл применение в Linux для организации замещения страниц памяти.
5. Процессор Intel i860 использует политику случайного замещения.
6. Алгоритм кэширования с адаптивным замещением (Adaptive Replacement Cache, ARC) применяется в некоторых контроллерах хранилищ данных IBM и до возникновения проблемы с патентом, использовался в PostgreSQL.
7. Алгоритм двойников для выделения памяти (buddy memory allocation), описанный Д. Кнутом в первом томе «Искусства программирования», применяется в ядре Linux, в параллельной системе выделения памяти jemalloc, используемой в FreeBSD и в Facebook.
Базовые утилиты *nix-систем
1. Утилиты grep и awk реализуют алгоритм Томсона-Мак-нотона-Ямады (Thompson-McNaughton-Yamada) для построения недетерминированных конечных автоматов на основе регулярных выражений. Такой подход даже более эффективен, чем реализация соответствующих механизмов в Perl
2. В tsort применяется топологическая сортировка (topological sort).
3. В коде утилиты fgrep можно обнаружить алгоритм поиска подстрок в строке Ахо – Корасик (Aho-Corasick).
4. Утилита GNU grep реализует алгоритм Бойера-Мура.
5. В crypt(1) из Unix имеется вариант алгоритма шифрования, применявшийся в машине Enigma.
6. Утилита Unix diff, созданная Дугласом Макилроем (Doug McIlroy), основана на прототипе, написанном совместно с Джеймсом Хантом (James Hunt), обладает более высокой производительностью, чем стандартный алгоритм динамического программирования, используемый для вычисления расстояния Левенштейна (Levenshtein distance).
Компиляторы
1. Восходящий алгоритм синтаксического разбора (Look-Ahead LR parser, LALR). Реализован в yacc и bison.
2. Алгоритмы вычисления доминаторов (dominators) используются в большинстве оптимизирующих компиляторов, основанных на SSA.
3. Утилиты lex и flex компилируют регулярные выражения в NFA.
Сжатие изображений и коррекция ошибок
1. Алгоритмы сжатия Лемпеля-Зива для графического формата GIF реализованы в различных приложениях для обработки изображений – от простой *nix-утилиты convert до гораздо более сложных программных комплексов.
2. Алгоритм кодирования длин серий (run-length encoding, RLE) применяется при создании PCX-файлов (используется во всем известном Paintbrush), сжатых BMP и TIFF-файлов.
3. Вейвлет-сжатие – это основа невероятно распространённого формата JPEG 2000. Каждый цифровой фотоаппарат, который умеет сохранять снимки в формате JPEG 2000, является «носителем» этого алгоритма.
4. Алгоритм коррекции ошибок Рида-Соломона задействован в ядре Linux. Кроме того, он используется при хранении информации на CD-дисках, в устройствах для чтения штрих-кодов. Да что там говорить, его, вместе с алгоритмом свёртки, использовали для передачи изображений с космического аппарата
Задача о выполнимости булевых формул
С 2000-го года время выполнения алгоритмов, решающих задачу выполнимости булевых формул, постоянно уменьшалось. Всё дело в применении новых подходов к решению таких задач. В частности, речь идёт об алгоритме управляемого конфликтами обучения дизъюнктам (Conflict Driven Clause Learning). Он является комбинацией алгоритма распространения булевых ограничений (Boolean Constraint propagation) из работы Дэвиса, Логемана и Лавленда (Davis, Logemann, Loveland) с методикой обучения дизъюнктам, которая берёт начало в технике программирования ограничениями (constraint programming) и в исследованиях, посвящённых искусственному интеллекту.
Применения подобных алгоритмов (SAT-решателей) весьма обширны. Например – это автоматическое доказательство теорем, тестирование аппаратного и программного обеспечения. IBM, Intel и многие другие компании имеют собственные реализации SAT-решателей. Многие менеджеры пакетов так же использует подобный алгоритм для разрешения зависимостей.
Выводы
Существует великое множество алгоритмов и примеров их практического применения. Хочется верить, наш рассказ о некоторых из них убедил тех, кто задавался вопросом: «Зачем это всё?», в том, что алгоритмы стоят того, чтобы потратить время на знакомство с ними. А если алгоритмы и структуры данных – ваши давние друзья, надеемся, вы нашли здесь что-нибудь новое и полезное для себя.
О, а приходите к нам работать? :)wunderfund.io — молодой фонд, который занимается высокочастотной алготорговлей. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.
Мы предлагаем интересные и сложные задачи по анализу данных и low latency разработке для увлеченных исследователей и программистов. Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь.
Присоединяйтесь к нашей команде: wunderfund.io
