Пять лайфхаков, как сдавать олимпиадные задачи, если ты пишешь на Python / Григорий Шовкопляс
HTML-код
- Опубликовано: 16 ноя 2021
- Григорий Шовкопляс - преподаватель Академии больших данных MADE.
В этом видео Григорий поделится полезными фишками, которые помогут улучшить опыт использования языка Python для сдачи задач в тестирующую систему:
• как ускорить работу программы;
• как лучше считывать входные данные;
• как избежать проблем с рекурсией.
VK Team - это безграничные возможности проявить себя. Мы делаем современные и быстрые интернет-сервисы, доступные каждому. На этом канале делимся опытом компании VK, рассказываем о технологиях, наших образовательных проектах и жизни команды.
😎 Сообщество ВКонтакте: vkteam
👨🎓 VK Education: education.vk.company/
🏆 Чемпионаты: cups.online/
👨💻 Карьера в VK: team.vk.company/
Видео классное, но кроме низкой производительности есть ещё проблемы с глубиной рекурсии (либо её недостаточно, либо не хватит памяти), отсутствием структур типа set и тд. Python классный язык, на котором приятно писать, но для олимпиадной проги стоит выбрать плюсы)
Так в питоне же есть множества set
в 99% случаев если решение выполнено в рекурсивном стиле, то это решение по умолчанию не эффективное, за счет очевидного стека вызовов. Уж лучше тогда просто создать руками стек и руками его опустошать.
Да и в олимпиадном программировании на сколько мне известно под питон имеются свои нормативы, так как все понимают его скорость. Да и суть олимпиад как мне кажется, не в борьбе с языком, а в написание алгоритма, который решает поставленную задачу
@@daiske2867, рекурсия часто используется в алгоритмах: 90% алгоритмов на графах (DFS, КСС, СНМ, мосты, точки сочленения,.. ), множество структур (ДД, ДО, BST,.. ) и тд, поэтому говорить о неэффективности таких решений неуместно.
Что касается скорости питона - да, делают тайм лимит под него, но не всегда. Плюсы делают 10^9 операций в секунду, питон ~10^5, поэтому если решение требует 10^7 операций, плюсы выдадут ответ за 0.01с, а питон будет работать гораздо дольше. Согласись, делать тайм лимит 1с для плюсов и несколько часов для питона никто не станет
@@pl3nka, в плюсах есть set - автоматически сортирующееся множество, unordered set - несортирующеся множество. На сколько я помню, в питоне именно второй тип множеств, и это конечно печально, когда задача на структуры стандартной библиотеки, а тебе нужно все делать самому
@@semyonnadutkin6836ты в курсе, что любой рекурсивный алгоритм можно переписать с использованием стандартных циклов и для этого всего лишь необходимо завести собственный стек, и коли ты так ратуешь за эффективность такое решение, всегда будет эффективнее чем аналогичное через стандартную функцию из-за, как бы это не было логичным, накладных ресурсов для вызова функции и хранения ее на стеке вызовов. И даже коли тебе это так уж надо питончик позволяет изменить стандартную константу отвечающую за максимальную глубину рекурсии.
Хорошо коли ты так ратуешь за скорость, почему тогда ты выбираешь небогоугодные кресты, с ровно таким же итого ты можешь взять тот же раст или хорошо, тебя не устраивает его компилятор, который заставляет тебя писать хорошо, то в этом случае обычный Си будет выполять код явно эффективнее крестов, как минимум из-за более чистого бандла (habr.com/ru/articles/347688/). А если сравнивать с # то можно чаем подавиться ненароком( ruclips.net/video/HZTp4ACt5m8/видео.htmlsi=ktJE-a3-X7Ia2ppu).
А вообще лучше всего писать на луа, это лаконичность питона * экосистему Си, раз уж как мы выяснили конкретно скорость тебе не так принципиальна
спасибо
а где крастер ?
5. PyPy
6. Всё-таки учить плюсы
поясните пожалуйста, я занимаюсь олимпиадным программированием на python около 4 лет и до сих пор не понимаю зачем вы пишете такие длинные названия функций и переменных, и вообще зачем функции в олимпиадном программировании, если они замедляют скорость работы программы?
Здравствуйте, а со скольки лет начали заниматься, если не секрет?
О, боги, а потом такие приходят работать в промышленность, и их код невозможно ни читать, ни поддерживать)
1:52 у меня даже 14 секунд 🤦🏻♂️
Горд петербургскими айтишниками
Почему вк начал блокировать порнографию?((
1 лайфхак. Переходитн на плюсы, питон кринж
Кринж потому что не надо с байтами дрочиться или потому что есть четкий договор по написанию кода, а может дело в скорости? Если первое, то чего ж тогда не ниже уровнем на С или Nasm\Yasm\ и прочих assемблерах. Если 2, то странно осуждать язык за то, что он заставляет тебя писать чуть более читабельно. А если вдруг 3, то и это как-то сомнительное в среднем, на типовых задачах для которых используют питончик(пресловутый io bound), вроде как не ощущается (оценочное суждение) его заторможенность. Единственное достоинство плюсов - поднятие уровня абстракции, в угоду скорости, а разве этим самым не славен питончик, в ином случае попрошу показать, что создание ветвистых классовых структур не влияет на производительность. А вообще лучше переходить на раст и не дрочиться с препроцессором и байтиками(пусть и иметь возможность приспуститься), и при этом иметь ту же скорость выполнения программ.
С++ низкоуровневый, он не подходит для многих задач.
Ну все, бегу на питоне писать, потому что в комментариях сказали, что
c++ он слишком низкоуровневый и там мучаются с байтиками😔
Язык прекрасный, скорость - просто приятный бонус. Благодаря ооп писать проекты не так уж и сложно.
выделение памяти - то, за что ругают его, мол постоянно нужно следить. Но для этого есть деструкторы, которые сами могут
подчищать выделенную память в куче, для этого даже сделали отдельные классы с умными указателями.
И, честно говоря, очень редко мне приходилось пользоваться выделением оперативной памяти, потому что уже почти под все хотелки придумали различные контейнеры.
А никого не смутило что с факториалом что то не так, больно не правдивый?
По модулю берется ответ