Страницы

Поиск по вопросам

среда, 27 ноября 2019 г.

Алгоритмическая “база” хорошего программиста. Вопрос по саморазвитию. [закрыт]

#алгоритм


Какие Алгоритмы Стоит Изучать?
Вот, чем  я руководствовался, задавая этот вопрос:
Почти любой работодатель хочет увидеть хорошую алгоритмическую "базу". Так же эта
"база" нужна и на практике. Но, какой должна быть эта "база"? Какие алгоритмы изучать?
Да, можно набросится на бесконечное множество всех алгоритмов и изучать их. Но их
слишком много,что бы реализовывать их программно. Поэтому, на реализацию забивать приходится. 
Мне этот путь не нравится. Думаю не только мне. Попытался найти в интернете подобные
списки, но нашел лишь советы людей - "Кто знает, что вам пригодится?", "мне хватает
знания сортировки пузырьком" и так далее. 
Читать разнообразные книжки, такие, как Кнута.. Там опять же много алгоритмов. Пробежаться
и забыть не хочется- хочется, что бы знания остались. А осваивать все-во первых долго,
во вторых многие из этих алгоритмов представляют лишь теоретический интерес и на практике
не применяются.    


Ответы

Ответ 1



Полный список, конечно, составить невозможно, поэтому пробегусь по тому, что мне кажется важным. Сложность алгоритмов. Вы должны знать O-нотацию и уметь сходу оценивать O-сложность алгоритма хотя бы для простых случаев. Структуры данных! Не только простые структуры, типа массива, но и сложные: вы должны представлять себе, что происходит при добавлении элемента в красно-чёрное дерево (std::map из C++), и понимать, почему добавление в него быстрое. Сортировки. Простые (надо знать и понимать недостатки и достоинства пузырьковой сортировки) и сложные (понимать хотя бы quicksort, и уметь на пальцах объяснить его идею). Алгоритмы работы с деревьями: например, различные их обходы. Поиск в графе: в ширину и в глубину, алгоритм Дейкстры и A*. Бинарный поиск в отсортированном массиве, конечно. Математика! Матричные алгоритмы (детерминант, решение системы линейных уравнений не через детерминанты), преобразование между системами счисления (включая смешанные). Работа с рекуррентными последовательностями: вычисление степени и n-ого числа Фибоначчи за логарифмическое время. Мне ещё пригодились когда-то нахождение выпуклой оболочки и векторные трюки (типа расстояния между скрещивающимися прямыми через векторное произведение), но они нужны всё-таки реже. Базы данных важны. Вы должны представлять себе, как выполняются JOIN'ы и какая «стоимость» материализации того или иного VIEW. Вы должны понимать, как строятся индексы, сколько они «стоят», и как они помогают. (В терминах O-нотации.) Анализ игр может пригодится. Например, построение множества выигрышных позиций «с хвоста».

Ответ 2



Большинство работодателей которых интересует "алгоритмическая база" на самом деле были латентными извращенцами, которые хотели показать, давая вам кривую олимпиадную задачу, как необозримо круты они, и как малы и латексны все вокруг)) С вопросами оплаты и карьерного роста потом тоже были проблемы. На самом деле львиную долю народа интересует в нанимаемых программистах три вещи: умение быстро доучиваться и творчески решать задачи; умение писать качественный код - то есть не содержащий багов, не содержащий ошибок в безопасности, не содержащих глупых ошибок, которые снижают быстродействие; умение приспосабливать к работе в команде. Алгоритмы - хорошо. Но общее понимание, что такое сортировка, что такое индексирование, как лучше хранить данные, чтоб это было оптимально по затратам и доступности, как лучше построить цикл (какие действия нужны внутри, а какие можно вынести вне), какие могут быть ошибки в данном коде, и как их нужно экранировать и обработать. Какие данные могут подсунуть пользователи на вход по дури, а какие по злому умыслу - и как максимально обезопасить код от ошибок внешних данных. Вот это с точки зрения хорошего программиста важнее. Алгоритмы как таковые вам понадобятся в трех случаях: вы трудоустраиваетесь в иностранную контору, где анализируется квалификация вцелом - но тесты обычно построены так, чтоб понимать, понимаете ли вы в общем о чем это - ну и дочитали ли вы Кнута, Седжвика, Вирта, Страуструпа до конца); вы трудоустраиваетесь в контору, которая пишет низкоуровневый софт, вот тут как раз вы можете нарваться на то, что многие из алгоритмов, которые "представляют лишь теоретический интерес и на практике не применяются", ещё живи и здравствуют; вы устраиваетесь в контору, которая пишет софт для моделирования, графики и 3Д движки)) Кстати, как утверждают знакомые, работающие в последней категории знание физики вцелом, предметной области, а также алгебры, геометрии, матанализа и умение щелкать пятиэтажые уравнения (причем правильно) - им нужно гораздо чаще, чем Кнут. Диверсификация знаний и навыков, как по мне, так же полезна, как и доходов ;)

Ответ 3



По совету @VladD преобразовал комментарий к его ответу тоже в ответ. Я бы добавил: Понимание компиляции-интерпретации-линковки (тут же (кроме линковки) сидят регулярные выражения и тоже надо бы понимать как их алгоритмы устроены). Представление о работе с дисками (теперь еще и с флэшем). В этом плане полезно знать как работает внешняя сортировка. Еще на эту же тему - когда индексный доступ к данным в базе полезен, а когда наоборот, только замедляет выполнение запроса. Ну и как LAN (TCP/UDP/ICMP и т.п.) работает. Тут в первую очередь надо познакомится с сокетами. Еще одна модная теперь тема это потоки (threads) и соответственно синхронизация доступа к памяти. Тут же вспомним о процессах и алгоритмах межпроцессного взаимодействия. К алгоритмам напрямую не относится, но желательны определенные познания в области современных архитектур компьютеров. Прежде всего конвейеризация исполнения команд, предвыборка команд и данных, внеочередное исполнение, кэши процессора и проблема когерентности кэшей в SMP и NUMA архитектурах, порядок величин времени задержек при обращении к кэшу и RAM, а также организация виртуальной памяти (разделение функций между аппаратурой (MMU, TLB) и ОС), принципы обработки прерываний (тоже, что делает железо, а что ОС). (если еще что-то хорошее (или о чем спрашивали меня или спрашивал я) вспомню, то буду добавлять сюда)

Комментариев нет:

Отправить комментарий