Алгоритмы *

Приветствуем, Хабр.

Не секрет, что большие языковые модели и, в частности, трансформеры (GPT) серьезно повлияли на работу программиста, привели к автоматизации многих рутинных задач, значительно удешевили проверку концепций и эксперименты при разработке новых продуктов. Коренные изменения произошли не только в разработке, но и во взаимодействии пользователя с ботами, агентами, поисковыми системами. Промпт-инжиниринг буквально за полтора года превратился из искусства в ремесло, которое способен освоить и подросток. Мы хотим очертить ближайшие перспективы выхода книг из типографии и планы на обозримое будущее — на наших верфях и уже практически на стапелях готовится целый флот литературы, ориентированной на работу с искусственным интеллектом.

Мне нужен был сервис, в котором должны были работать несколько разных алгоритмов. Часть математики я помнил, часть понимал поверхностно, часть собирался восстановить по ходу работы. Чтобы быстрее получить прототип, я подключил LLM к генерации бойлерплейта, интерфейсов и первых реализаций.

Через несколько дней (говно)кода стало много — вменяемого сервиса не получилось.

Один BFS принимал map[string][]string. DFS жил на другом типе графа. В одной реализации направленность задавалась на уровне графа, в другой вытекала из того, как было записано ребро. Опции существовали, но их комбинации не образовывали понятной политики. Result types возвращали срезы и числа, однако я не мог внятно ответить, что именно они гарантируют.

Проблема была не в том, что LLM «не умеет BFS». Я попросил реализации раньше, чем сформулировал общий контракт данных. Генератор заполнил пустые места правдоподобными допущениями — которые, очевидно, не совпали в разных кусках кода.

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

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

Задача тянет на головоломку, но в мире двумерного синтаксиса у неё есть красивое решение — просто отзеркалить операцию строчкой ниже. Такой трюк напрямую моделирует обратимость вычислений из квантовой физики.

Статья как раз об этом: как освоение второго измерения помогает чисто и наглядно записывать цепочки операторов, чистить мусор и даже строить 3-битный сумматор, который выглядит как единый двумерный блок.

Цель видна только через камеру, детектор отдает рамку, дальномера нет. В какой-то момент цель уходит из кадра на три четверти секунды, и ее надо продолжать вести вслепую. Классический фильтр Калмана в этой ситуации теряет цель в 84% эпизодов. Наш трекер теряет ее в 18% и возвращает в центр кадра в 80%.

Привет! Я Арина Сокова, аналитик в Авито Подработке. Мы отвечаем за то, чтобы смены на платформе закрывались, исполнители и заказчики находили друг друга, а платформа не тратила на продвижение сервиса слишком много. В статье расскажу, что такое субсидии в Авито Подработке, и как мы перешли от ручного назначения субсидий по бизнес-правилам к автоматической системе.

Текст будет полезен аналитикам и продакт-менеджерам, которые работают с ценообразованием, субсидиями, промомеханиками и любыми задачами оптимизации бюджета при ограничениях.

Привет, читатель!

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

Всем привет! Меня зовут Алина Бабенко, я acting DS-менеджер в Авито. Наша команда занимается моделями монетизации в поиске и рекомендациях: мы оцениваем ожидаемую выручку от действий пользователей и используем её в ранжировании. В этой статье я расскажу, какие модели используем для расчёта ожидаемой выручки, как оцениваем их качество, а также зачем корректируем ставки.

Материал будет полезен дата-сайентистам и тимлидам, которые работают с монетизацией на маркетплейсах и в сервисах для объявлений.

Допустим, вы пишете программу для обработки изображений. Программа получает изображение, преобразует его в значения с плавающей запятой, выполняет обработку и сохраняет изменённые пиксели на диск в виде 8-битных цветов. Сегодня я хочу рассмотреть вопрос преобразования целых значений в значения с плавающей запятой. Существует два решения, которые на Python и NumPy выглядят так:

Стандартное деление на 255

pixels = img / 255.0
result = process(pixels)
output = np.trunc(result * 255 + 0.5)

Альтернативное деление на 256

pixels = (img + 0.5) / 256.0
result = process(pixels)
output = np.trunc(result * 256)

Я предполагаю, что в обоих случаях выходные значения ограничиваются перед окончательным преобразованием типов:

# Ограничение и преобразование в 8 бит
output_8bit = output.clip(0, 255).astype(np.uint8)

В стандартном случае целочисленный 0 соответствует 0.0, а 255 соответствует 1.0. Это работает абсолютно нормально и именно так всё реализовано в GPU. В альтернативном случае прибавляется смещение на 0,5 и деление происходит на 256, поэтому целочисленный 0 соответствует 0.5/256=0.001953125. Это неудобно, потому что код обработки изображений, например, без знания константы не сможет обнаруживать чёрные пиксели. Из‑за этого мы привязываем логику к 8-битным значениям, даже если вычисления выполняются с плавающей запятой. В стандартном решении всегда можно предполагать, что чёрный соответствует 0.0.

Однако некоторых программистов всё равно притягивает альтернативное решение. В чём дело? Чем оно им так нравится?

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

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

Перед вами шестая и заключительная часть (а вот первая, вторая, третья, четвёртая и пятая) серии статей, посвящённых информационным технологиям в авиаперевозках. Сегодня мы поговорим об изменениях, происходящих в этой сфере. Системы, построенные на базе стандарта NDC, вот уже 14 лет пытаются вытеснить традиционные GDS. Этого до сих пор, в полной мере, не произошло. У такого положения дел есть определённые политико-экономические причины. Здесь же автор расскажет о том, что он, благодаря инциденту с птицей, узнал о системах, которые вот уже много лет пытаются заменить.

