Алгоритмы *

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

После переезда я искал булочную на Яндекс Картах и наткнулся на отзыв, начинающийся с фразы «да вот хороший вариант ответа».

Из этого вырос ReviewScope, инструмент для поиска аномалий, повторяющихся текстов и необычных закономерностей в отзывах.

Расскажу, как устроены embeddings, графы совпадений и взвешенный рейтинг, какие ошибки пришлось исправлять и что показала проверка на 21 тысяче настоящих отзывов.

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

MP3 128 кбит/с обрезал всё выше 16,7 кГц, MP3 320 дошёл до 20,1 кГц. После десяти пересохранений MP3 128 потерял больше 10 дБ. FLAC после повторного сжатия совпал с оригиналом до бита. Под катом пять замеров с графиками, слепой тест для своих ушей и таблица, какой формат для чего брать.

Почему ручное разбиение задач оказалось быстрее parallel().collect() в большинстве наших тестов.

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

Меня зовут Юрий, и уже десять лет я разрабатываю The Great Tribes — пошаговую 4X-стратегию, в которой игроку предстоит провести свою цивилизацию от первобытных племён до космической эпохи.

Игра создаётся на Java с использованием LWJGL и собственного игрового движка. Мы не используем Unity или Unreal Engine: за годы разработки у проекта сформировались собственная архитектура, система процедурной генерации мира и довольно специфические требования к обработке больших карт.

Сегодня хочу рассказать об одной небольшой, но интересной оптимизации.

Мы решили ускорить генерацию природных ресурсов, написали три реализации одного алгоритма и протестировали их на трёх компьютерах с процессорами AMD Ryzen.

Результаты оказались любопытными: более компактный вариант с parallel().collect() в большинстве измерений уступил реализации с ручным разбиением массива на части.

Но обо всём по порядку.

Сигнал изменился - как найти связанные эффекты и удалить известную связь? Сравниваю четыре структуры графа signal - effect по стоимости операций и памяти, а затем - в локальных замерах на V8. Почему одинаковая O(1) не означает одинаковое время?

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

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

В одной из предыдущих статей, уже описывал вычисление sin(x)/cos(x) с применением разложения в ряд Фурье с фиксированной точкой. Вычисление тригонометрических функций, в моем случае занимало порядка 125-130 тактов на пару (sin+cos) на процессорном ядре Cortex M7 (STM32H750). При этом, код компилировался для архитектуры Cortex M3. Точность sin/cos просчитанного таким образом составила менее 1.5LSB. Google посчитал ее как 1.2-1.3LSB, с минимальной дисперсией. Это уже дало динамический диапазон ~183dB. Для сравнения, полный динамический диапазон человеческого уха 120dB от болевого порога до шелеста листвы. А динамически диапазон звука который человек слышит одновременно порядка 40-60dB. Несколько позже поясню для чего приведено сравнение.

В общем и целом такого динамического диапазона и скорости уже достаточно чтобы производить операцию квадратурной свертки сигнала с частотой дискретизации до 450-500KHz. Кстати, на STM32F103C8T6, это заняло бы ~1.8uS на квадратурный отсчет. Т.е. с отключенными прерываниями процессор бы успел выполнить расчет одного бина честного преобразования Фурье в реальном времени. Это эквивалентно квадратурной демодуляцию на одной произвольной поднесущей до частоты 250КГц (хотя лучше брать Fsample/4 ), что позволяет работать с полосой до 125КГц, на простом контроллере в реальном времени.

Однако, этого мало для полноценной обработки сигналов. И тут я задумался. Как можно значительно повысить скорость работы и почти не потерять в точности? Первое что сделал,- разбил преобразование на блоки, фаза которых непрерывна. Это позволило работать с блоками отсчетов, которые, затем можно суммировать скользящим окном со сложностью O(1). Это привело к эффекту квадратурной демодуляции сигнала и без повышения сложности позволяло работать с малыми временными сдвигами. Фактически пришел к поблочной корреляция. Нечто вроде временного Rack-приема.

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

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

В стратегиях у ботов обычно есть обычно очень простая задача пройти через какие-нибудь ворота-узкое место, обойти стену и оказаться во дворе, и пока у нас один солдат, который идёт по пустой карте, никакой особой проблемы не возникает. А стоит вам добавить на карту десять, пятьдесят, сто, двести солдат и одни ворота, через которые физически способны одновременно протиснуться всего несколько юнитов, как выясняется они этого не делают, хотя алгоритме поиска пути (вроде A*) прекрасно отработал. Отработал, то отработал, а солдатики на месте тупят, и выясняется что мы пытаемся заставить его решать задачу, на которую он не рассчитан.

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

