Очень долгое время я не мог понять: когда я буду писать алгоритмы и структуры в продакшн коде также, как я это делал на олимпиаде? Время шло, а ничего сложнее бинарного поиска и расстояния Левенштейна не нужно было (все работало и так быстро, а структуры и алгоритмы были бы в ущерб модулярности).
Конечно, очень часто нам не нужно думать об эффективных алгоритмах, когда всю тяжелую работу выполняют база данных, веб-сервер и операционная система. А твой код лишь рисует веб-странички или кнопочки в приложении на айфон.
Но именно в этих сложных системах (ОС, базы данных, веб-сервер, компиляторы, др) и используются все те основы, что мы с вами читаем с книжек типа CLRS.
Полный ответ об алгоритмах из книжек был дан на stackexchange и потом был репостнут в блогах и позже на HN. Сегодня я решил перевести ответ об ОС Линукс со своими комментариями (отсебятина) и ссылками на ресурсы на русском языке.
Так давайте поговорим об ОС Линукс, оказывается там можно встретить все, что учит любой школьник до 9 класса (а может и раньше):
- Связанные списки, двусвязаные списки и lock-free версии
- B+ сбалансированное дерево, как мы помним они еще используются в файловой системе
- Двусвязаные списки отсортированные по приоритетам (их используют mutex локи)
- Красно-черные сбалансированные деревья используются очень много где
- Дерево интервалов (НЕ дерево отрезков как в e-maxx, а дерево интервалов, где в каждой вершине сбалансированного бинарного дерева лежит два числа: от и до)
- Radix tree (более знакомый нам как Бор)
- Куча с приоритетами используется в cgroups: ограничение ресурсов доступных процессу. Модная нынче контейнеризация (LXC использует cgroups, а модный Docker использует LXC), также не удивлюсь, если линуксовская версия runexe использует cgroups.
- Хэширование по Кнуту: раз и два
- Хэш-таблицы используются для inodes — структура хранящая мета-даныне о файлах на файловой системе
- Битовые массивы (прям как Си++шный bitarray)
- Бинарный поиск, бинарный поиск в B-дереве
- Поиск в глубину и ширину
- КМП и Бойер-Мур
- Сортировка слиянием иcпользуется для системы сборки мусора
Также советуется к прочтению оригинальный пост, там еще больше примеров с ссылками на статьи на английском языке.
И в добавку примеры использования динамического программирования: link
"...оказывается там можно встретить все, что учит любой школьник до 9 класса..."
Я надеюсь, это ирония:) Примеры интересные, спасибо!
это скорее восхищение нашими школьниками в сравнении с другими :)
А ведь кроме ядра есть ещё и "утилитки" всякие мелкие — хотя бы sort (у каждого ли получится с полпинка написать реализацию которая будет с аналогичной скоростью сортировать 20Гб файлы?) — а grep и пострашнее будет (если готовые регэкспы не спереть откуда-нибудь). Про gzip тоже думать страшно. Даже простенькие инструменты для текстовых файлов — например diff — и то, если вдуматься, могут изрядно озадачить своей реализацией.
А в бизнес-задачах "тупого ентерпрайза" да, другие ценности и другие устремления. :(
Я пытался написать свой дифф. Там очень интересно, если писать привычную нам динамику за квадрат, то в среднем работает дольше чем через жадность с оптимизациями. Написать очень быструю реализация я так и не смог, но попытался: https://github.com/slava/diff.js
Про регекспы тоже интересно! В Мире есть два типа регекспов: 1) регекспы, которые описывают какой-то Regular Language (отсюда и название) 2) расширенные регекспы, которые поддерживают фичи типа back-reference (\1 например) — они уже нифига не подходят под описание Regular languages.
Так вот, для 1) можно написать генератор DFA и за длину инпута проходить автомат. С 2) такая шняга не проканает, там нужно уже писать перебор с возратом (backtracking) с отсечениями (что делают perl и egrep). Я смог написать прототив 1) когда-то для фана: https://github.com/Slava/regex.js
А вот fgrep — это Ахо-Корасик :)
Я начал работать около месяца назад, и за неделю уже смирившись с тем, что "продакшн" и олимпиадное программирование не имеют ничего общего, спокойной себе кодил да учился уму разуму. Попытаюсь успокоить молодое поколение, чтобы не отрекались от деревьев и иже с ними :) Используется. Все используется. И всюду.
Во-первых, и самое главное, алгоритмы дают не только знание алгоритмов, но и, так сказать, "круто качают". И если в Украине, к примеру, это не всюду понимают, и интересуются в людях, прочитавших "Thinking in java" НАМНОГО больше, чем в людях, прочитавших того же Кормена, то "акулы" по типу Фейсбука, Майкрософта и т.д. на интервью даже не задали вопрос, на каком это я языке пишу. Только алгоритмы и логика. Потому, что умный человек может научится программировать, а обратное, увы, не всегда :)
Во-вторых, я за месяц "джуниорства" как-то умудрился уже применять во всю Binary search, HashMap, HashSet, TreeMap, TreeSet, боры, BucketSort, и прочее. И не просто ради любви к алгоритмам, оптимизация достигает хороших процентов.
Так что мой вам совет (если кого интересует и кто дочитал аж до сюда) : учите, учите алгоритмы, пишите CF, TC, и участвуйте во всех раундах. Потом, когда захотите на работу (обычную) выберите любое направление, и интенсивно почитайте недельки 3-4. Возьмут, гарантирую. А когда захотите на работу (крутую) ищите акул, и просто идите :) Алгоритмы у вас уже есть, опыт работы, коммуникабельность и английский вы получите на обычной работе. Можно сразу без нее (наверное).
Спасибо за внимание, удачи.
Я не буду начинать очередной холиварный тред про СП против Реальный Мир, но выражу свое скромное мнение.
Знания алгоритмов нужны, а точнее, важны ключевые концепты, которые позволили этим алгоритмам появиться. Когда мы решаем задачи в СП и выходит что-то нестандартное, решение строится из знакомых идей взятых с известных алгоритмов. (Хотя мне, как фиолетовому, можете не поверить).
Но в реальном мире низкоуровневые оптимизации — не самое главное. В постоении системы — важен дизайн системы, правильные абстракции, разделение модулей. Даже система имен в системы играет большую роль.
Алгоритмы — далеко не единственный технический скилл, который необходим. Как-то так.
Привет, не знаешь где можно подробнее узнать об алгоритме "Расстояние Дамерау — Левенштейна", было бы совсем отлично, если еще с реализацией на JavaScript, но в принципе любой язык общего назначения пойдет.
Link