Алгоритмы *

Привет, Хабр! На связи Максим Кацал, руководитель направления автоматизированного тестирования в РТЛабс.

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

В статье расскажу, как мы научились генерировать тесты прямо из JSON-схемы услуги. JUnit 5 + @TestFactory + рекурсивный обход графа маршрутов. Фреймворк, который сам прокладывает путь пользователя по приложению-конструктору, а потом проигрывает его в браузере.

Ниже раскрою архитектуру, код, подводные камни, опишу плюсы и минусы такого подхода.

Полгода назад я начал писать in-memory базу с векторным поиском на Go: RESP-протокол, HNSW-индекс, WAL, многопоточность. Рассказываю, что из этого вышло: как я мерил производительность и на каких граблях стоял, что реально ускоряет векторный поиск, а что нет. Все цифры воспроизводимы, код открыт.

Децентрализованно планируем эвакуацию раненых: под огнем, в бардаке, с постоянно меняющимся путем отхода и нервным поиском плана Б, если..., вернее, когда.

Привет, я Егор The Hawk, и я, тоже, своего рода, разработчик. Надо успеть написать про работу, пока не завершил карьеру. Постараюсь кратко. Геймдевелоперам зайдет.

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

Краткая история внешней памяти и пять функций листа бумаги

Не претендуя на гениальность задался простым, на первый взгляд, вопросом: "На моем столе в 2026г всегда лежит лист черновика и пара карандашей?" Ответ оказался не таким коротким, как ожидал. Приглашаю к прочтению!

Архивация - старая, давно изученная тема ...или нет?

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

Заодно напишем простой нейроархиватор работающий через инференс любой нейронки.

В прошлом году я уже рассказывал об AVI (Aligned/Agreement Validation Interface) — концепции внешнего, гибкого и независимого от модели фильтра, который работает как умный файрвол для LLM: отбивает промпт-атаки на входе, проверяет ответы модели на токсичность, этичность и нарушение закона — на выходе. Недавно мы доработали свою концепцию с точки зрения архитектуры, реализовали и выложили на GitHub рабочий сервис на Python и FastAPI: входной и выходной фильтры, RAG-модуль, докер-сборку с мониторингом (Prometheus, Grafana, Jaeger), а также инструментарий для воспроизведения экспериментов на FinanceBench. 

Под катом расскажу, к какой архитектуре системы мы пришли, как сделали так, чтобы новые правила для фильтрации можно было добавлять одной фразой на естественном языке, как AVI показал себя в тестах и как помогает экономить на обучении ИИ-моделей. 

А по-научному и подробно все описано в журнале MDPI.Electronics (на английском).  

Хорошая рекомендательная система быстро учится угадывать, что вы положите в корзину. И чем точнее она угадывает, тем реже показывает что‑то незнакомое: ведь выгоднее предлагать проверенное. Со временем система замыкается на привычках человека и перестаёт показывать ему хоть что‑то за их пределами.

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

Меня зовут Рамиль Боярченков, я занимаюсь машинным обучением в команде Яндекс Лавки. Расскажу, как мы собрали механизм, который подмешивает незнакомые товары персонально — тем, кто к ним расположен, — и с какой вероятностью это делать для каждого пользователя. По пути разберу, как мы калибровали «агрессивность» exploration и что получилось в итоге.

Дисклеймер: я не нефтехимик и не эксперт по моторам. Я embedded-разработчик, который в будни отлаживает встраиваемые системы, а по выходным развлекается с собственной машиной. Всё, что ниже, является компиляцией учебников по теории ДВС, технических регламентов и личного накопленного опыта - вдохновлением послужила актуальная статья ресурса про устройство ДВС. Напугала обложка? Она напугала и меня, но именно с друзьями-роботами хотелось создать нечто для привлечения внимания к действительно важной проблеме.

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

Как разогнать copy_if на NEON в 30+ раз без единой ветки в горячем цикле — эмулируем compress инструкцию, которой в NEON нет, через table lookup и немного битовой магии.

Клиент - производитель строительных материалов.

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

В момент погрузки, вилочный погрузчик заносит паллету шириной 2,40 метра, а она упирается в “неучтенный” выступ внутри кузова. Цена такой ошибки — повреждённый груз, развёрнутая на КПП машина, простой ворот, сорванный график отгрузки. 

Решение заказчика: поставить человека на осмотр: сотрудник заглядывает в кузов и по визуальному осмотру решает, грузить фуру или разворачивать. Это медленно, субъективно, не масштабируется, а отказы по геометрии кузова составляют заметную долю разворотов.

