Алгоритмы *

Алгоритм MinHash позволяет транслировать разряжённые (sparse) бинарные векторы большой размерности в целочисленные векторы многократно меньшей размерности с сохранением информации, позволяющей оценить похожесть исходных векторов.

С алгоритмом SimHash его объединяет то, что оба они просто потрясающе красивы! Настолько, что вот прям хочется про них рассказать.

Про SimHash в следующий раз, а вот если интересно чем же мне так понравился MinHash, добро пожаловать под кат!

Всем привет! Меня зовут Гриша Дядиченко, я технический директор и основатель White Label Games. Уже больше десяти лет работаю с компьютерной графикой, AR/VR и компьютерным зрением — в основном это заказная разработка, плюс собственные прототипы по вечерам, до которых дотягиваются руки.

Сталкивались ли вы с ситуацией, когда у вас в игре уже двести юнитов, а FPS почему-то уехал, хотя визуально на сцене ничего особенного нет? Или с тем, что хочется сделать настоящую орду — плотную, с реакцией на стрельбу, обтекающую укрытия — а получается стайка, которая либо разбегается как пыль, либо слипается в один шарик и едет им по всей карте?

Чтож, давайте по порядку. Как это устроено у настоящих скворцов над Римом и причём тут код, какие именно три правила Рейнольдса и как они балансируются весами, как сетка побеждает O(N²) и где она сама ломается, что такое ORCA и как она разруливает встречные потоки в коридоре, как steering behaviors дают агенту цель и обход препятствий, и что лежит под капотом конкретных шипнутых игр от AC Unity до World War Z.

Продолжение. Начало здесь. Предыдущая часть. Репозиторий с кодом - на гитхабе.

(Сокращения: НАМ - нормальные алгорифмы Маркова, КТ - компайл-тайм, РТ - рантайм).

Следующая неприятность, которая нас ждёт, - это циклы, которые в КТ вовсе не циклы. Нам надо как-то научиться бегать по правилам, из которых состоит НАМ-программа.

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

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

Оказалось, что классика вроде «Съешь ещё этих мягких французских булок» не подходит — в моём наборе каждая буква была только один раз. А те панграммы, где буквы не повторяются (можно найти, например, у Лебедева в «Ководстве») — «Эй, жлоб! Где туз? Прячь юных съёмщиц в шкаф.» или «— Любя, съешь щипцы, — вздохнёт мэр, — кайф жгуч» — они, скажем так, на любителя. Слишком много восклицаний, междометий и прямой речи. Хотелось чего-то более пристойное и связное.

У меня получилось найти следующую панграмму:

«Съев мяч, щипцы, эльф‑конюх ждёт груз шайб»

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

Я хотел просто пожарить кесадилью. В холодильнике лежали зеленые оливки (солено-кислые), сулугуни и фарш, а на полке консервированная кукуруза. И вот стою я над сковородкой и думаю: а оливки с кукурузой вообще сочетаются? А сулугуни не пересолит блюдо вместе с оливками? Сколько чего вообще класть?

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

Стоит открыть исходники любого современного игрового движка – неважно, это C++-рендер, сделанный на коленке, или какая-нибудь гигантская экосистема вроде Unity или Unreal Engine – вы первым делом натыкаетесь на одни и те же знакомые сущности. Все вокруг живет в Vector3: координаты, направления движения, точки столкновений. Каждая частица указывает, куда она смотрит, с помощью Quaternion. А если требуется что-то покруче – переносить и одновременно крутить объект, то Matrix4x4. Это уже как стандарт де-факто: кто пробовал крутить объекты руками, тот точно переписывал код с этими структурами. Ещё конечно же отдельно существуют лучи, плоскости, сферы, bounding boxes, а между ними тянутся километры функций вроде dot(), cross(), normalize(), lookAt(), inverse(), project() и бесконечных преобразований типов.

Привыкаешь к этому быстро. Нам кажется совершенно естественным тасовать эти типы между собой – уж слишком давно так делается по всей индустрии. Но стоит лишь чуток задуматься, и начинает прорезаться легкий когнитивный диссонанс: выходит, вся наша графика построена на наборах несовместимых между собой математических запчастей. Для одного действия нам нужен один тип данных, для второго – другой, а пересчитать простое столкновение луча со сферой или плоскостью без пятого велосипеда никак не получается. Вроде бы всё работает и даже неплохо работает… Но ощущение конструктора из костылей не отпускает.

И самое интересное заключается в том, что так было не обязательно.

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

Рассказываем, как из идеи «собрать меню на неделю» получилась задача оптимизации: КБЖУ, бюджет, целые упаковки, остатки в холодильнике, цены магазинов и план готовки.

Внутри — почему схема «рецепты → список покупок» быстро ломается, зачем понадобились greedy, simulated annealing и MIP, и почему список покупок оказался почти отдельным продуктом.

Принцип «бритвы Оккама» — краеугольный камень социальных наук. Для экономистов-финансистов он почти аксиома. Принцип назван в честь Уильяма Оккама, монаха XIV века. Согласно ему, самое простое объяснение любого явления — лучшее.

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

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

Пришло время запутаться и распутаться со строками в компайл-тайме... и с зависимыми типами.

Основные требования к КТ-строкам - чтобы можно было использовать их в качестве параметров шаблона, и чтобы можно было писать constexpr-функции, логика и типы которых зависят от значений аргументов. Это не очень сложно, но может быть неочевидно.

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

Для этого мы сравнили два способа «подружить» ИИ‑агента с внутренними API — MCP и CLI + Skill. Взяли гипотезу из внешних исследований, собрали бенчмарк на 14 сценариях и двух моделях, прогнали больше 400 запросов на реальных внутренних инструментах. И в какой‑то момент всё, что работало, сломалось — и это оказалось самым интересным. Пришлось разбираться почему.

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

