Артём Мурадов — Senior Software Development Engineer в Amazon и автор курса «Алгоритмы: roadmap для работы и собеседований». Уже больше 14 лет он использует алгоритмы для решения рабочих задач и прохождения собеседований. С помощью алгоритмов он повышал производительность приложений, побеждал в спорах с коллегами и ускорял исследование ДНК. Даже попасть в Amazon ему помогло знание алгоритмов.
Мы пообщались с Артёмом, чтобы узнать о его опыте. Он подробно рассказал, как изучал алгоритмы и как они помогали ему в работе.
Ускорил приложение в 600 раз с помощью алгоритма
2012 год. Я прихожу на работу и узнаю, что система, которую мы писали, медленно запускается. Настолько медленно, что мы даже не можем выпустить релиз.
Ситуацию спас один человек. Он увидел, что в задаче поиска, которая запускается на старте приложения, используется квадратичный алгоритм. Алгоритм работал хорошо на малом объёме данных. Но когда данных стало много, его скорость быстро деградировала. Это стало причиной блокера для релиза.
Тогда меня это поразило: человек просто поменял квадратичный алгоритм на линейный, и всё снова стало прекрасно.
Прошло 5 лет, я оказался в другой компании, где отвечал за приложение, которое сравнивало объекты. Представьте, у вас есть объект №1 с полями, и объект №2 с полями. Вам нужно понять, чем они отличаются. Вы открываете форму, и она показывает разницу между объектами: какие поля добавились или удалились.
В какой-то момент приложение начало долго открываться, что было критично. Невозможно работать, если у тебя обычная форма сравнения объектов открывается 30 минут.
Припоминая историю спасённого релиза, я уже догадывался, в чём может быть дело, и начал смотреть код. Причина оказалась та же — неэффективный алгоритм. Когда приложение создавалось, полей было около 200, алгоритм справлялся. Прошло 10 лет, и количество полей возросло до десятков тысяч. Такие объёмы алгоритму были уже не под силу: он начал работать очень медленно.
Я произвёл ту же замену, что и мой коллега когда-то, — заменил квадратичный алгоритм на линейный. На всё это ушёл один день, и время открытия формы уменьшилось с 30 минут до 3 секунд. Скорость выросла в 600 раз.
За 2 дня сделал то, на что ушло 2 года
Я всегда читал много разных книг по алгоритмам. Особенно меня поразили «Жемчужины программирования» Джона Бентли. По большому счёту, это сборник историй и рассказов о том, как помогают алгоритмы. Одна из историй рассказывала о сортировке подсчётом. Обычно, если ты хочешь отсортировать какие-то вещи, ты предварительно сравниваешь их друг с другом. А особенность сортировки подсчётом в том, что тебе не нужно ничего сравнивать.
В то время я даже не мог представить, что существует такой алгоритм. Мозг взрывался от нового знания, и я пошёл решать задачи. Какие-то давались легко, какие-то сложнее. Наконец, на одной платформе попалась такая, которую никак не получалось решить. Точнее моё решение работало, но было слишком медленным, что, конечно, меня не устраивало.
Шли месяцы, я всё пытался «одолеть» задачу, но она упорно не поддавалась. Теоретически, можно было бы подсмотреть решение в интернете, но я был слишком горд для этого.
В 2014 года я попал на онлайн-курс от Западного университета, где рассказывали про определённую структуру данных и её использование. К тому моменту про структуру данных я уже знал, но никогда не применял её на практике.
Открылась простая истина: недостаточно просто знать алгоритм, нужно понимать, когда его применить.
На курсе рассказали, что «структура данных» — это префиксное дерево, и показали, как с ним работать. Я начал решать примеры, и тут в голове щёлкнуло: «Это ведь та самая задача!». Я потратил ещё 2 дня и наконец-то справился с ней. Проблема была в теоретический базе — как только я её получил, сразу смог найти решение.
Естественно, я бы никому не советовал 2 года решать одну задачу. В то время я был немножко упоротый по алгоритмам — это и помогло не бросить всё на полпути. Но чтобы не тратить столько времени на поиск правильного решения, нужны проверенные источники для обучения.
Пранк вышел из-под контроля: решил нерешаемую задачу
В 2016 году меня пригласили работать в Польшу. Хорошо помню первую задачу в новой компании. Она касалась блоттера.
Блоттер — грид по типу Excel с двумя особенностями. Первая особенность в том, что он держит в памяти только те данные, которые показывает. Предположим, есть таблица с миллионом элементов, из которых видны только 100. Эта сотня — то, что есть прямо сейчас. Всех остальных элементов нет. Когда крутишь блоттер, он начинает запрашивать новые пачки данных, чтобы отображать их.
Вторая особенность — все данные изменяются в реальном времени. Это значит, что в любой момент какие-то строчки могут пропасть, или, наоборот, добавиться.
Мне нужно было сделать так, чтобы, когда пользователь выделял какую-то область в блоттере, а после этого проматывал вверх или вниз, выделенная область сохранялась в памяти. Проблема заключалась в том, что строки постоянно добавлялись, удалялись и обновлялись. Всё это было очень динамично и, разумеется, не сохранялось. Если что-то промотал, всё тут же исчезало.
Я понял, что нужен хитрый алгоритм, который бы находил строчки, которые были выделены, и показывал их, даже когда данные блоттера уже изменились. Провозился с задачей примерно неделю и все-таки решил её.
Но самое интересно дальше — начинаю рассказывать обо всём коллегам, а они только удивляются. Я, естественно, ничего не понимаю, спрашиваю, в чём дело. Тут выясняется, что надо мной просто пошутили. Все в команде уже пытались решить эту задачу, но ни у кого не получилось. И когда пришёл новичок, они просто хотели посмотреть, что он будет делать, столкнувшись с нерешаемой задачей. Правда, шутка вышла из-под контроля. И даже, когда спустя 4 года я уходил из компании, коллеги всё ещё вспоминали эту историю.
Ускорил исследование ДНК в 4000 раз
У меня около 900 ответов на Stack Overflow, из которых больше сотни по алгоритмам. В потоке вопросов я хорошо запомнил один, связанный с ДНК.
ДНК — молекула, которая обеспечивает хранение и передачу информации. Она состоит из нуклеотидов. Каждый нуклеотид содержит сахарную и фосфатную группу, а также азотистые основания. Эти азотистые основания делятся на 4 типа: аденин, тимин, гуанин и цитозин.
Эти же азотистые основания — 4 буквы, отвечающие за определённые позиции в ДНК. А сама ДНК выглядит как последовательность букв, алфавит которых ограничен 4 значениями. Для исследования нужно было обрабатывать миллионы таких последовательностей. Делать это автору вопроса приходилось в полуручном режиме. На то было две причины.
Первая — рабочее приложение принимало только 10 тысяч последовательностей, каждая не длиннее 10 символов. Вторая — это было лицензированное ПО, которое стояло на старом компьютере. Из-за ограничения лицензии его нельзя было перенести не более мощное устройство.
У меня родилась идея, как решить проблему. Если взять две последовательности, которые одинаковы на всех позициях, кроме одной, их можно смёржить в одну. Нужен только специальный символ, который скажет, что это не одна последовательность, а две.
Объясню на примере. У нас есть два имени: «Артем» и «Артём». Пускай, «е» и «ё» — это какая-нибудь спецбуква, например «у». Мы берём «Артём» и «Артем» и мёржим в «Артум». Теперь все, кто будет смотреть на слово «Артум», будут знать, что это два имени, но обрабатывать его смогут как одно.
Благодаря такому варианту сжатия можно было сократить количество последовательностей ДНК до нужного уровня. Допустим, на входе 600 элементов, а на выходе 17. На входе 3 миллиона, а на выходе 150 тысяч.
Я закончил писать алгоритм под свою идею, и автор вопроса опробовал его в действии. Он установил приложение с моим алгоритмом на новый компьютер и запустил обработку 4 миллионов последовательностей по 11 символов. Это было в 450 раз больше, чем могла посчитать его старая программа. Операция заняла 7 секунд. Производительность выросла в 4000 раз.
Я не делал никаких сложных распараллеленных вычислений. Только реализовал одну идею в простом алгоритме, который написал за пару дней. Всё.
История попадания в Amazon
Скажу сразу, Amazon — не единственная крупная компания, куда я пытался устроиться. Я ходил на собеседование в Microsoft, дважды участвовал в отборе в Google. Каждый раз я добирался до финального этапа, но выбор делали в пользу другого кандидата.
Признаюсь, три неудачных собеседования дают повод усомниться в реальности попадания в компанию уровня FAANG. Хотя я и готовился ко встрече с представителем Amazon, шёл туда больше по фану: на других посмотреть, себя показать и шутеечки пошутить.
Прихожу, меня спрашивают: «Ну, что, готов?».
Отвечаю: «Да, погнали. Давай мне алгоритмы, сейчас всё разберём!».
Возможно, дело было в том, что я два раза готовился к собеседованию в Google, два раза участвовал в чемпионате внутри моей компании и вообще был адово нагретый по алгоритмам. Но когда мне задавали задачу, я даже не дослушивал её до конца. Говорил: «Всё, стоп. Я знаю, как решать». И начинал решать. Для некоторых задач даже код не писал — просто объяснял, что нужно сделать.
Когда уходил с собеседования, был в состоянии типа: «А что это было вообще? А где настоящее собеседование? Почему меня не разносят задачами?».
Вскоре со мной связались и сказали, что я прошёл, да ещё и назвали senior. Я тогда удивился, но сейчас понимаю, что это закономерно. Каждое новое собеседование добавляло мне опыта и развивало.
Я шёл трудным путём: сам составлял себе программу обучения, сам всё учил, сам выбирал задачи и решал их без помощи извне. В Microsoft я подался в 2012 году, а работать в Amazon начал только в 2020 году. За 8 лет у меня было 4 собеседования в FAANG, 3 из которых прошли неуспешно.
Когда я рассказал на прошлой работе, что прошёл собеседование в Amazon, меня сразу стали спрашивать, что там и как. И спрашивали так часто, что пришлось сделать шпаргалку, которую я просто копипастил и отправлял всем интересующимся. Но это было не напрасно — те, кто воспользовался моими рекомендациями, теперь работают там, где мечтали.
Пару слов об экспресс-курсе «Алгоритмы: roadmap для работы и собеседований»
Всех, кто хочет погрузиться в тему алгоритмов, приглашаем на экспресс-курс «Алгоритмы: roadmap для работы и собеседований». Вы узнаете, как алгоритмы помогают в работе и на собеседованиях и получите проверенные ресурсы для их изучения.
Вам не придётся читать десятки ненужных книг — вы сразу начнете с правильной базы и сможете решать задачи, которые не под силу другим программистам.
Дисклеймер: всё, что Артем рассказывает на курсе — его личное мнение, которое никак не связано с позицией компании Amazon
Комментарии (25)
svr_91
16.03.2022 17:04Первая — рабочее приложение принимало только 10 тысяч последовательностей, каждая не длиннее 10 символов
А это не было каким-нибудь ограничением лицензии?
tym32167
16.03.2022 17:28Я не уточнял, если честно. Я помню, что ограничение лицензии не позволяло переносить ПО на другую машину. Предположу, что ограничили из за скорости работы, чтобы пользователь ждал ответа разумные минуты, а не часы.
svr_91
16.03.2022 17:44И вы таким образом нарушили лицензионное соглашение? :)
tym32167
16.03.2022 17:50Я не мог ничего нарушить, ведь я создал свое ПО со своим алгоритмом и приложение, которым пользовались до этого, даже в глаза не видел. Да и посчитайте сами, старое приложение работало минуту, а мое обрабатывало в 450 раз больше данных за 7 секунд - если бы старое и могло столько данных обработать, то по времени это было бы явно сильно долго.
mixsture
16.03.2022 17:21+6Все в алгоритмах хорошо, за исключением того, что они нужны в 1% случаев. А в остальных 99% не нужны, а иногда и вредны (потому что увеличивают стоимость поддержки кода, а вот профит от них может и не приносить пользу для бизнеса).
Соответственно, современная мода требовать алгоритмы на собеседовании приводит к тому, что прокачивается эффективность этого 1% работы. Тогда как вместо этого могла прокачиваться эффективность остальных 99%. Т.е. бизнес просит сотрудников прокачать малонужные навыки, что, естественно, выдаст снижение эффективности бизнеса.
P.S. я не отношу к алгоритмам обычные ошибки в производительности из разряда «не надо делать запрос к базе в цикле. если есть пакет данных, то и обработать его хорошо бы пакетно».tym32167
16.03.2022 17:40+5Смотря что подразумевать под "алгоритмами". Знание алгоритмов и структур данных помогает не только писать какие то хитрые алгоритмы. Это также требуется при, например, выборе правильной структуры данных для работы. Или при разделении между алгоритмами и доменной логикой. Чтобы просто пройтись нужным способом по дереву, надо какое то минимальное знание алгоритмов. Да даже если вы проектируете систему (проектируете, не кодите), можно использовать анализ алгоритмов, чтобы примерно представлять возможности масштабирования системы.
Потому ваши 1% ну сильно приуменьшены. По моему опыту процент будет в десятки раз больше. Наверное вы имеете ввиду случаи, когда надо реально какой то свой алгоритм изобретать - это да, это редко.
Deosis
17.03.2022 07:06+1По закону Парето алгоритмы полезны в 20% случаях.
tremp
18.03.2022 23:04И вы все правы ) - все зависит от того, в какой области работаете. Если вы мобильный разработчик в финтехе или разрабатываете какое-нибудь учётное по по типу 1с, то это 1%. А если вы бэкендщик, которому интересны алгоритмы, и выбираете себе соответствующие места работы, то там процент будет сильно выше.
tym32167
18.03.2022 23:48Есть много факторов. Если ты пишешь только круды в базу, то знать алгоритмы возможно и не придется. Но это очень простая работа - писать только круды и больше ни о чем не думать. Ну и долго так не каждый сможет работать.
По поводу финтеха - примеры с блоттером и формами как раз были для финтеха, я тогда работал разрабом настольных приложений. Там знания алгоритмов и структур данных были нужны может не каждый день, но весьма регулярно.
Бекендщик бекендщику тоже рознь. Можно и беком просто джейсоны перекладывать, но у меня есть примеры, когда алгоритмы понадобились и при реализации фич на беке, так и при проектировании бека. Так что тут не все так однозначно. Как тут уже писали, даже при проектировании микросервисов и их композиции требуется знание алгоритмов.
По сути - это как ООП. Кто то может сказать, что он просто лепит дтошки и рад этому - в таком случае не надо обладать хоть какими то знаниями ОПП для такой работы. Но если ты хочешь быть реально профессионалом, то тебе надо и ООП знать, и про паттерны, и подходы всякие, и про солиды/граспы и прочее.
Вот в этом и мысль. Жить как программист без знания алгоритмов ты можешь и даже что то делать полезное при этом. Но ты будешь всегда ограничен в своих возможностях, если ты не открывешь области, непосредственно связанные с выполнением своих обязанностей. Если ты пишешь код и не знаешь, быстрый он или медленный, то есть не можешь просто проанализировать эффективность своего кода или обосновать выбор своих структур данных и даже не знаешь, что это проблема - вот это самое печальное.
Я же не говорю про изобретение каких то своих алгоритмов, я говорю про самые основы, просто уметь и применять анализ того кода, что пишешь. Просто уметь обосновать выбор той или иной структуры данных для своей задачи. И применять это постоянно. Даже это повысит качество твоего кода.
Лично для меня освоение этой темы было как вот ощущение, что до этого я ползал по земле на корачках, а потом встал в полный рост и ходить лушче стал, и видеть дальше стал. Я не знаю, как это более доходчиво описать.
questor
16.03.2022 23:04+3Я очень часто слышу такое мнение и я пожалуй хотел бы высказать свои мысли на эту тему.
Во-первых, я совершенно согласен с тем, что есть ряд простых приложений, в которых алгоритмы нужны именно на уровне "достаточно понимать что алгоритм квадратичный" и уметь переводить их хотя бы в N log N. Ну допустим, вы решили написать калькулятор калорий на андроид - и это не рокет сайенс, вам не нужно знать красно-чёрные деревья для этого. И наверное есть много разработчиков, которые работают фрилансером, либо на себя в условиях мелкосерийного и кустарного производства - и если вы работаете в этом сегменте и вам нравится - то мы просто разные люди и каждому своё.
Просто лично я работал в крупных конторах с числом программистов более тысячи (пожалуйста, не воспринимайте как хвастовство, просто на мелких проектах мне скучно) и в этом сегменте всё несколько иначе: там приходится строить приложения может быть и не особо сложные, в том плане что это просто пачка мелких микросервисов, но из-за огромного числа этих маленьких микросервисов систему простой назвать язык не поворачивается. И в таких проектах, с командой по 50 человек и выше, вроде как на первый взгляд тоже не особо нужны алгоритмы... И я бы снова согласился что алгоритмы не нужны... Но есть одно "но": там сильно рулит сисдиз, вы должны понимать как строить сложные архитектуры из мелких кубиков, причём в этих кубиках всё настолько пропитано алгоритмами, что хорошо бы, чтобы алгоритмы уже спинным мозгом понимались, а не приходилось долго и мучительно вдумываться. Например, как работают разные виды кеширования. Или как устроены кластерные индексы в реляционных таблицах. А откроешь Клеппмана по высоконагруженным системам - там через страницу такое.
И поскольку в современном айти происходит сильная монополизация крупными игроками (скупают стартапы с мелкими приложениями но с высоким потенциалом - и модифицируют эти приложения под хайлоад), то всё больше востребованы именно программисты с прокачанным навыком алгоритмистики, чтобы на этом фундаменте можно было бы надстраивать следующий этаж - сисдиз.
Поэтому знания алгоритмов и структур данных я воспринимаю именно как знание азбуки или таблицы умножения, как один из важных кирпичиков для более сложного знания. А потому - маст хэв.
Я не особо часто слышу подобный аргумент, поэтому и захотел высказаться, если кому есть что дополнить или поопонировать - давайте обсудим. Есть ещё много других аргументов, я не буду их подробно здесь повторять, скажем, есть такая точка зрения что крупные компании могут устанавливать любые правила игры - сегодня спрашивают логические задачи, завтра про алгоритмы и нужно просто принять это если хочешь в крупную компанию - просто играй по этим правилам и у тебя будет результат после гроккинга очередного HR-фильтра.
wataru
17.03.2022 14:22+2Вот только алгоритмы надо знать, потому что иначе этот 1% становится нерешаемым. Программист просто даже не подумает, что вот тут можно применить алгоритм.
Или считается, что задача нерешаемая и приходится отказываться от какой-то фичи, или пишется тупое наивное решение, которое дико тормозит.Тогда как вместо этого могла прокачиваться эффективность остальных 99%.
Чем знание алгоритмов может помешать программисту клепать формочки или перекладывать json-ы (из чего в основном и состоят остальные 99%) работы, я не представляю.
mixsture
16.03.2022 20:35Знание алгоритмов и структур данных помогает не только писать какие то хитрые алгоритмы. Это также требуется при, например, выборе правильной структуры данных для работы. Или при разделении между алгоритмами и доменной логикой. Чтобы просто пройтись нужным способом по дереву, надо какое то минимальное знание алгоритмов.
При столь широкой трактовке под алгоритмы попадает почти все. Термин вообще ужасно «резиновый». Я под ними не подразумеваю базовые вещи, вроде обычного обхода дерева. Я к «алгоритмам» отношу очень специфичные знания вроде:
различия в деревьях (балансировка, красно-черное и т.д.)
различия в методах сортировки (вот эта вся тема про «давайте хеши разложим в корзины, а внутри каждой дерево).
(извиняюсь, веткой промахнулся. это ответ на habr.com/ru/company/southbridge/blog/655927/#comment_24172521 конечно же)tym32167
16.03.2022 21:00+2Я думаю, знание о сбалансированных деревьях поиска тоже полезны. Не обязательно все это уметь кодить самому, но хотя бы знать разницу между сортированным ассоциативным массивом (aka TreeSet\TreeMap) и простым несортированным (например, хешсеты\хешмапы) уже помогают выбрать что больше подходит под задачу.
Про устройство хешсета\хешмапы я вообще молчу, это же основы. Как, например, можно понять зачем перегружать equals и hashcode - если не знаешь зачем этот hashcode - я таких проблем на stack overflow видел не один десяток.
Потому вы правильно говорите, алгоритм - это термин широкий. И без знания основ алгоритмов и структур данных я не представляю, как можно разбираться хотя бы в тех структурах данных, которые сам же используешь в своем же коде.
Да и базовые вещи для многих уже проблема, по моему опыту, чуть меньше трети программистов просто не ориентируются даже в анализе алгоритмов. То есть пишут код и не понимают, быстрый этот код или медленный и каковы последствия роста входных данных. Понимаете, в чем проблема? Одно дело, когда программист пишет медленный код там, где это оправдано. Но другое дело, если программист пишет неэффективный код и даже не знает об этом.
Вот про это и есть курс. Там нет хитрых алгоритмов балансировки деревьев, но я поясняю, что это за зверь такой - двоичное дерево поиска и зачем его балансировать. Или например я покажываю самую простую реализацию хештаблицы и рассказываю, как качество хеш функции влияет на производительность и вообще корректность работы структуры данных. То есть примеры и теория максимально приближены к практике, но не перегружены деталями. Я не стал, например, рассказывать про Кнутта-Морриса-Пратта или Белмана-Форда (а вы как часто это используете?), но рассказал самые основы теории графов и самые популярные обходы (bfs\dfs) с конкретно практическим примером, который встречался мне именно на работе.
К тому же, как вы пишете, бизнес требует навыков в алгоритмах - но бизнес не требует чего то сверхсложного. У меня целый модуль в курсе про собеседования, что просит бизнес и почему он это просит (с моей точки зрения).
Вот такой получился курс, там нет никакого rocket science, но есть конкретные примеры из конкретно моей практики и теория привязана именно к ним.
mynameco
16.03.2022 21:45+2С одной стороны кричат - преждевременная оптимизация это зло!
С другой - какие не оптимизированные алгоритмы вы используете!
tym32167
16.03.2022 21:51Все верно, в программировнии должны быть компромиссы. То же самое про что угодно можно сказать: "с одной стороны - учите солиды\паттерны, с другой - hello, world: enterprise edition".
wataru
17.03.2022 14:26"Преждевременная оптимизация" — эта цитата была скорее про микрооптимизации. Типа использовать битовые трюки везде где можно, хранить несколько переменных в одном int-е для экономии памяти и всякая другая фигня. Выбор правильного алгоритма и структур данных должен происходить еще на этапе проектирования. Оно не может быть преждевременным.
Shadasviar
17.03.2022 06:34+5Из моего опыта, 90% проблем с производительностью решаются применением подходящих структур данных, которые есть в стандартной библиотеке, типа использования хэш-таблиц вместо линейного поиска, или использование списков вместо массивов, если реаллокация объектов при расширении массива дорогая.
Keeper1
Мне кажется, "квадратичные" алгоритмы -- это меньшая из ваших проблем.
JustDont
Это классика — крайне мало людей думает над производительностью (из-за чего регулярно происходят ляпы в самых неожиданных местах), но при этом еще меньше людей думает над пределами масштабирования тех или иных систем. Главным образом UI, где пределы проявляются очень быстро.
Это я говорю как человек, которому неоднократно предлагали зафигачить в UI табличку на миллион+ строк, и возражения "но никто никогда в жизни не прочитает миллион строк" поначалу даже слышать не хотели.
tym32167
Большие формы - это было частью бизнес процессов, типичная вещь в той доменной области, где я тогда работал.
С точки зрения программирования, скорость работы с такими формами решалась виртуализацией. Но это не отменяет модели с кучей полей. Кнонечно, это не означает 10к+ полей в DTO, так как у нас были составные поля (например, в гриде каждая ячейка считалась отдельным полем, значит грид 10х10 = 100 полей).
Конечно, это не есть хорошо и с точки зрения UI/UX, с этим борятся другими методами, не связанными с алгоритмами.
TiesP
У него нет проблем… он в amazon работает
Keeper1
Как будто что-то хорошее.