Алгоритмы *

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

Именно за эту сложную задачу взялась команда Департамента управления данными (SberData) в рамках эффективной интеграции ИИ‑агентов в Корпоративную аналитическую платформу Сбера (КАП), которая объединяет современные инструменты для работы с данными: хранение, интеграция, аналитика, моделирование и контроль качества данных. Наличие таких технологий, как продвинутые LLM (например, GigaChat), и большие объёмы данных делают исследование подобных задач актуальным для рынка больших данных.

В статье мы сравним эффективность векторного поиска, гибридных методов и подхода Retrieval‑Augmented Generation (RAG), оценим их влияние на точность результатов и обсудим практические ограничения.

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

Мы, Тимофей Соломенников и Руслан Мирзоев, разработчики онлайн-кинотеатра PREMIER, хотим поделиться своим опытом и на реальных примерах показать, что даёт правильное использование структур данных.

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

Всякое рациональное число в позиционной системе счисления имеет либо конечную запись дробной части, либо бесконечную периодическую запись. Как вычислить соответствующий период для произвольного числа вида 1/α? В статье выведем универсальную формулу и рассмотрим конкретный и «быстрый» пример с большим периодом, но в шестнадцатеричной системе счисления, который можно проверить на калькуляторе.

Прием и парсинг NMEA-данных от GPS-приемника, а также, рассмотрение работы разных типов GPS (UART и RS-232): как правильно подключить модуль к микроконтроллеру STM32.

«Лень‑матушка вперёд нас родилась»

В этой статье я хочу рассказать о технике «Expression Templates» и её применении в библиотеке simstr.

Как известно, «хороший программист — ленивый программист». Именно лень толкает нас на поиск оптимальных решений и экономию ресурсов. А человек, проводящий много времени с компьютером — волей‑неволей начинает его «одушевлять» и беспокоится о нём. Поэтому не знаю, как у вас, а у меня сердце кровью обливается, когда я вижу, что для получения конечного результата тем способом, который написан в программе, бедному процессору придётся выполнять много лишней работы, зазря тратить тактики и бестолку гонять байтики туда‑сюда. Это прямо вызывает боль.

Вот, к примеру, давайте рассмотрим такой простенький код.

Можно ли применить известный трюк с операцией XOR, используемый для поиска в списках одного или двух пропущенных чисел, сделав так, чтобы он подошёл бы для поиска тысяч отсутствующих идентификаторов в таблицах, содержащих миллионы строк?

Идея собрать инерциальный навигатор пришла в голову быстро, но подобрать подходящие компоненты было сложнее. Главный микроконтроллер должен иметь достаточную вычислительную мощность для интегрирования уравнений движения и работы пользовательского интерфейса, при этом потреблять минимум энергии. Я выбрал контроллер семейства STM32 от STMicroelectronics, основанный на ядре ARM Cortex‑M. Этот чип обладает богатым набором периферии (I²C, SPI, UART, SDIO) и аппаратным блоком плавающей точки. К тому же компания ST поставляет готовые программные библиотеки для работы с MEMS‑датчиками.

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

Интегральный датчик инерции — сердце устройства. За основу взял 9‑осевой MEMS‑IMU WitMotion WT901, сочетающий три акселерометра и три гироскопа и электронный компас, что соответствует классическому INS. Этот модуль имеет низкий шум ускорений (~0,03 m/s²) и угловых скоростей (~0,02°/s) и выдает данные по интерфейсу SPI. Для обеспечения работы в широком температурном диапазоне датчик снабжён встроенным термодатчиком, данные которого учитываются при калибровке.

Двоичная куча (binary heap) — это структура данных, которая представляет собой бинарное дерево, удовлетворяющее определённым условиям:

Библиотека функций к Script-fu

Как я ранее уже говорил, обобщённые функции нашей системы производят диспетчеризацию вызовов методов основываясь на типах входящих аргументов. Пока меня устраивала ситуация, что диспетчеризация производится только для классов. Все остальные типы данных не учитывались при диспетчеризации методов. В реально же CLOS возможна диспетчеризация по примитивным типам данных. И вообще для работы обобщённых функций классы не требуются. Можно ли как то реализовать подобное поведение в нашей системе? Решению данного вопроса и посвящена эта статья.

В комментариях к моим статьям регулярно встречаются возражения по поводу понятия «модель числа» – это какой-то оксюморон, фантазии автора и др.
В ответ могу только заметить, что в математике имеют дело с натуральными (N), целыми (Z), рациональными (Q), вещественными (R) и комплексными (С) числами. Приведенные термины по существу называют модели чисел с четко различимыми свойствами и допустимыми операциями в каждом из множеств названных чисел. Соотношения между этими моделями задается  включением левого (меньшего) в правое (большее) множество чисел N ⸦ Z ⸦ Q ⸦ R ⸦ C.
Главными операциями над множествами чисел в таких моделях являются сложение (+) и умножение (×), обратными к которым являются операции вычитания (–) и факторизация (×^-1).