(Продолжение. См. первую часть, где мы научились кодить на марковских алгорифмах "на бумажке").

Какие неприятности нас ждут?

Я уже сказал, что реализация НАМ в КТ - это задача со звёздочкой.

Что нам придётся героически преодолеть, и о чём понятно прямо на старте?

Руководство по разработке своей версии vsnprintf для целочисленных значений для увлекающихся osdev. Проходит стандартные тесты от gcc

В июле 2024 года французская компания Kyutai опубликовала речевую модель Moshi с нейронным аудиокодеком Mimi. Это был первый в мире голосовой end-to-end AI с открытыми исходниками, способный вести диалог в реальном времени и свободный для использования всеми желающими, демо.

Вместо прямого предсказания сэмплов аудиокодек работает в три этапа:

1. Токенизация звука.

2. Предсказание следующих токенов в LLM.

3. Восстановление оригинала.

Какие программы могут быть по-настоящему достойны хаба "ненормальное программирование"?

Конечно же, программы для нормальных марковских алгорифмов! (Далее - НАМ).

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

Поэтому поставим задачу со звёздочкой: научимся писать для НАМ в компайл-тайме С++!

Для начала, посмотрим: что такое НАМ и что на них вообще можно делать.

# Как мы четыре раза неправильно диагностировали зависание на джобе 281 339

Несколько месяцев назад я писал, [как мы четыре раза неправильно чинили мерцание](https://habr.com/ru/articles/1042962/) при рендеринге 4,4 миллиона полигонов. Тогда казалось, что это рекорд: месяц блужданий, четыре отброшенных подхода, решение на неделю. Эта история хуже. Баг пережил четыре диагноза подряд, два из которых мы успели «подтвердить числами», получил по дороге три работающих фикса от несуществующих причин - и в итоге оказался файлом, который лежал на рабочем столе.

Напомню контекст: мы небольшой командой пишем на Rust + Vulkan редактор топологий интегральных схем + верификатор (DRC/LVS/Antenna/PEX) с прицелом на российский рынок. Команда - три человека, я в роли CTO направляю архитектуру и принимаю основные решения. В том числе неверные, о которых ниже. Тестовый основной дизайн всё тот же - Caravel SkyWater SKY130: 4,4 миллиона полигонов, 1014 уникальных ячеек, 22 уровня иерархии, 278 МБ GDS (недавно воспользовались прекрасным проектом [TinyTapeout]( https://github.com/TinyTapeout/) - для прогона на различных gds)

К моменту этой истории мы только что закончили перф-кампанию по паразитной экстракции (PEX). Если коротко: чтобы посчитать ёмкости, нужно сначала собрать цепи - обойти иерархию чипа BFS-ом от каждого "сида" (точки на цепи устройства) и выяснить, какие фигуры электрически связаны. На Caravel это 537 748 сидов. Кампания ужала полный холодный прогон с 962 секунд до 70: пространственный грид вместо квадратичного перебора пар, параллельные трейсы на 14 потоках, кеш результата. Все гейты бит-идентичности зелёные, CLI летает.

10 мая, в возрасте 86 лет умер Джим Саймонс, создатель Renaissance Technologies — одного из самых прибыльных хедж-фондов в истории. Его состояние оценивается в $31,4 млрд, 55-е место в рейтинге Forbes. Аналитики Уолл-стрит до сих пор не смогли разгадать главный секрет успеха самого прибыльного фонда Саймонса — Medallion.

Для создателей стратегий и алготрейдеров это не просто новость. Это повод задать вопрос: что именно делал Medallion и можно ли из этого извлечь практические уроки для собственных систем?

Приветствую читатель!

Для тех кто со мной впервые вот оглавление:

Часть 1

Часть 2

Часть 3

Код лежит тут

Подразумевается что читатель знаком с архитектурой аллокатора из части 3 и понимает алгоритм неявного списка свободных блоков который был освещен в части 1

Аллокатор работает стабильно, все тесты зеленые, включая тесты на стабильность. И следующим шагом логично бы реализовать перегрузки new и delete для abi, но вот незадача: там есть версии принимающие дополнительный аргумент, а именно выравнивание. Эту фичу я реализовать как раз забыл. В архитектуре которая рассматривается в предыдущей статье это оказалось простой, но интересной задачей. Ее мы и обсудим ниже.

Решение потребовало реализации функции mem_malloc_aligned которая выделит бОльший кусок памяти с учетом запрошенного выравнивания что бы мы там точно нашли правильно выровненный адрес.

Но что если адрес указателя из mem_malloc_aligned не совпадает с адресом указателя который вернул mem_malloc? Что делать в mem_free? Что делать в mem_realloc? Как мне работать с указателем перед которым не хедера?

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

Но как мне отличить offset от header? Я решил добавить magic number в хедер и футер увеличив тем самым размер оверхеда в 2 раза и раз уж от него считалось внутреннее выравнивание блоков памяти в аллокаторе и минимальный размер блока, то теперь минимальный размер блока стал 32 байта, а с оверхедом все 64. Теперь можно просто проверять magic number и если он не совпадает, то интерпретировать число на месте хедера как смещение до payload блока который вернул mem_malloc и далее получив на него указатель работать с блоком стандартным образом.

У меня было множество вело фар и всегда меня напрягало то, что фара включается практически мгновенно.

Глаза даже не успевают приспособиться и это доставляет существенный дискомфорт.

В связи с этим я принял решение разработать свою безопасную вело фару.