Comments 127
Спасибо, об этом стоило напомнить
И почему через пару лет, когда ИИ будет писать весь код за меня, это понимание станет единственным, что меня спасёт.
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 и тд давно уже живут ф библиотеках и фреймворках), то необходимо посмотреть, а как ее лучше решить не "в лоб" (перебор - это, например, в лоб).
И вот тут нужно либо воспользоваться математиком, который подскажет куда копать, или как раз таки спросить у ЛЛМ - именно не код написать, а про алго и оптимальные пути его решения, потом самому переложить это в код.
И, имхо, правильный инженер должен поступит именно так.
Затем, в сухом остатке остается знание, что при возникновении такого типа задач нужно воспользоваться таким-то алгоритмом. Не нужно инженеру или программисту знать наизусть кучу вещей, которые могут не понадобиться вообще. Нужно лишь понимание где может возникать бутылочное горлышко - а для этого нужна лишь базовая логика, остальное можно будет уточнить или проверить.
Ну и, иногда, решения "в лоб" работают лучше, чем куча хитростей и сложный алго - это тоже надо понимать.
А как вы поймете что LLM не галлюцинирует, предлагая вам "оптимальный путь"? Как вы оцените, действительно ли предложенный алгоритм подходит для вашей задачи и ваших ограничений? Чтобы эффективно пользоваться советами математика, нужно самому быть немного математиком
Нужно понимание и логика.
Если есть предложенный вариант, но нет понимания как он работает - попросить обьяснение, а не алгоритм или сразу код.
И подумать над ним, понять - и тогда принимать или не принимать этот вариант.
А просто быть "немного математиком" - это как вычислять длину деревянной распорки по модулю комплексных чисел над полем Галуа, вместо того чтобы воспользоваться теоремой Пифагора (можно даже не понимать ее доказательства).
Вот объяснения LLM делать вообще почти не умеет. Она почти гарантировано галлюционирует их. Весьма правдоподобные, но противоречивые, ложные и нелогичные.
Представьте что вы общаетесь с учеником-троечником, который очень много чего читал, но сам не понял.
Пусть извлечёт воспоминания и попробует вам объяснить - так сами увидите связь
Тут другая ситуация: студент к экзамену ничего не выучил, но списал ответ у товарища (не факт что правильно, кстати). И он начинает вам заливать. Складно, красиво, но вообще не факт что релевантно к теме экзамена. Дело в том, что эти задачки много где приводятся с кодом, но редко с вменяемым объяснением. Поэтому LLMка, даже если угадает код, редко "вспомнит" хоть какие-то факты из объяснений.
Буквально ещё 3 года назад легко в процессе работы можно было наткнуться на задачу, которую проще решить чем опознать (ну какое-нибудь префиксно-суффиксное дерево я сначала писал, а потом узнал как оно называется).
Сегодня - да по описанию нейронка часто способна воспроизвести правильные термины.
У меня к вам только один вопрос: зачем вы старались, писали статью руками в лоб, когда можно было бы просто сгенерировать ее с помощью нейросети за минуту? Пора бы уже совершить фундаментальный сдвиг парадигмы в своей ментальной модели, и перестать заниматься этой ерундой.
Ну так для этого нужно промпт писать
Понимаю, короткий промпт написать сложнее, чем большую статью, но это важный навык в современном мире, где промпт-инжениринг совершил тектонический сдвиг в сфере революционных перфомансов.
Бесспорно, да. С таким же успехом можно комментарии генерить)) Короче пришлите мне ссылку на вашу сгенерированную статью, любо посмотреть
Пожалуйста: https://habr.com/ru/articles/972630
Только никому не говорите, что она сгенерирована, а то растащат на цитаты.
От случая к случаю всё меняется
Если надо написать мусорный текст, то да, короткий промпт. Но если нужен качественный материал, который меня бы устроил, нейросеть годится искать материал, подбирать выражения, менять и согласовывать стиль, вычитывать, даже писать куски. Но максимальное ускорение работы, которого можно достичь в принципе - я пишу сумбурно и тезисно, а она вслед за мной раскрывает, упрощает и украшает мысли, не добавляя отсебятины. И потом это придётся ещё и править
Повторюсь, это именно самый быстрый метод для качественного текста. Но другой нам не нужен, ведь так? И то тут я должна от и до знать, чего хочу. Если работа более исследовательская, так просто не выйдет.
Это помощник, но ошибка позволять ему делать что-то самому. Даже если на вид норм
Прошу лишь не выкладывать то, что вы сгенерили за минуту. Пользуйтесь сами, но не замусоривайте сайт.
Так статья так и создана, странно, что тут серьезное обсуждение в комментах. Обороты в духе "Джун пишет вложенный цикл по массиву из миллиона элементов. Не чувствует боли. Процессор "съедает" всё за секунду." или "В этот момент я понял: проблема не в Python. Не в памяти. Не в процессоре. Проблема в том, как я думаю." -- это же очевидный гпт, я будто в мусорные инстаблоги с аи слопом зашел
Джун пишет вложенный цикл по массиву из миллиона элементов. Не чувствует боли. Процессор "съедает" всё за секунду.
Потом этот код попадает в продакшн с 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-графикой (крутил на процессоре то, что стоило бы обсчитывать шейдерами на видеокарте например).
Так что уж простите, но за снобизм не извиню)
Не знаю, не знаю. Без понимания алгоритмической сложности как только понадобится самостоятельно написать хоть какой-то алгоритм сложнее перекладывания полей из одной джсонки в другую, и как только в этот алгоритм попадёт крупный кусок данных, проблемы обязательно вылезут. Как будто бы этого можно избежать, только если заниматься исключительно крудошлёпством на фреймворках.
Скорее всего он просто работал в областях, где производительность редко упирается в сложность алгоритма, а чаще в запросы к базе или сетевые задержки
"Напишу рекурсию, которая проверит все пути и выберет лучший".
Почему-то новичкам в качестве примера рекурсии показывают факториал, что является неудачным примером на мой взгляд. Факториал лучше реализовывать с помощью цикла, причем это так же просто.
Это стандартная задача на динамическое программирование. Тут можно как снизу-вверх, так и сверху-вниз делать. Хоть циклами, хоть рекурсией с запоминанием результатов.
Пока Вы не рассказали решение, я даже был готов математически обосновать его невозможность.
Вы меня сломали. Я тоже не умею кодить теперь.
Вполне возможно что в процессе математического обоснования вы пришли бы к тому, что математически эта задача как раз решается за n^2.
Пока Вы не рассказали решение, я даже был готов математически обосновать его невозможность.
Ну таких "детских" ошибок очень легко избегать.
Главный вопрос, который нужно задавать - для выбора вам нужно сравнивать между собой "сами данные" или "их аггрегат".
Любую сложную задачу можно решить разными путями. Сначала в голову приходят наиболее сложные способы. Но если начать думать, то задача неожиданно решается относительно просто и минимальными ресурсами. Весь вопрос в том что надо размышлять. Я тоже не умею кодить и в сложной задаче ( описана в публикации в моем профиле на хабре) я избрал путь без кода на клиенте, но с кодом на сервере при команде в 2 человека. Избавление от высокоуровневых ЯП потребовало больших затрат мыслительной энергии и в результате получилась система, которая уже несколько лет живет и практически не напрягает в поддержке. Без всяких абстракций и современных "подходов".
Наглядная демонстрация того, зачем было нужно высшее образование. ВУЗ давал механизм решения задач и умение им пользоваться, понимание - знания из какой отрасли нужны для решения этой задачи, хотя бы приблизительная оценка того, какого специалиста и какой квалификации привлечь для решения той или иной задачи в качестве консультанта. Есть большая пропасть между я могу решить вот конкретно эту задачу, с помощью вот этого инструмента и я умею решать задачи. ИИ навыка решать задачи не даст, более того излишнее использование ИИ "тупит" мозг. ИИ хорош, как вспомогательный инструмент для специалиста, который и так задачи своими мозгами решает нон-стоп.
Человек, который даже не открывал Кнута, в принципе не может называть себя сеньором, даже с 10 годами стажа. У водопроводчика тоже есть стаж.
Даже если вкатиться без образования - за 10 лет (на то он опытом и называется) должно быть понимание, что полный перебор и рекурсия - это то чего следует избегать всегда.
По этому заголовок вполне верный, это статья справедлива для "кодера 10-летнего". Но уж никак не для "программиста" или "разработчика"
Задача, которая всё изменила
Представь треугольник из чисел:
Что вы «ерундой болтаете»? Почитайте книги Д.Э. Кнута «Искусство программирования для ЭВМ.», например, третий том: «Сортировка и поиск» и у вас подобных мыслей не возникнет.
Когда я реализовывал алгоритм своей обучающей программы «L'éclole» (см. ее работу на видео: 001-ФранцузскийАлфавит.mp4 : https://disk.yandex.com/i/G4pJZ__AKhtHsw ), так я себе чуть мозги не сломал. Вот это была задача! А у вас это просто отсутствие хорошего ВУЗ-овского образования.
Круто. Да и таких большинство)
Кнут для математиков, а не для программистов - сам он не смог применить написанное
Вы говорите за Кнута или за участников форума LINUX.ORG.RU?
Кнут рассказывает о существующих алгоритмах, мере их эффективности, вычисляет асимптотику их поведения, указывает наихудшие и наиболее вероятные случаи и т.д. и т.п. Это, конечно, программистам знать вредно? И, правда, зачем писать эффективные алгоритмы, экономить память и время их работы, когда компьютерной памяти – вагон, процессоров – куча, а мегатонные фрейморки перестали напрягать? Вот и получаем программу для скачивания видео на «всего лишь» 471 Мегабайт, тогда как аналогичная имеет размер 18 Мегабайт. Потому выбираем «очевидный» алгоритм на больших данных и ужасаемся его медленной работе.
только потом исправить и поддерживать 471мб легче чем 18мб которые опять переписывать из-за непонятности
Я имел в виду опенсорсные проекты: гуишные бинарники «MediaDownloaderQt5-5.4.3», который, после подгрузки вспомогательных бинарных файлов из Интернета, вроде, библиотеки FFMpeg, занимает несколько сотен мегабайт и консольный бинарник «yt-dlp.exe» на 18 «метров». Причем первый тоже использует второй.
Да, у него полно разных рюшечек, но пользоваться ими нет ни малейшего желания – громоздко и неудобно. А вторым, с помощью конфигурационного файла, можно делать всю туже самую работу, но в консольном режиме, в т.ч., пакетное скачивание вместе с субтитрами и прочими «причандалами» видео-роликов из «народного» видео-хостинга.
При этом консольный загрузчик обновляется каждые две недели. Чтобы не делать это вручную, я сделал небольшую гуишную «пришлёпку» «MiniDL64r.exe» и опубликовал её в статье: «Минималистский графический интерфейс, на C++ / WTL, для консольного загрузчика» ( https://habr.com/ru/articles/955838/ ). При этом, размер этого бинарника менее 300 килобайт! Причем, работа вся делается та же самая. Мне, лично, очень удобно. Главное ведь, что? Загружать видео, а не «наслаждаться» громоздким интерфейсом от Qt. Не так, ли? Но, если вам удобней иметь дело с последним, то, кто вам запретит?
“Когда бы рыло, смогла бы ты вверх поднять, тебе бы видно было….»
Вообще-то он описал свой компьютер и на его языке реализовал большинство своих алгоритмов. Можете развлечься «ты ж программист» и написать реализацию этого компьютера . А потом закодировать пару алгоритмов…
Я думаю автор просто хитрит, и вокруг ~обычной задачи сотворил некую атмосферу, вложил художественный смысл…
Все он понимает…
Так-то у каждого в какой-то рандомный момент появляется синдром самозванца, но не стоит забывать, что подходы самые разные бывают, и всё зависит только от того хватает ли практического опыта, но в целом, пока дело не касается оптимизации самое важное, что бы код работал)
Добро пожаловать в клуб! У каждого из нас есть свой треугольник, после которого приходит это озарение. У кого-то это задача на графы, у кого-то на комбинаторику. Главное не испугаться этого чувства, а принять его как точку роста
Разве после джуна код сразу попадает в прод? ))
она выглядит решаемой в лоб, но подобрана так
вообще ни разу не выглядит. особенно Euler+ на Hackerrank. Многие задачи поставлены так, что иногда требуют передний край математики, ибо построение даже простейших граничных условий приводит к тупику.
А есть топ-игрок с кодфорсес, который года полтора назад решил весь Project Euler, его зовут Radewoosh
Какие задачки советуете порешать, чтобы попрактиковаться в таком?
Практические. Те, что решают реальные проблемы и задачи. А теорию можно у ии попросить
Вы так говорите, будто задачи с литкода в практике не встречаются. Встречаются только так. Вот бесстыжая ссылка на мою статью. Только без знаний базы и прорешивания кучи таких задач вы даже и не заметите, что вот это вот тривиальное действо из двух вложенных циклов на самом деле какой-то алгоритм. Поэтому бытует ошибочное мнение, что это не практичные задачи.
Попробуйте сделать какой-нибудь игровой движок/рендерер - там и графика мат.челенджей накинет (освещение, сглаживание, фильтры и эффекты) и какой-нибудь ECS. Добавляем воксели и получаем новый класс проблем для оптимизации.
На заре книгопечатания - во время прошлой информационной революции, ключевой компетенцией была сама технология Гуттенберга. Но довольно быстро, по историческим масштабам, технология стала лишь обычным средством. Главную роль стали играть люди, которым есть что сказать в помощью печатного слова. Нечто подобное произойдёт и в рамках современной информационной революции. Что удивительно, даже сроки развития и распространения современных информационных технологий сопоставимы со сроками распространения книгопечатания. Как ни крути, а главное в информации - это передаваемая с её помощью идея: "Сначала было слово!"
Программист - это человек, который преобразует некий алгоритм в код. Основная задача программиста - написать оптимальный код для алгоритма в соответсвии с архитектурой и возможностью программно-аппаратного окружения.
Что это значит? А значит это то, что алгоритм зачастую диктуется специалистом какой то предметной области будь то: бухгалтер, экономист, математик, биолог, квантовый физик и тп. Т.е. очевидно, что программист, умея писать код, никогда не сможет познать все области знаний.
И что мы видим? Вот появился программист с 10-ю годами стажа, влез в область (в данном случае в область математмки) с которой он никогда не работал и даже не удосужился спросить у математиков, алгоритм решения этой задачи (кстати, кто ставил задачу, никто?). А чтобы делал, если бы задача оказалась сложнее, ну например, математик, изучающий нейросети, попросил бы тебя написать ему фреймворк, который бы использовал видеокарты для ускорения вычислений, ушел бы в сантехники?
Постскриптум, все эти литкод алгосики не требуют каких то специальных знаний, лабораторий со сложным и дорогим оборудованием, и их с удовольствием щелкают увлеченные школьники старших класмрв и студенты начальных курсов.
Программист - это человек, который преобразует некий алгоритм в код.
Так было 50 лет назад.
То что вы написали - это кодер. Запрограммировать какие-то готовые формулы, выданные условным математиком - это тоже кодерство.
А вот программист, в более широком смысле может (и чаще всего делает) придумывать сам алгоритм, если его нет. Также как архитектуру, программно-аппаратное обеспечение. Не всегда есть специально выделенный архитектор.
А вот программист, в более широком смысле может (и чаще всего делает) придумывать сам алгоритм, если его нет.
Придумывают новые алгоритмы инженеры, которых выкупают за миллионы топовые IT компании, всем остальным хватает библиотек. Мы с вами, к сожалению (или к счастью), ничего нового не придумываем.
Процитирую мифического человека месяца, написанного в конце прошлого века:
Повторно разработать математический компонент стоит дорого, а разобраться в функциональности стоит дешево
Придумывают новые алгоритмы инженеры, которых выкупают за миллионы топовые IT компании,
Нет. Если у вас стоит задача посчитать какую-то метрику, то вы должны придумать эффективный алгоритм рассчета этой метрики, или свести задачу к известному алгоритму. Вы не будете на каждый чих дергать топового инженера за миллионы.
Например, если вам надо посчитать среднее в радиусе вокруг каждого числа в массиве, то вы сами должны догадаться, что вам надо просто поддерживать сумму в окне, а не гнать 2 вложенных цикла. Нет никакой библиотеки, которая бы такие вещи делала. Потому что это слишком простая вещь. Как и нет библиотеки, которая бы решала задачу из статьи, потому что это слишком специфичная задача. И большинство задач, сотящих перед вами, будут именно такими - уникальными или слишком простыми, чтобы быть в библиотеке.
Вообще, реализацию найти можно, но вам надо знать ключевые слова "среднее в окне", "динамическое программирование" и все такое.
вы должны придумать эффективный алгоритм рассчета этой метрики
Почти любой метод, который я пишу в java, я могу назвать алгоритмом. Но отвечая @tklim, я имел ввиду алгоритм в более узком смысле — алгоритмы сортировки или поиска по графу и т.д. это алгоритмы, которые мы используем в основном в библиотеках (но возможно и иногда сами пытаемся их применить для наших сущностей), потому что они придумывались и шлифовались уже очень долго, что довольно глупо "изобретать" их с нуля, легче просто разобраться в существующих и применить по необходимости. Видимо я не так понял, что имел ввиду комментатор под "программист придумывает сам алгоритм, если его нет"(
я имел ввиду алгоритм в более узком смысле — алгоритмы
Но между ними нет принципиальной разницы. Просто что-то чуть более сложное и известное обозвали алгоритмами "сортирвки" или "поиска по графу". @tklim различия между ними и не делает, в отличии от вас.
Потому что тут нельзя провести четкую границу, где заканчивается код который вы "пишите на джаве" и начинается "алгоритм" в вашем понимании.
довольно глупо "изобретать" их с нуля, легче просто разобраться в существующих и применить по необходимости
Да, известные уже решенные задачи не надо придумывать с нуля, можно взять готовое. Как можно бойлерплейт код для какого-нибудь системного АПИ просто скопировать из спавки или со стак-оверфлоу, вместо выдумывания с нуля. Но у вас редко будет именно задача из учебника прямо слово-в-слово. Иногда вам придется выдумывать что-то свое.
Но вот свести вашу задачу к известной и вообще сначала понять, что у вас задача - это проблема программиста. И для этого надо как минимум большинство этих известных задач знать хотя бы поверхностно и понимать какие там бывают методы решения.
Вы, похоже, как и ТС, работаете в какой-то очень узкой теме. И также узко воспринимаете понятие программист.
всем остальным хватает библиотек. Мы с вами, к сожалению (или к счастью), ничего нового не придумываем.
Где-то заплакали эмбеддед-программисты, которые могут не использовать библиотеки или писать свои.
Т.е. очевидно, что программист, умея писать код, никогда не сможет познать все области знаний.
Необходимо знать базу предметной области, а чаще даже больше "заказчика".
И если для вас программист и инженер - это отдельные сущности, это печально.
Где-то заплакали эмбеддед-программисты, которые могут не использовать библиотеки или писать свои.
Можно писать свои библиотеки, но при этом использовать известные алгоритмы сортировок, поиска и т.д., это не "изобретение нового алгоритма".
Вы, похоже, как и ТС, работаете в какой-то очень узкой теме. И также узко воспринимаете понятие программист.
Расскажите как вы воспринимаете понятие программист) И где я вообще, что-то писал о том как я воспринимаю понятие программист?)
Что-то очень сомнительно, чтобы сеньор с 10-летним опытом не понимал таких вещей. Да, можно не понять с ходу, как лучше решать задачу, но то, что перебор сверху вниз плохая идея — это как раз очевидно.
Когда фокусник показывает фокус, лучше смотреть на сам фокус, а не пытаться разглядеть, что в рукаве))
А не очевидно, что изначальная постановка задачи ущербна?
Все начали с умным видом доказывать, что легко решаемо, но никто не обращает внимания, что на входе те самые 2^100 узлов, и никакой, даже самый продвинутый алгоритм здесь уже не поможет.
В смысле? При N уровнях узлов N*(N+1)/2.
Вы что-то напутали, там алгоритм за O(N^2) в итоге. Никаких 2^100 нигде нет.
если 100 уровней - строк, значит на последнем уровне уже 2^100 узлов, они же удваиваются на каждый следующий уровень:
на 0 - 1 (2^0)
на 1 - 2 (2^1)
,,,,
на 10 - 1024 (2^10)
,,,
на 100 ~ 10^33 (2^100)
Где вы удвоение заметили? Элементов там +1 на следующем уровне. Там 1,2,3,4,5 а не 1,2,4,8,16 элеметов в строках.
Да, там по 2 варианта куда пойти (вниз или вправо) из каждой клеточки, Но почти в каждую клеточку можно войти из двух предыдущих. Да, путей там экспоненциально много, но клеточек всего квадрат. Именно поэтому полный перебор медленный, а хорошее решение - быстрое.
Да на самом деле можно и сверху вниз ту же константу по памяти сделать. Обход получится чуть менее оптимальным, но не прям смертельно.
И зачем вот эти вот "олимпиадные" задачки нужны кроме как проходить собеседования? Так где нужен лютый матан - нужен лютый матан, потроха нейронок, какая ньть предметная область вроде твердотельного моделирования, геймдев тот же, там такими задачками не обойтись, дифуры и матрицы понадобятся. Крудошлепство - даже рядом ничего подобного, там скорее борьба со сложностью предметной области, паттернами и современной инфраструктурой которая сама по себе уже как матан. Задачки такие хорошо известны, описаны, и значит как раз для ИИ наоборот - доступны по умолчанию, именно их он надочен решать как следует. И то что названо "инженерным чутьем" это никакое не чутье а как раз насмотренность на таких задачах, которое у ИИ по определению есть. Как раз реальная человеческая предметная область со всеми своими неоднозначностями, несформулированными требованиями, массой сложных взаимосвязей - вот тут кмк ИИ спасует. Ему останутся хорошо формализируемые вещи, собственно как и всегда было для железных болванов, просто на несколько новый уровень абстракции вышли. Но уж точно не в таких задачках будем с ним тягаться.
Если у вас есть хоть какие-то данные и работа с ними, то там постоянно именно такие "олимпиадные" задачки и возникают. У меня несколько статей об этом есть. Бесстыжая ссылка.
Вот только без знания базы и насмотренности на такие задачи вы даже и не заметите этого. Потому что почти все такие задачи можно решить наивно тупо переведя задачу с русского на язык программирования. Ну тормозит немного, что такого?
Чтобы распознать задачу и понять что вам ИИ не наврал, надо знать базу.
Да, в формошлепстве такое встречается реже. Но ИТ состоит далеко не только из формошлепства.
Крудошлепство - даже рядом ничего подобного
А вы пробовали в крудошлёпство кооп добавлять?
Ссылка на эту задачу на литкоде. Только тут необходимо найти минимальную сумму.
https://leetcode.com/problems/triangle/description/
Доступные языки программирования:
Странно, это же простая задача на "жадность", в универе куча аналогичных задач решается на курсе "методы и алгоритмы принятия решений".
Почти все задачи на логистику очень похожи, только там найти минимум нужно.
Жадность тут не работает.
1
1 10
1 1 100
1000 1 1 1Жадно вы пойдете в 10->100 и оттуда в 1000 уже никак не попадете. Даже если вы будете идти в максимальное число по массиву, легко подобрать тест, где это не будет работать.
Это что, айтишнику алгебру что ли надо знать¿?...)
Современный программист избалован избытком ресурсов, пишет код не стесняя себя ограничениями.
Для того, чтобы прочувствовать ограничения на "собственной шкуре", есть, к примеру, Ардуино. Всё как в старый компьютерах - 2кб оперативки, 8-битный процессор, работаешь почти напрямую с железом. Любое такое 2ⁿ обернётся, в лучшем случае, перезагрузкой, в худшем - полным капутом платы. Сам вручную регулируешь напряжения, амперы, шмамперы, поменяешь катод и анод - прощай светодиод.
Инженерия - это выбор из компромиссных вариантов и менеджмент ошибок/катастроф. То, что вы описали - это математика (информатика, если хотите), которую литкод вам замечательно натренирует.
Как я осознал, что не умею кодить