Исторически в Яндекс Картинках релевантность документа оценивалась по двум сигналам: насколько запросу подходит само изображение и насколько — текст, связанный с этим изображением. Такой подход позволяет учесть контент картинки и не провалиться на визуально трудноотличимых объектах, однако он же порождает проблему: в «серой зоне», когда текстовая релевантность не сонаправлена с картиночной, становится неочевидно, как именно агрегировать сигналы в финальный скор релевантности.

Привет! Я Константин Николаев, занимаюсь внедрением нейротехнологий в Поиске по картинкам. В этой статье я расскажу, как наша команда научила модели смотреть на картинку и читать текст документа одновременно: начали с тяжёлой мультимодальной VLM ради максимального качества, а затем дистиллировали её в набор лёгких моделей — по одной под каждую стадию пайплайна. Что из этого удалось довести до realtime‑поиска с десятками тысяч запросов в секунду и как совместный анализ двух модальностей добавил 5% релевантных картинок в топ выдачи — под катом.

Все голосовые платформы решают, что человек договорил, по таймеру тишины. Я замерил, во что это выливается на живой русской речи, и получил цифру, которая меня удивила: из 1275 мс задержки перед ответом 1200 мс — это ожидание секундомера, и только 75 мс — работа самой модели.

Ниже — методика, замеры и решение, которое даёт 316 мс вместо 1200 при двух обрывах вместо тридцати восьми. Всё воспроизводимо, детектор — на правилах, без обучения и без GPU.

В естественном языке распространена ситуация, когда значение слова нельзя установить без контекста: «замок закрыли ключом», «замок окружён рвом».

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

В языке существует способ упаковать несколько значений в одно слово-омоним. В этой работе мы сознательно отказываемся от однозначности слов. Будет представлен алгоритм, сжимающий словарь русского языка в десятки и сотни раз, используя раскраску графа.

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

Продолжаю тему реверса алгоритма, ссылка на первую статью: https://habr.com/ru/articles/1064990/. В этой части доведу реверс до конца, постараюсь показать как делать не надо, почему декомпиляция хорошо, а эмуляция лучше )

p.s. Тут нет 50 минут, листинги в спойлерах повлияли, их можно не читать.

Есть кластер задач, который выглядит скучно, но кормит половину мировой экономики. «Сколько будет стоить эта квартира?» «Сколько дней займёт доставка товара получателю?» «Какое количество посетителей будет в магазине в субботу?» «Какой будет расход электричества дата‑центра за неделю?»

Выглядят эти задачи однотипно: на входе набор известных заранее данных, а на выходе одно конкретное число. Статистики и специалисты по машинному обучению называют это регрессией, а для остальных это «прогноз», с которым они работают на ежедневной основе.

Последние полтора десятка лет эти задачи решали инструменты, о которых обычный человек никогда и не слышал. К примеру, XGBoost. Устроены эти инструменты как перечень примерно из двадцати вопросов, на которые необходимо последовательно ответить. «Дорогой ли район?» «Больше трёх комнат?» и так далее. Заданные в определённом порядке, они относительно точно приводят к ответу. Работает быстро, себестоимость копеечная, принцип понятен на всех уровнях руководства.

А потом выяснилась неожиданная вещь. Языковые модели (LLM), которые обычно помогают нам писать письма и придумывать креативы, умеют делать то же самое, а иногда даже точнее.

Давайте разберёмся, почему.

Привет хабр!

Мы разрабатываем приложение для управления линейным персоналом.

Хочу рассказать об одной из самых сложных наших разработок — динамического визуального кода, который должен считываться камерой обычного смартфона в реальном времени.

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

На практике путь от первого прототипа до стабильной работы оказался гораздо сложнее. Мы успели обучить модель для object detection, столкнуться с ограничениями мобильного железа, отказаться от нейросети и почти без опыта в компьютерном зрении построить собственный real-time-пайплайн обработки кадров.

Рассматривать предметный образец под микроскопом — всё равно что пытаться увидеть концертный зал через замочную скважину: в поле зрения попадает только небольшой фрагмент, а общей картины не видно. 

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

Есть белок — рестриктаза ЭкоРИ. Она плавает в клетке, натыкается на двойную спираль ДНК и ищет конкретную последовательность из шести нуклеотидов (ГААТТЦ). Нашла — разрезает цепь ровно между первой и второй буквой. В стандартных лабораторных условиях никакой другой последовательности она не трогает. 

Прим. автора: при высоком содержании глицерина или нестандартном pH у ЭкоРИ проявляется так называемая звёздная активность — фермент начинает резать похожие, но не идентичные последовательности. Это известный артефакт, с которым борются в любом молекулярном протоколе.

Форма активного центра белка оптимизирована именно под эти шесть нуклеотидов — точное структурное соответствие обеспечивает во много раз большее сродство, чем к любой другой комбинации. Биохимики называют это специфичностью.

Леонард Эдлман — тот самый, чья буква «А» стоит в конце аббревиатуры RSA. Профессор Университета Южной Калифорнии, в 2002 году получил премию Тьюринга — высшую награду в информатике. В 1993 году, читая учебник Уотсона по молекулярной биологии, он задумался — а если фермент узнаёт последовательность и выполняет действие, это ведь и есть вычисление. Спустя год опубликовал эксперимент.

В этой статье последовательно разобран полный цикл обновления React: от Virtual DOM до внутреннего устройства Fiber Reconciler.

хочу представить вам свой очень быстрый алгоритм нахождения простых делителей огромных составных чисел. Однажды на уроке математики мне нужно было найти делители какого-то числа. Раз уж "лень — двигатель прогресса", я решил поручить эту задачу компьютеру. Но простая программа на Python по перебору до корня мне показалась скучной, и тогда я решил найти более интересный способ.