Хабр Курсы для бэкендеров
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 79
Спасибо, об этом стоило напомнить
И почему через пару лет, когда ИИ будет писать весь код за меня, это понимание станет единственным, что меня спасёт.
ChatGPT, о котором стоило напомнить, передаёт привет, и даже спасибо не просит — в карман, говорит, не положишь — подписку давай: «…
Bottom-up решение (in-place). Идём снизу вверх, накапливая максимальные суммы прямо в массиве. Псевдокод:
def max_path_sum(triangle):
# triangle: list of lists, triangle[i] длины i+1
n = len(triangle)
# начинаем со второй снизу строки
for i in range(n - 2, -1, -1):
for j in range(i + 1):
triangle[i][j] += max(triangle[i + 1][j],
triangle[i + 1][j + 1])
return triangle[0][0]Смысл:
на шаге
iстрокаi+1уже содержит максимальные суммы от каждой своей позиции до низа;мы обновляем
triangle[i][j]до «макс. сумма от (i,j) до низа»;в конце
triangle[0][0]— ответ.
Оценка сложности
Для треугольника из n строк:
количество элементов:
1 + 2 + … + n = n(n+1)/2, дляn=100→ 5050;операций порядка
O(n²)— здесь ~5·10³ действий, смешно мало.
По времени это оптимально (надо хотя бы один раз прочитать все элементы). По памяти — можно:
либо модифицировать треугольник «на месте» (как выше);
либо держать отдельный массив для «текущей строки» снизу (тогда
O(n)памяти).
…».
— После чего показала вариант с отдельным массивом, закончив так: «… Итого: для 100 строк (и сильно больше) оптимальное решение — динамическое программирование снизу вверх с квадратной сложностью O(n²) и O(1) или O(n) памяти. Полный перебор с ветвлением 2^(n−1) бессмысленен уже при n≈50. …»
Да, даже Deepseek предложил версию решения с "низу-вверх"
Нейросети умеют все, если ты не ощущаешь сложности, то ты не сможешь сказать нейросети сделать по другому, когда она предложит линейный вариант
Если ты не чувствуешь, как ты ей скажешь, и как поймешь что решение ок?)
Так это валидация уже (а не написание), и ключевое тут собственное знание и критическое мышление — как и ресурсы на таковые, потому что они таки вполне ограничены, а не какое-то абстрактное «чувствование» вообще-то. Инженерное мышление — это на 99 % использование готовых шаблонов, нюанс лишь в их уместности. Творчества в этих процентах, грубо говоря, лишь в масштабах выбора как и какие кубики складывать. И, кстати, проблема валидации была и задолго до того, как модели код писать научились.
Но суть моего комментария не в этом даже. Он лишь о том, что даже под конец 2025 так называемый AI вполне себе сходу решает эту задачу, и даже способен указать на критерии оценки её эффективности. И «паттерны» эти модели видят уже получше большинства из нас. Так что заявления громкие, но в основном вхолостую.
сходу решает
Это хрестоматийная задача, миллион раз обмусоленная и как пример ДП, и как "задача для собесов". Странно было бы, если бы гпт про неё не знал
Это хрестоматийная задача
А то. Но суть-то всё же в том, что нейронки по мере роста своих масштабов способны «зреть в корень» всё эффективнее, так что задача может быть, условно говоря, переодета, но тем не менее, распознана и решена эффективно.
есть прикол и с этой задачей и с тем как её решает нейронка
Подавляющее число алгоритмов типа этого... уже решены. Гораздо более умными, чем я по крайней мере, людьми. Некоторые решены всякими супер хитрыми приколами, которые и не к программированию относятся первым делом, а к математике и всяким её заковыристым подразделам.
Именно по этому нейронки умеют их решать, а точнее находить уже существующее решение и применять его.
"Но они же не смогут решить принципиально новый агоритм", воскликнешь ты, на что я сразу же вспомню мем из "Я Робот"
ой не, не этот
"А ты сможешь?"
и ещё более интересный "а тебе надо?"
Допустим у нас есть какой-то супер-пупер бигтех продукт, который будет решать сверхсложные задачи за сверхкороткое время.
Сколько разработчиков будет работать над продуктом? А сколько из них будет писать этот алгоритм?
В 99.99% случаев, если ты натыкаешься в проде на момент где нужно использовать алгоритм, то первым делом ты должен посмотреть уже готовые решения этого алгоритма, выстраданные тысячами продуктов и миллионами разработчиков и взять лучшее из них. Ты же не пишешь свою реализацию ECDSA или SHA когда тебе их нужно использовать, ты берешь уже готовое решение так как в нем годами происходит оптимизация, чистка уязвимостей и прочие прелести.
И только в тех единицах случаев, когда ты упираешься в неведомое доселе чудо ты начинаешь разрабатывать свой алгоритм.
«А ты — хотя бы год на энергии в 2-х граммах плутония?»
ну не скажите, 2х граммов плутония ЛЮБОМУ разработчику-человеку хватит ДО КОНЦА ЖИЗНИ!!!!
...в первую очередь потому, что без нескольких тонн свинца этот конец наступит достаточно скоро!
без нескольких тонн свинца
Из той же википедии: «… Плутоний-238 используют в радиоизотопных источниках энергии (например, в РИТЭГах)[6]. Ранее (до появления литиевых батарей[8]) использовались в кардиостимуляторах[9][10]. …»
Тунца, а не свинца…
Мне хватит ~ куб воды;)
«Видите ли, Жора...» ©, в случае с плутонием (и прочими радиоактивными источниками) есть нюанс несколько нюансов — на 2 грамма путония нужно много килограммов радиационной защиты (которая, да, роботам — в первую очередь их «мозгам», хотя и не только: радиационное охрупчивание конструкционных материалов — это не выдумки — тоже нужна).
Не говоря уж об огромной куче агрегатов, обеспечивающих превращение радиации в электричество (а «простые» РИТЭГи в лучшем случае имеют КПД где‑то в районе 5%).
Ну если ужас с какой серьёзностью в ответ на мемасики wesha'ть, то сам по себе плутоний — источник альфа-излучения, которое экранируется без всяких «килограммов»: «… Плутоний-238 является практически чистым альфа-излучателем …», а вот современный реактор не нём — это уже другое дело, но «видите ли, Жора» начало этого комментария достаточно чётко?
Да, но мне вот как-то хотелось перебрать весь кэш в Firefox (не спрашивайте зачем, я просто люблю пострадать фигней), так там gpt не смог написать мне решение для чтения файлов по строкам не держа их полностью в оперативке (надо было отслеживать наличие определённых слов и отдавать мне текст между ними, а они могли оказаться половиной на 1 строке, половиной на другой).
Вроде не сложная задача, но блин, самому пришлось писать.
Если ты не чувствуешь, как ты ей скажешь, и как поймешь что решение ок?)
"Проверь свое решение, оно точно ок?"
Вообще это наивная попытка конечно, потому что в итоге легко получить n вариантов решения, которые могут быть неверными вообще, или далеки от оптимальных. Проблема валидации гораздо хитрее, и в общем виде, сродни проблеме останова — «анализатора не существует»… ©
Ставить под сомнение и перепроверять никогда не помешает. А вот что и как перепроверять зависит от того самого iq
Хм, а где там в литкоде зубрежка-то? Сборник задачек как-раз таких, вокруг которых построена статья. Не знаю как можно зубрить литкод, всегда когда садился за него, играл в него как в головоломки, иногда над сложными задачками по три дня зависая.
Мне тоже проект Эйлера понравился, занимался им, пока была возможность.
Можно поспорить?
Инженерия тут не причем - понятно дело, что если возникла необходимость решения математической нестандартной задачи (ибо стандартные типа sort и тд давно уже живут ф библиотеках и фреймворках), то необходимо посмотреть, а как ее лучше решить не "в лоб" (перебор - это, например, в лоб).
И вот тут нужно либо воспользоваться математиком, который подскажет куда копать, или как раз таки спросить у ЛЛМ - именно не код написать, а про алго и оптимальные пути его решения, потом самому переложить это в код.
И, имхо, правильный инженер должен поступит именно так.
Затем, в сухом остатке остается знание, что при возникновении такого типа задач нужно воспользоваться таким-то алгоритмом. Не нужно инженеру или программисту знать наизусть кучу вещей, которые могут не понадобиться вообще. Нужно лишь понимание где может возникать бутылочное горлышко - а для этого нужна лишь базовая логика, остальное можно будет уточнить или проверить.
Ну и, иногда, решения "в лоб" работают лучше, чем куча хитростей и сложный алго - это тоже надо понимать.
У меня к вам только один вопрос: зачем вы старались, писали статью руками в лоб, когда можно было бы просто сгенерировать ее с помощью нейросети за минуту? Пора бы уже совершить фундаментальный сдвиг парадигмы в своей ментальной модели, и перестать заниматься этой ерундой.
Ну так для этого нужно промпт писать
Понимаю, короткий промпт написать сложнее, чем большую статью, но это важный навык в современном мире, где промпт-инжениринг совершил тектонический сдвиг в сфере революционных перфомансов.
Бесспорно, да. С таким же успехом можно комментарии генерить)) Короче пришлите мне ссылку на вашу сгенерированную статью, любо посмотреть
Пожалуйста: https://habr.com/ru/articles/972630
Только никому не говорите, что она сгенерирована, а то растащат на цитаты.
Прошу лишь не выкладывать то, что вы сгенерили за минуту. Пользуйтесь сами, но не замусоривайте сайт.
Джун пишет вложенный цикл по массиву из миллиона элементов. Не чувствует боли. Процессор "съедает" всё за секунду.
Потом этот код попадает в продакшн с 10 000 пользователей одновременно. Серверы падают. Бизнес теряет деньги. CTO орёт на команду. И джун не понимает, что пошло не так. Ведь у него на ноуте все работало.
Ситуация высосана из пальца буквально: ревью, нагрузочные тесты, откаты на предыдущую версию после деплоя, и ничего этого нет в компании с 10к rps 😁
- Цель: найти путь с максимальной суммой чисел
как у "сеньора с 10-летним опытом работы" задача по поиску пути превратилась в задачу по поиску длины этого пути, которая заметно легче?
У вас задача отдаленно похожа на поиск N-го числа фибоначчи, которую не рекомендуют решать рекурсией. Почему вы не попробовали переделать на рекурсию?
И если уже заморачиваться на алгоритмы, то у вас в условии граф. Что мешает добавить снизу еще один ряд с одной точкой (в которую можно перейти из любого места нижнего ряда) и найти самый длинный путь между этой точкой и начальной? Задача по поиску кратчайшего пути между двумя точками графа общеизвестная и за много лет оптимизирована, а задача самого длинного пути решается аналогичным образом
Мне важно было легко объяснить решение, а графы и кеширование подзадач кажется сложнее и выглядят как оверинжиниринг для задачи, которая решается тремя строками кода. Но предлагаемый вами вариант бесспорно хорош, спасибо
У нас тут граф с N вершинами и O(N) ребрами, представленное решение работает за O(N), даже если его допилить под поиск пути. Более общие алгоритмы для кратчайшего пути смогут дать такую асимптотику?
Задача по поиску кратчайшего пути между двумя точками графа общеизвестная и за много лет оптимизирована, а задача самого длинного пути решается аналогичным образом
Ха. Задача поиска самого длинного пути - на порядки сложнее, если только у вас граф не ацикличиский, где почти любая аддитивная целевая функция пути решается одним и тем же алгоритмом динамического программирования (что и есть случай в статье).
Это потому, что критерий кратчайшего пути почти автоматически исключает хождение по циклам, это же не выгодно. А вот в длиннейшем пути ходить по циклам бывает выгодно.
Я и подразумевал, что граф ацикличный - при поиске кратчайшего пути в графе с циклами тоже могут бы проблемы, если веса ребер отрицательные. Кстати возможно так и стоит поступить - решить обратную задачу (кратчайший путь), только брать веса с противоположным знаком.
P.s. Я там опечатку допустил - имелось в виду рекурсию заменить итерациями.
Кстати возможно так и стоит поступить - решить обратную задачу (кратчайший путь), только брать веса с противоположным знаком.
Плохая идея. Большинство алгоритмов поиска кратчайшего пути, вроде Дейкстры, вообще не работают, если в графе есть отрицательные ребра. Даже если нет отрицательных циклов. Работает какой-нибудь алгоритм Беллмана-Форда работает, но он в N раз медленнее на этой задаче.
Надо знать какие бывают алгоритмы, и где они применимы. Соответственно, ваш граф ациклический - так что тут работает динамическое программирование и никакие другие алгоритмы тут не нужны. Они сложнее, медленнее, и не факт, что заработают вообще из-за отрицательных ребер. А динамическому программированию вообще пофигу, что считать - минимальную длину, максимальную длину, произведение, минимальное или максимальное ребро на пути.
Первая реакция разработчика
"Напишу рекурсию, которая проверит все пути и выберет лучший".
Прошу прощения за снобизм, но это первая реакция человека, которому рановато называться разработчиком.
Ну то есть, это надо было вообще ни разу в жизни не упереться в производительность алгоритма. Не убить процесс, который завис на неожиданно долгих вычислениях. Не писать в универе лабу по динамическому программированию, наконец. По-моему звучит скорее как джун-вкатун.
У вас высокие планки)
Понимание, что опорожнение кишечника и снимание штанов не коммутативны, нынче высокая планка?)
Планки у нас постоянные, а вот почему динамическое программирование упоминается на КДПВ но не в статье, было бы интересно узнать.
А как можно ниже? Насколько мне известно, знания алгоритмической сложности операций на коллекциях/типах языка это абсолютно базовые джуниорские вопросы. Вкатун, конечно, может вызубрить, что мол тут O(1), тут O(N), но неспроста ему, скорее всего, предложат решить простую алгоритмическую задачу, чтобы убедиться, что эти "ошки" для него значат хоть что-то вообще. Оффтопный пример, я недавно был в отеле, где на розетках везде заботливо прикеили надпись "220 Вт". Спасибо, но не от всей души, как говорится. Полагаю в меру разумный иностранец, возьмет свой смартфон с ИИшкой, получит перевод, успокоится, что ну какие 220 ватт, мне для бритвы и 30 хватит и получит забавный пшик в руках, надеюсь забавный. А осторожному такая надпись не нужна, он и так знает, что напряжение в сетях может отличаться в разных странах. А где-то радуется один новый джун-вкатун, который выучил "раз массив, то говорим O(1)". Ага, щас.
На Хабре очень любят бунтовать против литкода, уговаривать, что мол "я уже 15 лет в области, и мне ни разу не пригодились эти ваши алгоритмы". Вброс и провокация. В одно время я пошел в самый настоящий кровавый-зомби-энтерпрайз, потому что хотел использовать 0.001% своего мозга (максимум) и иметь 300кк/нс (минимум). По описанию проекта было понятно, наукоемкость равна ровному 0, по сути, даже никакой алгоритмической обработки данных не предвидилось вообще...
...Ну и что, это проект, он работает с данными. Не с данным (одним!), а с набором данных. Везде, где есть наборы данных и какие-то даже около-тривиальные операции с ними, везде так или иначе есть алгоритмы. Но, хуже того, у данных есть структуры, которые тоже не с неба падают (бывший архитектор написал, да), и даже выбор правильной, подходящей задаче, структуры данных это уже алгоритмическая задача, где нужно не только помнить оценки сложности, но и уметь выбирать подходящие варианты с учетом всех компромиссов.
Можно было, конечно, раньше где-то хитро засесть между фронтендом и разработчиками БД, у вторых просить конкретные выдачи данных, а первым фигачить их в джейсончик, и гордо именовать себя бэкенд разработчиком, как всегда, очень плохо решая проблемы авторизации (ну например)... Да, точно, называть при этом "бизнес логикой" бесконечные нагромождения if-ов в коде и требовать побольше денег, потому что эту мешанину if-ов уже невозможно держать в голове (особо будет сложно следующему на вашем месте), но, думаю, те времена уже прошли.
Вы просто не осознаёте, насколько широк набор задач, которые ставятся перед разработчиками)
Ну то есть, это надо было вообще ни разу в жизни не упереться в производительность алгоритма.
Можно, но не факт, что этот "раз в жизни" научит правильно работать с такими задачами. Когда у тебя проблема производительности возникает раз в год-два, а вот вопросы сложности бизнес-логики и архитектуры решаешь регулярно... вполне логично, что ты просто не научишься решать такой класс задач.
Не писать в универе лабу по динамическому программированию, наконец.
Дык в программировании огромная куча народу без профильного образования. Я бы даже сказал, что это раньше была скорее норма, чем исключение. Да и это не панацея: у меня вот образование профильное, но лаб по динамическому программированию не было. Больше того, вообще не было лаб или домашних работ, где было реально упереться в проблемы производительности. Впервые об этом задумался на олимпиадах и всяких соревнованиях, где наивные алгоритмы перестали успевать решать задачу. А в реальной работе проблемы производительности были обычно не в моих алгоритмах, а в том, как я работал с БД (неоптимальные индексы и запросы, не запихивание множества изменений в одну транзакцию и т.п.) или с 3D-графикой (крутил на процессоре то, что стоило бы обсчитывать шейдерами на видеокарте например).
Так что уж простите, но за снобизм не извиню)
Не знаю, не знаю. Без понимания алгоритмической сложности как только понадобится самостоятельно написать хоть какой-то алгоритм сложнее перекладывания полей из одной джсонки в другую, и как только в этот алгоритм попадёт крупный кусок данных, проблемы обязательно вылезут. Как будто бы этого можно избежать, только если заниматься исключительно крудошлёпством на фреймворках.
Скорее всего он просто работал в областях, где производительность редко упирается в сложность алгоритма, а чаще в запросы к базе или сетевые задержки
"Напишу рекурсию, которая проверит все пути и выберет лучший".
Почему-то новичкам в качестве примера рекурсии показывают факториал, что является неудачным примером на мой взгляд. Факториал лучше реализовывать с помощью цикла, причем это так же просто.
Это стандартная задача на динамическое программирование. Тут можно как снизу-вверх, так и сверху-вниз делать. Хоть циклами, хоть рекурсией с запоминанием результатов.
Пока Вы не рассказали решение, я даже был готов математически обосновать его невозможность.
Вы меня сломали. Я тоже не умею кодить теперь.
Любую сложную задачу можно решить разными путями. Сначала в голову приходят наиболее сложные способы. Но если начать думать, то задача неожиданно решается относительно просто и минимальными ресурсами. Весь вопрос в том что надо размышлять. Я тоже не умею кодить и в сложной задаче ( описана в публикации в моем профиле на хабре) я избрал путь без кода на клиенте, но с кодом на сервере при команде в 2 человека. Избавление от высокоуровневых ЯП потребовало больших затрат мыслительной энергии и в результате получилась система, которая уже несколько лет живет и практически не напрягает в поддержке. Без всяких абстракций и современных "подходов".
Наглядная демонстрация того, зачем было нужно высшее образование. ВУЗ давал механизм решения задач и умение им пользоваться, понимание - знания из какой отрасли нужны для решения этой задачи, хотя бы приблизительная оценка того, какого специалиста и какой квалификации привлечь для решения той или иной задачи в качестве консультанта. Есть большая пропасть между я могу решить вот конкретно эту задачу, с помощью вот этого инструмента и я умею решать задачи. ИИ навыка решать задачи не даст, более того излишнее использование ИИ "тупит" мозг. ИИ хорош, как вспомогательный инструмент для специалиста, который и так задачи своими мозгами решает нон-стоп.
Человек, который даже не открывал Кнута, в принципе не может называть себя сеньором, даже с 10 годами стажа. У водопроводчика тоже есть стаж.
в java много бывших сантехников
Даже если вкатиться без образования - за 10 лет (на то он опытом и называется) должно быть понимание, что полный перебор и рекурсия - это то чего следует избегать всегда.
По этому заголовок вполне верный, это статья справедлива для "кодера 10-летнего". Но уж никак не для "программиста" или "разработчика"
Задача, которая всё изменила
Представь треугольник из чисел:
Что вы «ерундой болтаете»? Почитайте книги Д.Э. Кнута «Искусство программирования для ЭВМ.», например, третий том: «Сортировка и поиск» и у вас подобных мыслей не возникнет.
Когда я реализовывал алгоритм своей обучающей программы «L'éclole» (см. ее работу на видео: 001-ФранцузскийАлфавит.mp4 : https://disk.yandex.com/i/G4pJZ__AKhtHsw ), так я себе чуть мозги не сломал. Вот это была задача! А у вас это просто отсутствие хорошего ВУЗ-овского образования.
Круто. Да и таких большинство)
кнут для математиков а не для программистов - сам он не смог применить написаное
Кнут для математиков, а не для программистов - сам он не смог применить написанное
Вы говорите за Кнута или за участников форума LINUX.ORG.RU?
Кнут рассказывает о существующих алгоритмах, мере их эффективности, вычисляет асимптотику их поведения, указывает наихудшие и наиболее вероятные случаи и т.д. и т.п. Это, конечно, программистам знать вредно? И, правда, зачем писать эффективные алгоритмы, экономить память и время их работы, когда компьютерной памяти – вагон, процессоров – куча, а мегатонные фрейморки перестали напрягать? Вот и получаем программу для скачивания видео на «всего лишь» 471 Мегабайт, тогда как аналогичная имеет размер 18 Мегабайт. Потому выбираем «очевидный» алгоритм на больших данных и ужасаемся его медленной работе.
“Когда бы рыло, смогла бы ты вверх поднять, тебе бы видно было….»
Вообще-то он описал свой компьютер и на его языке реализовал большинство своих алгоритмов. Можете развлечься «ты ж программист» и написать реализацию этого компьютера . А потом закодировать пару алгоритмов…
Я думаю автор просто хитрит, и вокруг ~обычной задачи сотворил некую атмосферу, вложил художественный смысл…
Все он понимает…
Так-то у каждого в какой-то рандомный момент появляется синдром самозванца, но не стоит забывать, что подходы самые разные бывают, и всё зависит только от того хватает ли практического опыта, но в целом, пока дело не касается оптимизации самое важное, что бы код работал)
Добро пожаловать в клуб! У каждого из нас есть свой треугольник, после которого приходит это озарение. У кого-то это задача на графы, у кого-то на комбинаторику. Главное не испугаться этого чувства, а принять его как точку роста
Разве после джуна код сразу попадает в прод? ))
она выглядит решаемой в лоб, но подобрана так
вообще ни разу не выглядит. особенно Euler+ на Hackerrank. Многие задачи поставлены так, что иногда требуют передний край математики, ибо построение даже простейших граничных условий приводит к тупику.
А есть топ-игрок с кодфорсес, который года полтора назад решил весь Project Euler, его зовут Radewoosh
Какие задачки советуете порешать, чтобы попрактиковаться в таком?
На заре книгопечатания - во время прошлой информационной революции, ключевой компетенцией была сама технология Гуттенберга. Но довольно быстро, по историческим масштабам, технология стала лишь обычным средством. Главную роль стали играть люди, которым есть что сказать в помощью печатного слова. Нечто подобное произойдёт и в рамках современной информационной революции. Что удивительно, даже сроки развития и распространения современных информационных технологий сопоставимы со сроками распространения книгопечатания. Как ни крути, а главное в информации - это передаваемая с её помощью идея: "Сначала было слово!"
Программист - это человек, который преобразует некий алгоритм в код. Основная задача программиста - написать оптимальный код для алгоритма в соответсвии с архитектурой и возможностью программно-аппаратного окружения.
Что это значит? А значит это то, что алгоритм зачастую диктуется специалистом какой то предметной области будь то: бухгалтер, экономист, математик, биолог, квантовый физик и тп. Т.е. очевидно, что программист, умея писать код, никогда не сможет познать все области знаний.
И что мы видим? Вот появился программист с 10-ю годами стажа, влез в область (в данном случае в область математмки) с которой он никогда не работал и даже не удосужился спросить у математиков, алгоритм решения этой задачи (кстати, кто ставил задачу, никто?). А чтобы делал, если бы задача оказалась сложнее, ну например, математик, изучающий нейросети, попросил бы тебя написать ему фреймворк, который бы использовал видеокарты для ускорения вычислений, ушел бы в сантехники?
Постскриптум, все эти литкод алгосики не требуют каких то специальных знаний, лабораторий со сложным и дорогим оборудованием, и их с удовольствием щелкают увлеченные школьники старших класмрв и студенты начальных курсов.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Как я осознал, что не умею кодить