Алгоритмы *

Поиск подстроки в строке — важная задачка в текстовой обработке. В Go стандартная библиотека имеет strings.Index, но он использует простой перебор символов, который работает с O(n × m) в худшем случае, где n — длина текста, m — длина подстроки.

Алгоритм Кнута-Морриса-Пратта решает эту проблему, используя префикс-функцию, которая позволяет пропускать заведомо ненужные сравнения. В результате его сложность O(n + m), что делает его подходящим для больших текстов и множественных поисковых запросов.

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

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

Многие слышали о классической игре сокобан, а кто-то наверняка играл в "Мудрого крота" из Роботландии. В этой части мы будем двигать ящики по складу, используя возможности json[b] и геометрического типа point.

ML‑модели применяются в сервисах Яндекса уже много лет, мы накопили большой опыт в их обучении. Статьи об этом коллеги регулярно публикуют, в том числе на Хабре. Но сегодня хочу обсудить другую не менее важную задачу — ускорение инференса (процесса работы на конечном устройстве) моделей. Скорость зависит от разных условий, главным образом от архитектуры и железа, но есть множество интересных способов повлиять на неё. Особенно актуальна проблема тяжёлого инференса при использовании больших языковых моделей (LLM) — на то они и large!

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

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

Прогнозирование погоды прошло долгий путь. В 650 г. до н. э. вавилоняне пытались предсказать погодные условия, основываясь на характере движения облаков. Три столетия спустя Аристотель написал «Метеорологику», рассуждая о таких явлениях, как дождь, град, ураганы и молнии. Многое из этого оказалось неверным, но это одна из первых попыток подробно объяснить погоду.

Лишь в 1859 году Метеорологическая служба Великобритании выпустила свой первый прогноз погоды для судоходства. Два года спустя служба опубликовала свой первый публичный прогноз погоды. Хотя метеорологические измерения со временем улучшились, масштабные изменения в прогнозах произошли с использованием компьютерного моделирования. Это началось столетие спустя, в 1960-х годах.

С тех пор прогнозы значительно улучшились.

Метеорологическое бюро заявляет, что его четырехдневные прогнозы сейчас так же точны, как и однодневные прогнозы 30 лет назад.

Национальный центр ураганов США публикует данные об «ошибке отслеживания» ураганов и циклонов — ошибке в том, где обрушивается ураган. Это показано на диаграмме ниже, начиная с 1960-х годов.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

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

Как известно, нахождение оптимального алгоритма решения любой NP-полной задачи - это цель амбициозная, пахнущая славой и неплохими деньгами. Как раз к таким задачам относится Судоку, и как раз своим решением этой головоломки я горел последний месяц. На данный момент сделана (по ощущениям) лишь половина дела, и хоть результаты и вышли интересными (по крайней мере для меня-любимого) - дело еще далеко до завершения, т.к. в определенном моменте настал "творческий тупик". Впрочем, надеюсь, что он пройдет и на свет появится по крайней мере какое-то новое любопытное решение. Пока что лишь поделюсь своими первыми наработками в этом направлении. Пока что они не вполне вылизаны + написаны на Java, перевод на какой-нибудь более простой для восприятия язык планируется лишь с окончательной победой на Java.

Вопрос

