Алгоритмы *

Я думаю, что многим программистам по мере их профессионального роста и наращивания стека технологий сильно не хватает времени. Это касается как технических аспектов (например, проектирование архитектуры или масштабируемость приложений), так и общей организации работы. Даже если не учитывать все эти нюансы, вход в новый проект требует значительных временных затрат на изучение теории и создание портфолио, особенно для стажеров и джуниоров.

По мере вхождения в проект, изучая документацию и инфраструктуру, я начал чаще сталкиваться с вопросами, связанными с ускорением алгоритмов и потреблением памяти, я также интересовался прокачкой хард-скиллов. Если раньше мне было достаточно базовых возможностей LINQ, то с увеличением объёмов данных из внешних источников я задумался о рефакторинге и смене подходов к разработке.

Находясь на позиции junior, я столкнулся с необходимостью оптимизации кода – и после частого откладывания этого вопроса на потом мне всё же пришлось поднять его снова. Сегодня я бы хотел поделиться своим опытом на эту тему.

Давненько я ничего не публиковал на Хабре — пора это исправлять.

В этот раз хочу поделиться темой, которая кажется простой, но на деле вызывает интерес у многих разработчиков и системных администраторов: как создать свою легковесную систему планирования задач на Python. Что-то вроде мини-аналога cron, но под свои задачи и со своими фишками.

Ведь часто бывает так: хочется, чтобы какие-то проверки или скрипты запускались в определённое время — например, в обеденный перерыв у сотрудников можно поставить автоматическую проверку всех машин на наличие вредоносного ПО. Или наоборот — распределить рутинные проверки так, чтобы они не мешали основной работе.

Хочу поделиться знанием, которое не является секретом, в каких-то курсах по алгоритмам оно наверняка дается, но нагуглить его совсем не просто. Поэтому пусть будет.

Алгоритм Дейкстры можно обобщить на произвольную функцию длины пути, если только она удовлетворяет трем условиям:

Монотонность. При добавлении ребра к пути, его длина не уменьшается.

Консистентность. При добавлении одинакового ребра к путям одинаковой длины, получившиеся новые пути имеют одинаковую длину.

Оптимальность префикса. Если к двум путям приписать одинаковое ребро, то кратчайший путь останется кратчайшим.

Под катом я привожу доказательство корректности обобщенного алгоритма и показываю, как его применить в задаче на литкоде: Trapping rain water II.

В этой статье я расскажу о стеке и задачах в которых он применяется. Включая задачу с заключительного этапа Всероссийской олимпиады школьников по информатике 2025 года.

Доброго времени суток.

В качестве первой статьи решил выбрать разбор реализации отечественного шифра «кузнечик». Постараюсь объяснить сложные вещи простым языком.

В качестве рабочего примера моя реализация на C.

Привет! Меня зовут Дмитрий Бандурин, я заместитель директора департамента биллинговых решений в компании «СИГМА». Моя команда регулярно выполняет нетривиальные задачи для стабильной работы высоконагруженных систем. Сегодня расскажу, как мы переработали логику обработки пакетных процессов в нашей системе массовых операций, на примере расчета дебиторской задолженности. Нам было необходимо, чтобы она справлялась с возрастающим объемом данных — и всё это в жестких временных рамках и в условиях многопоточности.

И это решит 95% проблем типичного стартапа. Как-то так повелось, что по всему СНГ и его окрестностям на работу набирают зумеров с колоссальным опытом в три года, и они начинают создавать идеальные архитектуры. Да, каждый из вас, как только получает возможность взять на себя хоть малейшую ответственность, сразу вспоминает все прочитанные и не прочитанные книги и пилит свою уникальную архитектуру, непохожую ни на что.

Зачем программисту алгоритмы?

Многие компании, нанимающие программистов, требуют от них знания алгоритмов. Некоторые даже устраивают отдельное собеседование по алгоритмам, зачастую весьма нешуточное.

