- PVSM.RU - https://www.pvsm.ru -
Многие студенты, впервые сталкиваясь с описанием какой-нибудь хитроумной штуки, вроде алгоритма Кнута – Морриса – Пратта или красно-чёрных деревьев, тут же задаются вопросами: «К чему такие сложности? И это, кроме авторов учебников, кому-нибудь нужно?». Лучший способ доказать пользу алгоритмов – это примеры из жизни. Причём, в идеале – конкретные примеры применения широко известных алгоритмов в современных, повсеместно используемых, программных продуктах.
Посмотрим, что можно обнаружить в коде ядра Linux, браузера Chromium и ещё в некоторых проектах.
Практически любой большой программный продукт не обходится без реализаций собственных алгоритмов. Вот небольшой список алгоритмов, которые нашли применение в ядре Linux. В некоторых случаях мы приводим выдержки из комментариев к их реализации.
1. Связный список [2], двусвязный список [3], неблокирующий связный список [4] (lock-free linked list).
2. B+-дерево [5]. Обратите внимание на комментарии. В них есть ценные идеи, подсказанные практикой.
Сравнительно простая реализация B+-деревьев. Я написал её, когда разбирался с тем, как такие деревья работают. Потом довёл код до ума, чтобы им можно было пользоваться.
Тут применяется один нестандартный приём, которого не найти в книгах. А именно, значения возрастают справа налево, а не так, как принято в классической реализации – слева направо. Все занятые ячейки в узле расположены слева, все незанятые содержат значение NUL. При выполнении большинства действий производится однократный обход всех ячеек и остановка на первой ячейке, которая содержит NUL.
3. Список с учётом приоритета элементов [6] (priority sorted list). Подобная структура данных используется, например, в реализации мьютексов [7] и драйверов [8].
4. Красно-чёрные деревья [9] применяются в подсистемах планирования, для управления виртуально памятью, для отслеживания дескрипторов файлов, записей в директориях и в других случаях.
5. Деревья интервалов [10] (interval tree).
6. Деревья остатков [11] (radix tree) используются для управления памятью, в механизмах поиска NSF и в сетевых подсистемах.
Типичный пример использования деревьев остатков – хранение указателей на структуры, описывающие страницы памяти.
7. Очередь с приоритетом [12] (priority heap) нашла применение в механизме распределения ресурсов (control groups).
Простая очередь с приоритетом на основе двоичной кучи. Поддерживает только вставку элементов, размер задаётся при создании и не меняется в ходе работы. Реализация основана на описании, которое можно найти в Главе 7 первого издания книги «Алгоритмы: построение и анализ», Т. Кормена, Ч. Лейзерсона и Р. Ривеста.
8. Хэш-функции [13], в комментариях к реализации которых даются ссылки на работы Дональда Кнута и на исследование Чака Левера.
Дональд Кнут рекомендует использовать в мультипликативном хешировании простые числа, делящие некий интервал в соответствии с правилом золотого сечения. Верхняя граница интервала является максимальным целым числом, представленным машинным словом. Чак Левер подтверждает [14] эффективность такого подхода.
9. В некоторых местах, например, в коде этого драйвера [15], задействуются собственные хэш-функции.
Хэш-функция, использующая алгоритм кольцевого хеширования (rotating hash). Глава 6.4. третьего тома «Искусства программирования» Д. Кнута.
10. Хэш-таблицы используются для реализации индексных дескрипторов [16] (inode), для проверок целостности файловой системы [17] и в других случаях.
11. Битовые массивы [18] применяются для работы с флагами, прерываниями и так далее. Подробности о них можно найти в четвёртом томе «Искусства программирования» Д. Кнута.
12. Семафоры [19], циклические блокировки [20] (spin lock).
13. Двоичный поиск [21] используется при обработке прерываний, поиске в кэше [22] и в других случаях.
14. Двоичный поиск по B-деревьям [23] (binary search with B-trees).
15. Поиск в глубину [24] (depth first search) и вариант алгоритма, используемый в конфигурации директории [25].
Производится модифицированный проход поиска в глубину по дереву пространства имён, начинающийся (и заканчивающийся) в узле, заданном параметром start_handle. Функция-callback вызывается всякий раз, когда удаётся найти узел, соответствующий параметру, задающему тип. Если callback возвращает ненулевое значение, поиск немедленно прекращается и это значение возвращается туда, откуда был вызван поиск.
16. Поиск в ширину [26] (breadth first search) применяется для проверки корректности блокировки во время выполнения кода.
17. Сортировка слиянием [27] на связных списках используется в подсистеме сборки мусора [28], для управления файловой системой [29] и в других случаях.
18. Сортировка пузырьком [30]. Удивительно, но она тоже используется.
19. Алгоритм поиска подстроки в строке Кнута-Морриса-Пратта [31].
Реализован алгоритм сравнения строк Кнута-Морриса-Пратта, время его исполнения линейно зависит от входных данных. Подробности можно найти в книге «Алгоритмы: построение и анализ» Т. Кормена, Ч. Лейзерсона, Р. Ривеста и К. Штайна, в разделе «Алгоритм Кнута-Морриса-Пратта».
20. Алгоритм поиска подстроки в строке Бойера-Мура [32] (Boyer-Moore) с пояснениями и рекомендациями, касающимися возможных альтернатив.
Теоретической основой реализации алгоритма Бойера-Мура стали следующие источники.
» A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977 [33].
» Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004 [34].
Посмотрим, что интересного можно найти в коде Chromium.
1. Косое дерево [35] (splay tree).
Дерево, кроме прочего, параметризуется аллокатором. Память под списки выделяется либо в зоне ускоренного доступа (реализуется в классе Zone, обратите внимание на zone.h), либо в обычном свободном пространстве.
2. Диаграммы Вороного [36] задействованы в демонстрационном примере.
3. Алгоритм Брезенхэма [37] (Bresenham) используется в подсистеме управления вкладками (tabs).
А вот некоторые алгоритмы и структуры данных, которые есть в коде сторонних разработчиков, включённом в Chromium.
4. Двоичные деревья [38].
5. Красно-чёрные деревья [39].
Джулиан Уокер о красно-чёрных деревьях:
Красно-чёрные деревья — интересная тема. Предполагается, что они проще AVL-деревьев (их непосредственного конкурента), и на первый взгляд так оно и есть. Всё дело в быстрой и простой вставке новых элементов. Однако, если вникнуть в алгоритмы удаления элементов, красно-чёрные деревья преподносят немало сюрпризов. В то же время, в противовес дополнительным сложностям, и вставку, и удаление элементов можно реализовать так, чтобы они выполнялись за один проход.
6. АВЛ-деревья [40] (AVL tree).
7. Алгоритм поиска строки Рабина – Карпа [41] (Rabin – Karp) используется для сжатия данных.
8. Вычисление количества слов, допускаемых ациклическим конечным автоматом. [42]
9. Фильтр Блума [43] (Bloom), реализованный Apple Inc.
10. Алгоритм Брезенхэма [44].
Полагаем, на библиотечные реализации алгоритмов полезно обратить внимание. Создатели языков программирования, очевидно, считают, что это стоит потраченных времени и сил. К тому же, такие стандартные решения, тщательно протестированные, испытанные на практике множеством разработчиков, обычно предпочтительнее аналогичных «самописных». Хотя, конечно, всё зависит от потребностей программиста и от особенностей конкретного алгоритма или структуры данных.
1. Если рассматривать, например, языки C и Java, то в первом случае можно встретить больше самостоятельных реализаций базовых вещей, во втором, благодаря обширному стандартному API, подобное встречается реже. В C++-библиотеке STL можно найти реализацию списков, стеков, очередей, карт, векторов и алгоритмов для сортировки, поиска и работы с кучей.
2. Java API включает в себя реализацию огромного количества структур данных и алгоритмов.
3. Библиотека Boost C++ содержит алгоритмы наподобие поиска подстроки в строке Бойера-Мура и Кнута-Морриса-Пратта.
Это интересные эвристические алгоритмы. Реализация каждого из них зависит от потребностей системы и может опираться на разные структуры данных.
1. Алгоритм вытеснения элементов, которые не использовались дольше всего (Last Recently Used, LRU) можно реализовать различными способами. В ядре Linux имеется реализация, основанная на списках [45].
2. Среди других похожих алгоритмов можно выделить следующие. Это – алгоритм «первым вошёл – первым вышел» (First In First Out, FIFO), алгоритм вытеснения наименее часто используемых элементов (Last Frequently Used, LFU), алгоритм распределения нагрузки распределённой вычислительной системы методом перебора и упорядочения её элементов по круговому циклу (Round Robin, RR).
3. В системе VAX/VMS применялся один из вариантов FIFO.
4. «Часовой» алгоритм [46] (Clock) Ричарда Карра [47] нашёл применение в Linux для организации замещения страниц памяти.
5. Процессор Intel i860 использует политику случайного замещения.
6. Алгоритм кэширования с адаптивным замещением [48] (Adaptive Replacement Cache, ARC) применяется в некоторых контроллерах хранилищ данных IBM и до возникновения проблемы с патентом [49], использовался в PostgreSQL.
7. Алгоритм двойников для выделения памяти [50] (buddy memory allocation), описанный Д. Кнутом в первом томе «Искусства программирования», применяется в ядре Linux, в параллельной системе выделения памяти jemalloc, используемой в FreeBSD и в Facebook [51].
1. Утилиты grep и awk реализуют алгоритм Томсона-Мак-нотона-Ямады (Thompson-McNaughton-Yamada) для построения недетерминированных конечных автоматов на основе регулярных выражений. Такой подход даже более эффективен, чем реализация соответствующих механизмов в Perl [52]
2. В tsort применяется топологическая сортировка (topological sort).
3. В коде утилиты fgrep можно обнаружить алгоритм поиска подстрок в строке Ахо – Корасик [53] (Aho-Corasick).
4. Утилита GNU grep реализует алгоритм Бойера-Мура [54].
5. В crypt(1) из Unix имеется вариант алгоритма шифрования, применявшийся в машине Enigma.
6. Утилита Unix diff [55], созданная Дугласом Макилроем (Doug McIlroy), основана на прототипе, написанном совместно с Джеймсом Хантом (James Hunt), обладает более высокой производительностью, чем стандартный алгоритм динамического программирования, используемый для вычисления расстояния Левенштейна (Levenshtein distance).
1. Восходящий алгоритм синтаксического разбора [56] (Look-Ahead LR parser, LALR). Реализован в yacc и bison.
2. Алгоритмы вычисления доминаторов (dominators) используются в большинстве оптимизирующих компиляторов, основанных на SSA.
3. Утилиты lex и flex компилируют регулярные выражения в NFA.
1. Алгоритмы сжатия Лемпеля-Зива [57] для графического формата GIF реализованы в различных приложениях для обработки изображений – от простой *nix-утилиты convert до гораздо более сложных программных комплексов.
2. Алгоритм кодирования длин серий (run-length encoding, RLE) применяется при создании PCX-файлов (используется во всем известном Paintbrush), сжатых BMP и TIFF-файлов.
3. Вейвлет-сжатие – это основа невероятно распространённого формата JPEG 2000. Каждый цифровой фотоаппарат, который умеет сохранять снимки в формате JPEG 2000, является «носителем» этого алгоритма.
4. Алгоритм коррекции ошибок Рида-Соломона задействован в ядре Linux [58]. Кроме того, он используется при хранении информации на CD-дисках, в устройствах для чтения штрих-кодов. Да что там говорить, его, вместе с алгоритмом свёртки, использовали для передачи изображений с космического аппарата
С 2000-го года время выполнения алгоритмов, решающих задачу выполнимости булевых формул, постоянно уменьшалось. Всё дело в применении новых подходов к решению таких задач. В частности, речь идёт об алгоритме управляемого конфликтами обучения дизъюнктам (Conflict Driven Clause Learning). Он является комбинацией алгоритма распространения булевых ограничений (Boolean Constraint propagation) из работы Дэвиса, Логемана и Лавленда (Davis, Logemann, Loveland) с методикой обучения дизъюнктам, которая берёт начало в технике программирования ограничениями (constraint programming) и в исследованиях, посвящённых искусственному интеллекту.
Применения подобных алгоритмов (SAT-решателей) весьма обширны. Например – это автоматическое доказательство теорем, тестирование аппаратного и программного обеспечения. IBM, Intel и многие другие компании имеют собственные реализации SAT-решателей. Многие менеджеры пакетов так же использует подобный алгоритм для разрешения зависимостей.
Существует великое множество алгоритмов и примеров их практического применения. Хочется верить, наш рассказ о некоторых из них убедил тех, кто задавался вопросом: «Зачем это всё?», в том, что алгоритмы стоят того, чтобы потратить время на знакомство с ними. А если алгоритмы и структуры данных – ваши давние друзья, надеемся, вы нашли здесь что-нибудь новое и полезное для себя.
О, а приходите к нам работать? :)wunderfund.io [59] — молодой фонд, который занимается высокочастотной алготорговлей [60]. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.Мы предлагаем интересные и сложные задачи по анализу данных и low latency разработке для увлеченных исследователей и программистов.
Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь.Присоединяйтесь к нашей команде: wunderfund.io [59]
Автор: Wunder Fund
Источник [61]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/razrabotka/112307
Ссылки в тексте:
[1] Image: https://habrahabr.ru/company/wunderfund/blog/277143/
[2] Связный список: https://github.com/mirrors/linux-2.6/blob/master/lib/llist.c
[3] двусвязный список: https://github.com/mirrors/linux-2.6/blob/master/include/linux/list.h
[4] неблокирующий связный список: https://github.com/mirrors/linux-2.6/blob/master/include/linux/llist.h
[5] B+-дерево: https://github.com/mirrors/linux-2.6/blob/39caa0916ef27cf1da5026eb708a2b8413156f75/lib/btree.c
[6] Список с учётом приоритета элементов: https://github.com/mirrors/linux-2.6/blob/master/include/linux/plist.h
[7] мьютексов: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/rtmutex.h
[8] драйверов: https://github.com/mirrors/linux-2.6/blob/f0d55cc1a65852e6647d4f5d707c1c9b5471ce3c/drivers/powercap/intel_rapl.c
[9] Красно-чёрные деревья: https://github.com/mirrors/linux-2.6/blob/master/include/linux/rbtree.h
[10] Деревья интервалов: https://github.com/mirrors/linux-2.6/blob/master/include/linux/interval_tree.h
[11] Деревья остатков: https://github.com/mirrors/linux-2.6/blob/master/include/linux/radix-tree.h
[12] Очередь с приоритетом: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/prio_heap.h
[13] Хэш-функции: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/include/linux/hash.h
[14] подтверждает: http://www.citi.umich.edu/techreports/reports/citi-tr-00-1.pdf
[15] этого драйвера: https://github.com/mirrors/linux-2.6/blob/0b1e73ed225d8f7aeef96b74147215ca8b990dce/drivers/staging/lustre/lustre/lov/lov_pool.c
[16] индексных дескрипторов: https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/fs/inode.c
[17] целостности файловой системы: https://github.com/mirrors/linux-2.6/blob/ff812d724254b95df76b7775d1359d856927a840/fs/btrfs/check-integrity.c
[18] Битовые массивы: https://github.com/mirrors/linux-2.6/blob/master/include/linux/bitmap.h
[19] Семафоры: https://github.com/mirrors/linux-2.6/blob/master/include/linux/semaphore.h
[20] циклические блокировки: https://github.com/mirrors/linux-2.6/blob/master/include/linux/spinlock.h
[21] Двоичный поиск: https://github.com/mirrors/linux-2.6/blob/master/lib/bsearch.c
[22] поиске в кэше: https://github.com/mirrors/linux-2.6/blob/10d0c9705e80bbd3d587c5fad24599aabaca6688/drivers/base/regmap/regcache.c
[23] Двоичный поиск по B-деревьям: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/fs/befs/btree.c
[24] Поиск в глубину: https://github.com/mirrors/linux-2.6/blob/a9238741987386bb549d61572973c7e62b2a4145/drivers/acpi/acpica/nswalk.c
[25] конфигурации директории: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/fs/configfs/dir.c
[26] Поиск в ширину: https://github.com/mirrors/linux-2.6/blob/4fbf888accb39af423f271111d44e8186f053723/kernel/locking/lockdep.c
[27] Сортировка слиянием: https://github.com/mirrors/linux-2.6/blob/master/lib/list_sort.c
[28] сборки мусора: https://github.com/mirrors/linux-2.6/blob/42a2d923cc349583ebf6fdd52a7d35e1c2f7e6bd/fs/ubifs/gc.c
[29] файловой системой: https://github.com/mirrors/linux-2.6/blob/ff812d724254b95df76b7775d1359d856927a840/fs/btrfs/raid56.c
[30] Сортировка пузырьком: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/drivers/media/common/saa7146/saa7146_hlp.c
[31] Кнута-Морриса-Пратта: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/ts_kmp.c
[32] Бойера-Мура: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/ts_bm.c
[33] A Fast String Searching Algorithm, R.S. Boyer and Moore. Communications of the Association for Computing Machinery, 20(10), 1977: http://www.cs.utexas.edu/users/moore/publications/fstrpos.pdf
[34] Handbook of Exact String Matching Algorithms, Thierry Lecroq, 2004: http://www-igm.univ-mlv.fr/~lecroq/string/string.pdf
[35] Косое дерево: https://code.google.com/p/chromium/codesearch#chromium/src/v8/src/splay-tree.h
[36] Диаграммы Вороного: https://code.google.com/p/chromium/codesearch#chromium/src/native_client_sdk/src/examples/demo/voronoi/index.html
[37] Алгоритм Брезенхэма: https://code.google.com/p/chromium/codesearch#chromium/src/chrome/browser/ui/cocoa/tabs/tab_strip_controller.mm
[38] Двоичные деревья: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/bintree.py
[39] Красно-чёрные деревья: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/rbtree.py
[40] АВЛ-деревья: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/bintrees/bintrees/avltree.py
[41] Рабина – Карпа: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/zlib/deflate.c
[42] Вычисление количества слов, допускаемых ациклическим конечным автоматом.: https://code.google.com/p/chromium/codesearch#chromium/src/native_client/src/trusted/validator_ragel/dfa_traversal.py
[43] Фильтр Блума: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit/Source/wtf/BloomFilter.h
[44] Алгоритм Брезенхэма: https://code.google.com/p/chromium/codesearch#chromium/src/third_party/libvpx/source/libvpx/vp8/common/textblit.c
[45] основанная на списках: https://github.com/mirrors/linux-2.6/blob/master/include/linux/list_lru.h
[46] «Часовой» алгоритм: http://en.wikipedia.org/wiki/Page_replacement_algorithm#Clock
[47] Ричарда Карра: http://dl.acm.org/citation.cfm?id=4750
[48] Алгоритм кэширования с адаптивным замещением: http://en.wikipedia.org/wiki/Adaptive_Replacement_Cache
[49] проблемы с патентом: http://www.varlena.com/GeneralBits/96.php
[50] Алгоритм двойников для выделения памяти: http://en.wikipedia.org/wiki/Buddy_memory_allocation
[51] Facebook: http://www.facebook.com/notes/facebook-engineering/scalable-memory-allocation-using-jemalloc/480222803919
[52] реализация соответствующих механизмов в Perl: http://swtch.com/~rsc/regexp/regexp1.html
[53] Ахо – Корасик: http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm
[54] реализует алгоритм Бойера-Мура: http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html
[55] Unix diff: http://www.cs.dartmouth.edu/~doug/diff.pdf
[56] Восходящий алгоритм синтаксического разбора: http://en.wikipedia.org/wiki/LALR_parser
[57] Лемпеля-Зива: http://en.wikipedia.org/wiki/Lempel_Ziv
[58] ядре Linux: https://github.com/mirrors/linux-2.6/blob/b3a3a9c441e2c8f6b6760de9331023a7906a4ac6/lib/reed_solomon/reed_solomon.c
[59] wunderfund.io: http://wunderfund.io
[60] высокочастотной алготорговлей: https://en.wikipedia.org/wiki/High-frequency_trading
[61] Источник: https://habrahabr.ru/post/277143/
Нажмите здесь для печати.