Я знаю, как декодировать UTF-8 с помощью битовой математики и таблиц поиска (см. https://github.com/skeeto/branchless-utf8), но если я хочу преобразовать кодовую точку UTF-8, то можно ли сделать это без ветвлений?

Для начала, можно ли как-то написать эту функцию на C, которая возвращает количество байтов, необходимых для хранения байтов UTF-8 кодовой точки, без использования ветвления? Или для этого потребуется огромная таблица поиска?

Привет. Меня зовут Макс, с недавнего времени я занимаюсь в AIRI вопросами ИИ для вычислительной химии и физики. А до того работал в научной группе Т‑Банка, где занимался проблемой неопределенности нейронных сетей. Недавно нашу статью «Identity Curvature Laplace Approximation for Improved Out‑of‑Distribution Detection» приняли на WACV 2025 — престижную конференцию по машинному зрению.

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

Подробнее о новом методе — в тексте ниже.

В 1987 году вышла дебютная научно-популярная книга Джеймса Глика «Хаос. Создание новой науки», впервые опубликованная на русском языке в переводе издательства «Амфора» и выложенная здесь. Эта книга оживила интерес к теории самоорганизующихся систем, сформулированной в середине XX века в работах Германа Хакена (1927-2024) из Штутгартского университета, посвящённых синергетике. Смежные исследования по физике неравновесных систем принадлежат Илье Романовичу Пригожину (1917 - 2003),  франко-американскому физику российского происхождения. В основе этих работ лежит идея о том, что существуют такие системы, нарастающая энтропия в которых постепенно выравнивается, и общая структура системы остаётся относительно неизменной, несмотря на то, что в отдельных частях системы энтропия продолжает нарастать. В том же 1987 году появилось удивительное исследование Пера Бака, Чао Танга и Курта Визенфельда, в котором они описали модель песчаной кучи.    

Феномен связан с изучением и моделированием самоорганизующихся систем и их устойчивости, а также смыкается с исследованием фракталов, степенных рядов и клеточных автоматов. В контексте фракталов эту тему рассматривал на Хабре уважаемый Андрей Заболотский @Browning в статье «Фракталы в песках или больше трёх не собираться». Если желаете вместо моего текста почитать строгое, но вполне популярное и увлекательное изложение данной темы — отсылаю вас к статье уважаемого Никиты Калинина «Песочная модель», размещённой на сайте МФТИ. Под катом я расскажу, как эта модель работает и какие неожиданные вопросы подбрасывает.

Давным‑давно, когда мир ML состоял из бустингов, линейных моделей и статистических подходов, перед нашей командой API Яндекс Карт стояла задача сделать качественный Геокодер. Это алгоритм, который конвертирует текстовые запросы пользователей в поисковой строке карт в координаты и обратно. Он нужен, когда люди вводят адреса с ошибками, опечатками или народными наименованиями, например «Мяснитская 8». Геокодер должен понять, что имелось в виду «улица Мясницкая, дом 8/2», и вернуть на карте отметку с точной локацией и координатами.

Разработанный для России Геокодер отлично справлялся, но мы хотели найти способ быстро адаптировать это решение к адресным системам других стран. Технологические ограничения не позволяли быстро адаптировать решение, поскольку для каждой страны требовалась разработка собственных правил геокодирования, которые бы учитывали различия и языковые особенности. Однако появление и развитие алгоритмов deep learning открыло новые горизонты: методы active learning, аугментации данных и contrastive learning позволяют значительно улучшить итоговое качество геокодирования и учитывать нюансы различных адресных систем.

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

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

const fizzbuzz = (n: number)=>`${n%3 ? '' : 'Fizz'}${n%5 ? '' : 'Buzz'}`;

В данной статье представлен метод rStar-Math, демонстрирующий способность малых языковых моделей (SLM) достигать конкурентоспособных результатов, сопоставимых и даже превосходящих показатели модели OpenAI o1 в задачах математического рассуждения, без использования дистилляции знаний из более крупных моделей. Ключевой особенностью rStar-Math является применение "глубокого мышления" посредством поиска по дереву Монте-Карло (MCTS), где SLM выступает в роли модели политики, генерируя последовательность шагов решения, а другая SLM оценивает их, действуя как модель вознаграждения за процесс. Представлены три ключевые инновации: метод синтеза данных CoT с расширением кода, новый подход к обучению модели предпочтения процессов (PPM) и стратегия саморазвития. Экспериментальные результаты показывают значительное улучшение математических способностей SLM, подтверждая эффективность предложенного подхода.

Как создать быстрый код на C++? Мы будем разбираться в современных техниках оптимизации: кэш-локальности, кастомных аллокаторах и многопоточности. Практические примеры и результаты тестов.

• Алгоритмы не должны быть чрезвычайно сложными для понимания!
• Алгоритмы не скучны и не бесполезны!
• Интересные книги про алгоритмы могут быть и с примерами кода на Си!

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

Никита Грибанов — Data Scientist из компании RAFT, занимается исследованием безопасности. На закрытом эфире для комьюнити Skillbox Code Experts рассказал, что такое LLM и как с ними общаться. Изложили основные мысли в статье.

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

В качестве небольшого предисловия:
Зачем я спроектировал дерево?

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

Пример профилей поведения будет в конце статьи.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

В этой части совсем простая идея по одновременному решению систем линейных уравнений "пачками".