В предыдущей статье «Как я собирал ERP-контур из 5 продуктов для строительной компании» я рассказывал об автоматизации учёта и взаимодействия систем. Однако за любыми данными в ERP стоит физический объект: монолит, конструкции, инженерные сети и выполненные работы. Каким образом связать то, что происходит на стройплощадке, с тем, что мы видим в документах и информационных системах ?

Привет, Хабр! Я руководитель группы экспериментальных клиентов Kokoc Performance (входит в Kokoc Group). Мы в Kokoc Group занимаемся продвижением в генеративных поисковых системах. Хочу поделиться кейсом B2B-клиента из рынка корпоративного обучения. Расскажу подробно о замерах, кластеризации, смысловых профилях бренда, внешних площадках и специфике статей-рейтингов и, конечно, о результатах. Кейс будет полезен тем, кто занимается SEO, контентом, B2B-маркетингом, GEO и AEO. 

Битовые массивы кажутся экзотической структурой данных, которую применяют только опытные учёные мужи в специфичных сферах? Не всегда!

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

Под катом — эволюция от классических битовых массивов до современных сжатых форматов и реальный бизнес‑кейс их прикладного применения.

5 октября американские исследователи Вирджиния Василевска-Уильямс, известная своими быстрыми (и безумно сложными) алгоритмами перемножения матриц за вместо и её бывший аспирант Джош Алман опубликовали препринт на arxiv.org, демонстрирующий алгоритм решения задачи 3SUM за .

Это знаковое событие в узких кругах. Во-первых, раньше предполагалось, что решить эту задачу быстрее, чем за , невозможно. Во-вторых, вместе с ней наконец решилась быстрее, чем за , задача нахождения кратчайших путей между любыми парами вершин в графе (All-Pairs Shortest Paths, APSP) — по-настоящему практическая задача вычислительной геометрии. В-третьих, мало того, что корректность работы проверяла закрытая модель Anthropic — авторы также утверждают, что Claude нашёл изначальный алгоритм, после чего учёные осознали и улучшили его.

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

Threads у моего проекта EverStory (семейные фото-книги) долго жил по остаточному принципу. 2–3 поста в неделю, если вспомню, а в неделю релиза тишина. Комментарии я лайкала и забывала. Хотя люди писали там вполне живые вещи: про бабушкины альбомы, коробки с плёнками, про то, кто в семье «хранитель архива». Разбирать это было некому.

Тогда я собрала агента Amy. Она пишет посты и публикует их 5 раз в день, отвечает на комментарии и раз в неделю приносит выжимку того, что говорит аудитория. Управляется кнопками в Telegram, без моего одобрения ничего не публикует. Код открыт, ссылка в конце.

Почему при стандартных настройках KNN-поиска пересчёт расстояний при колоночном хранении векторов работал медленнее, чем при построчном, и как Manticore почти убрал эту разницу, сохранив скорость поиска по данным, которые не помещаются в память.

Плеер показывает у трека «ми минор», но как он это узнал? Программа не слушает гармонию, как музыкант: она считает, сколько звучит каждой из 12 нот, и ищет гамму, на которую набор похож сильнее всего. Разбираю алгоритм Крумхансл-Шмуклера на реальных треках, показываю, где он путает квинту и родственную тональность, и что тут меняют нейросети.

В статье расскажу про то как боролся с переместившимся клубком запутанных сущностей. Также поделюсь идеями и новостями по прототипу.

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

СуперЗавуч - современная программа для составления расписаний уроков для школ, лицеев и колледжей. Программа позволяет создать расписание за несколько минут и имеет много параметров для конфигураций.

Почему для понимания товара недостаточно одной фотографии? Проследим, как модели электронной коммерции эволюционировали от визуального поиска и CLIP к мультимодальным представлениям, объединяющим изображения, текстовые описания и атрибуты товаров. Также рассмотрим e-CLIP, MOON, MOON2.0, AFMRL и MOON3.0.

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

В стеке вроде Raft логика такая: узлы голосуют за лидера, пишет только он; у каждого периода лидерства есть порядковый номер (term), чтобы отличать старые голоса от новых; лидер пропал — новые выборы. В Grid допуск записи устроен иначе. Лидер не выбирается голосованием. Вместо этого узлы обмениваются числовым параметром синхронизации (фазой, в смысле модели Курамото) и отдельно подтверждают каждую операцию контрольной суммой её содержимого. Этот протокол называется ORCHID.

За последний год я проверил около двадцати торговых идей. Каждая сначала выглядела убедительно: приличная t-статистика, гладкая кривая доходности, понятная история. И каждая умерла на конкретной проверке. В этой статье собраны эти проверки с реальными цифрами «до» и «после».

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