Для факторизации еще не введен обозначающий ее символ (мной использована операция обратная к символу произведения). Заметим, что обратимость даже главных операций возможна не в любой из моделей. Так операция вычитания не является допустимой для натуральных чисел. Если при вычитании  уменьшаемое меньше вычитаемого, то результат – (разность) не определен в множестве N натуральных чисел.

Когда мы представляем число из некоторого множества суммой слагаемых а + b, то, изменяя значения а и b так, чтобы сумма их оставалась постоянной, мы задаем аддитивное представление конкретного числа или его аддитивную (линейную) модель. Такая списочная многострочная модель (СММ) допустима во всех известных множествах. Совокупность сумм для N = х + у, где х и у – переменные модели, с накладываемыми на них ограничениями, задает модель числа N. А распределение делителей числа в натуральном ряде задается законом распределения делителей (ЗРД) числа.

При описании математическими средствами объекта, явления или процесса мы используем отображение (функцию от переменных), которое называем моделью объекта, явления или процесса. Разработка и исследование таких моделей имеет целью определение таких значений переменных модели, которые отвечают  наилучшим описаниям объекта, явления или процесса и цели проводимого исследования, не выходя за рамки допустимого.

Привет, Хабр! Меня зовут Георгий Семёнов, в VK я занимаюсь разработкой в команде инфраструктуры рекомендательных систем, а в Университете ИТМО начинаю свой аспирантский путь в области децентрализованных коллаборативных сред.

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

Если вы учились программировать в конце 80x-начале 90х, то наверняка делали это на ZX Spectrum, БК-0010 или MSX. Во всех этих компьютерах был встроенный язык програмирования. Кто-то начинал сразу с машинных кодов Радио-86РК. В любом случае первыми программами скорее всего были игры.

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

Работа со строками в С++ - зачастую больная боль.

Однако за 25 лет я сумел найти лекарство от этой боли и после 13 лет разработки и испытаний готов поделиться им со всеми страждущими.

simstr — библиотека для использования строк в C++, в которой пишется легко и удобно, а выполняется быстро и оптимально.

Решение первого соревнования на kaggle титаник с помощью библиотеки от яндекса catboost. Два способа: обычная модель и второй: с перебором гиперпараметров с помощью randomizedsearch. Сравнение результатов.

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

Библиотека функций к Script-fu

В принципе реализация представленная в файле obj4.scm и описанная ранее, меня вполне устраивала. Я реализовал там всё что хотел от объектной системы: определения классов и обобщённых функций, множественное наследование, статические поля класса. Но вот какое-то маленькое зёрнышко сомнения, мешало мене оставить этот проект. А всё ли я сделал для ускорения работы системы? И дело даже не в том, что какие то нехорошие люди из проекта GIMPа обрезали возможность для Script-fu загружать расширения, что не даёт возможности быстро рассчитать хеш-код символов(а то и вовсе заменить хеш-таблицы сишной реализацией). Нет. Для себя я спокойно перекомпилирую Script-fu и буду пользоваться всеми преимуществами предоставляемыми настоящей tinyscheme. Но что же можно сделать ещё, чтобы улучшить скорость работы ОО системы? А может и не только скорость.

В 1957 году, когда компьютеры программировались на машинных кодах и ассемблере, канадский учёный Кеннет Айверсон задумался: как сделать описание алгоритмов столь же строгим, как математические формулы, но при этом ещё и сделать интерактивном исполняемым? Да-да, интерактивный язык в 60-х, задолго до пайтона, перла и тикля.

Так родился APL — сначала как академический инструмент для описания алгоритмов в книгах (например, в его работе "A Programming Language" 1962 г.), постепенно эволюционировавший в исполняемый язык.

Но причём здесь 2025-й год спросите вы?

Data Science: APL опередил NumPy/Pandas на 40 лет — матричные операции здесь вшиты в ядро.

Обучение: Лучший способ понять SVD или преобразование Фурье — записать их в APL.

Прототипирование: Проверить идею можно быстрее, чем ChatGPT сгенерирует ответ.

Почему об этом мало говорят? 

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

Все примеры — на Python. В предыдущей статье я показывал написание бота и бектест кода, который просто выдаёт сухие сделки и реализованную прибыль в %. Однако существует много разных параметров и переменных стратегии, без которых ее использование обычно убыточно.

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

Привет, Хабр! Сегодня я расскажу про реализацию матричного умножения и особенности разработки для GPU. Познакомлю вас с устройством GPU, объясню, чем отличается программирование от привычного для CPU, какие нюансы нужно учитывать для эффективной реализации операций GEMM. А затем сравним производительность разных подходов к реализации.