Задача, которую решала наша команда: автоматизировать осмотр кузова перед погрузкой. Убрать сотрудника из точки принятия решения и выдавать решение “грузить / не грузить” на основании математических расчетов и реальной геометрии.

Планка задана высокая. Нужно замерять сразу три габарита: 

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

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

Начнем с того, что фундаментальные законы физики не только не запрещают жизнь, но и крайне её поддерживают в некоторых условиях. Жизнь - вещь упорядоченная и по умолчанию она распадается, однако размножается она в основном там, где есть условия для восстановления собственной структуры (обеспечены питание и прочие аспекты метаболизма). Таким образом, печально известный и демотивирующий многих второй закон термодинамики на самом деле скорее жизнеутверждающая вещь. Репликация, основа жизни с точки зрения физических процессов, стабильна во времени и жизнь как форма материи очень устойчива. Трудно представить себе сценарий, в котором жизнь полностью вымрет. Даже для вымирания человечества надо так сильно постараться, что никто стараться не будет.

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

Поэтому я поискал по Zhihu и прошёлся примерно по всем рассказам о собеседованиях, связанным с обучением с подкреплением (reinforcement learning), сопоставил их со свежими обсуждениями и собственными наблюдениями, а затем подготовил из этого выжимку на 35 самых интересных вопросов. Считайте получившееся своего рода бенчмарком для собеседований по RL.

Задача широко знакома в узких кругах: наш каталог товаров встречается с каталогом контрагента — по сути одни и те же позиции, но названы по-разному. Надо найти совпадения и предоставить коллегам список подходящих наших артикулов для каждой их позиции.

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

Range minimum query – это классическая задача, в этой заметке решаем статический вариант. Есть массив ; нужно построить структуру данных, которая умеет быстро находить минимум и его позицию на произвольном интервале . Я собрал несколько практических наработок и сделал из них два очень компактных и быстрых варианта:

вариант с дополнительных бит, которому иногда нужно обращаться к исходному массиву;

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

Обе реализации очень быстры на практике: на случайных запросах по массиву размера элементов они работают в среднем за 20–30 нс на запрос.

Для ориентира: туториал Codeforces по блочному RMQ описывает структуру, которая отрабатывает запрос за 100 нс для массивов длины с 32-битными целыми числами, при этом используя дополнительных бит.

Доброго утречка. Прогреемся?

Мое мнение не отражает позицию какой бы то ни было компании. Все совпадения с вашими нанимающими менеджерами случайны. Мой бывший Director Title в одном из топ-трех русскоговорящих бигтехов никакого отношения к высказанному не имеет и совпадения с ним тоже случайны. Кто захочет — при желании найдет, где и чем я занимался последние 10 лет и почему мое мнение имеет ценность.

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

┼┼┼┼┼┼┼┼┼▄▀▀▀▄▄▄▄▄▄▄▀▀▀▄┼┼┼┼┼┼┼┼
┼┼┼┼┼┼┼┼┼█▒▒░░░░░░░░░▒▒█┼┼┼┼┼┼┼┼
┼┼┼┼┼┼┼┼┼┼█░░█░░░░░█░░█┼┼┼┼┼┼┼┼┼
┼┼┼┼┼┼─▄▄──█░░░▀█▀░░░█──▄▄─┼┼┼┼┼
┼┼┼┼┼┼█░░█─▀▄░░░░░░░▄▀─█░░█┼┼┼┼┼
┼┼┼██░██░████░██░░░██░░░█████┼┼┼
┼┼┼██▄██░██▄▄░██░░░██░░░██░██┼┼┼
┼┼┼██▀██░██▀▀░██░░░██░░░██░██┼┼┼
┼┼┼██░██░████░████░████░█████┼┼┼

Для строительства компиляторов, нам нужны начала математики. Из них, как мы убедимся, проистекает добрая половина понимания и всех наших работ.
В частности, без начал не понять лямбда-исчисление Чёрча, которое мы применим на этапе работы с AST. Рассмотрим элементы дискретной математики с примерами на С, JavaScript, SQL.

Раньше построение KNN-индекса было самым медленным этапом при сохранении и слиянии чанков в таблицах с векторными атрибутами. Начиная с v27.1.5 , Manticore может задействовать несколько ядер CPU при сохранении чанков, слияниях через OPTIMIZE, авто-оптимизации и ALTER TABLE ... REBUILD KNN. На 16-ядерном Ryzen 9 5950X построение KNN-индекса для 1 миллиона 1536-мерных векторов сократилось с 8 минут до 39 секунд.

Что такое ANSI коды и как их обрабатывает терминал? Зачем нужны эмуляторы терминала? Как отформатировать вывод в PowerShell из AutoHotkey? Разбираемся в этой статье.