Однако сами программисты нередко удивляются, зачем всё это? Действительно, работа наших коллег часто заключается в поиске и устранении ошибок в залежах legacy кода. Какие уж там алгоритмы? Даже те, кому посчастливилось участвовать в новом проекте знают, что зачастую новый проект состоит на 80% из чужого, уже кем-то написанного и найденного на просторах гитхаба кода, а новый код - это, по сути, клей и обёртки, которые позволяют склеить эти уже готовые запчасти между собой, чтобы получить заданный продукт.

Сегодня я прочитал на Хабре статью о подготовке к алгоритмическому собеседованию в Яндексе. Видно, что ребята относятся к делу всерьёз. Однако на вопрос, зачем всё таки это нужно, статья отвечает в том духе, что алгоритмическая подготовка показывает полезную готовность кандидата поотжиматься (отмечу при этом, что это не мнение Яндекса, а личное мнение человека, получившего этот опыт с обеих сторон - и кандидата и интервьювера).

Однако всё же, действительно ли основная польза алгоритмической подготовки сводится к тому, чтобы продемонстрировать работодателю свою сообразительность и готовность потратить время жизни на подготовку к собеседованиям, а в целом она не слишком полезна для нормального рабочего процесса? Или всё же алгоритмы нужны?

❯ Механизм согласования

В моих предыдущих статьях (1, 2) я подробно рассматривал, как работает React.memo, а также делился более эффективными подходами к оптимизации производительности с помощью компоновки. Однако для глубокого понимания работы React необходимо разобраться в основном механизме, лежащем в основе всех этих оптимизаций – алгоритме согласования (reconciliation).

Согласование – это процесс, в результате которого React приводит DOM в соответствие с деревом компонентов. Именно этот механизм позволяет реализовать декларативный подход к программированию на React: вы формулируете свои намерения, а React самостоятельно определяет, как выполнить эти намерения наилучшим образом и с наименьшими затратами.

В конце января мне написал рекрутер из Яндекса с предложением пройти алгоритмическое собеседование. На тот момент у меня было решено всего 55 задач на LeetCode, из которых 50 — по SQL. Знания в области алгоритмов были практически на нуле.

Я решил взять паузу на два месяца и сосредоточиться на подготовке. В конце марта я успешно прошёл первый этап. О том, как прошли остальные этапы, расскажу ближе к концу статьи.

В этой статье я хочу поделиться своим опытом подготовки: как я готовился, какие стратегии использовал и что в итоге действительно помогло.

Может кому-то это будет интересно, даст возможность лучше подготовиться; или наоборот кто-то примет решение не участвовать.

Коротко о себе: 41 год, senior software developer, стаж > 20 лет. Однако, как я понял, эти собесы все равно для всех одинаковые, так чтоб все написанное актуально и для молодежи.

Итак, угораздило меня согласиться на т. н. «Weekend Offer на позицию разработчика на Kotlin». Вообще‑то мне больше нравится Scala, и опыта по ней гораздо больше, но рекрутерша была сильно настойчива, и я решил обновить экспиренс, а возможно, и прибавку в деньгах. И вот что было дальше.

Как и обещали, публикуем вторую часть перевода статьи — и она ещё более драматичная и насыщенная событиями.

Вас ждёт продолжение истории: стремительное развитие новых ИИ-моделей, противостояние государств в гонке ИИ-вооружений и два возможных сценария будущего — один, в котором человечество осознанно ограничивает рост искусственного интеллекта ради общей безопасности, и другой, в котором даёт ИИ полную свободу, со всеми вытекающими последствиями. Чем всё это заканчивается — читайте ниже.

Приветствую! Меня зовут Егор Ершов, я руковожу группой «Цветовая вычислительная фотография» в AIRI, а также заведую сектором репродукции и синтеза цвета ИППИ РАН. Область моих научных интересов касается способов регистрации и обработки изображений, что в той или иной степени касается любого человека, кто хоть раз пользовался камерой, монитором или проектором.

