Посмотрим, что можно обнаружить в коде ядра 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. Двоичные деревья.
Джулиан Уокер о красно-чёрных деревьях:
Красно-чёрные деревья — интересная тема. Предполагается, что они проще 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
This entry passed through the Full-Text RSS service - if this is your content and you're reading it on someone else's site, please read the FAQ at http://ift.tt/jcXqJW.
Комментариев нет:
Отправить комментарий