tgoop.com/reinforced_sc/69
Last Update:
Алгоритмы
Пока все дружно отменяют алгосы на собесах (меня они тоже бесят кстати), я решил честно подбить список алгоритмов, которые мне пригодились в работе или пет-прожектах. Погнали.
— Обход деревьев по-всякому. Вообще каждая первая задача на фронтенде.
— Нахождение наибольшей общей подпоследовательности (динамическое программирование). Использовал несколько раз с целью поиска diff-а.
— Префиксное дерево один раз делал. Нужно было для поиска в приложении, где не было базы данных.
— Сортировка слиянием. Ваще топ. Пишется в три строчки, работает хорошо в связке с другими сортировками, быстро отрабатывающими на небольших данных. Использую её много и для разного. Например, для решения задачи "получить от пользователя excel-ку и обновить данные в БД согласно ей с попутными вычислениями". Вытягиваешь данные из базы, из excel-ки, сортируешь по какому-либо критерию, бежишь по обоим наборам и вычисляешь.
— Пару раз писал на коленке топологическую сортировку. Пытался оптимизировать работу MSBuild ещё до выхода ReSharper Builds/Rider.
— Считал расстояние Левенштейна на фронтенде для оптимизации выдачи автокомплита.
— Хэшмапы (в миру шарпистов — Dictionary). Ни разу не делал сам, но то и дело пользую для всякого. Да ой, их сейчас все используют и, как по мне, грешно не знать как работает самая популярная структура данных.
А ещё на отдельной любимой полочке у меня лежат графические алгоритмы. Мне кажется, там много всякого-интересного.
— Линейная, билинейная и бикубическая интерполяция. Это с натяжкой можно назвать алгоритмикой, конечно. Просто несложная математика. Используется во всякой служебной графике (например, красивое отображение heatmap-ов). А ещё на бикубической интерполяции рандома строятся шумы Перлина. Это не продакшон, это просто красиво.
— Дебайеризация. Можно её назвать алгоритмом? Ну, наверное с натяжкой, но было дело я писал дебайеризацию для 12-битной вебкамеры.
— Рейтрейсинг. Не, не поймите неправильно, я не впиливал трассировку лучей на продакшен. Но позадрачиваться с рейтрейсингом стоит, чтобы потом лучше соображать в графической 2D/3D математике. Ну там, знаете, векторы, матрицы поворота, проекции, параметрические кривые/поверхности второго порядка и иже с ними. Хотя, пожалуй, тут подойдёт просто поиграться с OpenGL.
— Всякие матричные фильтры. Использовал несколько раз для прикладного анализа изображений с OpenCV. Да, и таким я занимался было дело.
Какая же тут мораль? А морали тут, как мне кажется, две.
Во-первых эту всю байду я в голове не держу. Без гугла я смогу разве что линейную интерполяцию написать, и то с ошибками. Если вдруг случится ядерная война и отключится интернет — я знаю в каких книжках подсмотреть. Если и книжки сожгут — в пределах недели сам соображу все перечисленные алгоритмы в коде. Запоминать эту бесполезную по сути информацию я не вижу смысла.
Во-вторых, мой опыт считается ещё глубоким и широким. Для решения абсолютного большинства сколько-нибудь полезных задач весь этот багаж знаний не нужен. На худой конец можно взять либу. Да, я всё ещё считаю хорошим тоном соображать в двух словах как оно всё работает под капотом. Но необходимо ли это? Совершенно нет.
Есть другие, более важные вещи, которые необходимо понимать.
Такие дела
BY Novikov on Soapbox
Share with your friend now:
tgoop.com/reinforced_sc/69