Вычислительная фотография лежит на стыке сразу нескольких дисциплин: физики, физиологии, компьютерных наук. Из‑за этого в ней ещё много сложного, но вместе с тем интересного и неизвестного. Я подготовил полноценный курс по алгоритмам вычислительной фотографии для МФТИ и ВШЭ, но мне также хотелось бы поделиться со всеми желающими его материалами в текстовом формате.

Этот курс посвящен как феномену цвета, механизмам его восприятия, исследованию зрительной системы человека, так и непосредственно алгоритмам цветовой вычислительной фотографии. Но в этой статье я бы хотел в общих чертах обрисовать проблему регистрации изображений, а также дать введение в теорию цвета, которая потребуется в дальнейших частях.

Система и алгоритм оповещения о ракетной опасности с использованием Яндекс Станций. Пользователь вручную создает сценарии для устройств «Умного дома Яндекса» с использованием «Лампочки», которая включается при сигнале о РО и выключается при сигнале ОТБОЙ.

Стэк: Python, telethon, aiogram 3.x, mqtt, postgresql.

Наверное, я очень опоздал с изучением CUDA. До недавнего времени даже не знал, что CUDA — это просто C++ с небольшими добавками. Если бы я знал, что изучение её пойдёт как по маслу, я бы столько не медлил. Но, если у вас есть багаж привычек C++, то код на CUDA у вас будет получаться низкокачественным. Поэтому расскажу вам о некоторых уроках, изученных на практике — возможно, мой опыт поможет вам ускорить код.

Хеш-таблица(мапа) — одна из самых популярных структур данных, потому что поиск по ключу происходит за O(1). Причем ключ может быть любым любым типом, элементы которого можно сравнивать (Comparable Trait).

Я столкнулся с тем, что мапа не такая быстрая по бенчмаркам на языке GO, хотя теоретическая сложность алгоритма О(1).

Давайте рассмотрим следующую задачу и способы ее решения.

Привет, Хабр!

Когда-то я писал веб-приложения. Решал задачи бизнеса, деплой в прод, REST, тесты, метрики, кубики. Всё было нормально. Но в какой-то момент мне стало… скучно.

Да, задачи были интересными. Команда — отличной. Но где-то внутри появилась пустота. Хотелось делать что-то настоящее. Осязаемое. Что-то, где за твоим кодом — больше, чем UI и API. Хотелось влиять на реальный мир.

Так я попал в мир электропривода.

Локализация с помощью NDT

Посвящается всем тем, кто хочет узнать, как работает алгоритм, не читая диссер на английском на 200 страниц [1].

Дисклеймер: некоторые определения или заявления могут быть не точными, для получения самой точной информации обратитесь к серьезным статьям.

Расскажу о том, как решал одну из наиболее интересных задач в разминке Яндекс Алгоритмы 2023 г. Интересной я называю ее потому, что: 1) решал я кратно дольше, чем предыдущие 6 задач из разминки вместе взятые; 2) именно в этой задаче я проникся мощью префиксных сумм, и применением их для двумерных массивов.

И так задача:

Кролики очень любопытны. Они любят изучать геометрию, бегая по грядкам. Наш кролик как раз такой. Сегодня он решил изучить новую фигуру — квадрат.

Кролик бегает по грядке — клеточному полю N × M клеток. В некоторых из них посеяны морковки, в некоторых нет.

Помогите кролику найти сторону квадрата наибольшей площади, заполненного морковками полностью.

Формат ввода

В первой строке даны два натуральных числа N и M ( 1 ≤ N, M ≤ 1000). Далее в N строках расположено по M чисел, разделенных пробелами (число равно 0, если в клетке нет морковки или 1, если есть).

Формат вывода

Выведите одно число — сторону наибольшего квадрата, заполненного морковками.

На хабре уже пару раз упоминался дизеринг, но в довольно узком ключе. Здесь, я хоть и буду делать упор на применение дизеринга в графике, я хочу продемонстрировать его недооценённость, из-за чего его снова и снова переизобретают.