C++ Academy

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

Для этого существует HyperLogLog - вероятностный алгоритм оценки количества уникальных элементов.

Вместо хранения каждого значения он:

— хеширует элементы
— распределяет их по buckets
— отслеживает необычно длинные последовательности нулей в хэшах
— по этой статистике оценивает cardinality

Например, с 16384 регистрами можно оценивать даже огромные множества, занимая порядка десятков килобайт памяти.

При этом ошибка может оставаться около 1%.

Именно поэтому HyperLogLog любят в аналитике и больших данных: посчитать COUNT(DISTINCT ...) для миллиардов объектов можно без хранения миллиардов ID.

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

⚙️ useful_abstractions - вычисления на этапе компиляции в C++23

Библиотека упрощает работу с constexpr и consteval. Один заголовочный файл, без зависимостей за пределами стандартной библиотеки.

Что можно делать при компиляции:

* Передавать строки в параметры шаблонов и собирать их из частей.
* Вычислять хеши.
* Получать имена типов без RTTI.
* Экранировать строки для JSON, URL и HTML.
* Проверять UTF-8 и преобразовывать его в UTF-16/UTF-32.
* Останавливать сборку с понятным сообщением при ошибке в данных.

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

Требуется C++23: GCC 14+, Clang 19+ или свежий AppleClang.

Документация — https://constexprcore.github.io/useful_abstractions/

Разница между C++ и Python

«Я про бэкенд»: как устроены AI-системы под капотом бигтеха

🗓 3 октября, Москва и онлайн

О чём: как разработчики высоконагруженных рекомендательных и генеративных систем справляются с нетривиальными вызовами. Доклады в 6 направлениях — от архитектуры систем с AI/ML до MLOps и работы на стыке бэкенда с железом.

Часть спикеров:
🎤 Михаил Цветков (Алиса AI и Умные устройства) — как устроен инференс генеративных ответов Алисы в Поиске
🎤 Алина Шестакова (Positive Technologies, Cloud SIEM) — вердикт за минуту: ML-фильтр и LLM на потоке более 40 тысяч событий в секунду
🎤 Андрей Аксёнов (Авито) — база векторных баз
🎤 Егор Хайруллин (Рекламные технологии Яндекса) — как распределённо обрабатывать более 100 ГБ/с в реальном времени без потерь и дублей с помощью YTsaurus Flow
🎤 Владислав Тюльбашев (Яндекс) — как надежно раздавать конфиги на 200к хостов при отказе [n-1] ДЦ
🎤 Алексей Логинов (Алиса AI и Умные устройства) — как сделать агентную платформу надёжной

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

Полная программа и регистрация

💡 Алгоритм Флойда находит цикл в связном списке всего с двумя указателями и `O(1)` дополнительной памяти.

Идея простая:

slow двигается на 1 узел
fast — на 2

Если цикл есть, они обязательно встретятся.

После встречи один указатель возвращаем в head, а дальше оба двигаем по одному узлу. Следующая точка встречи — точное начало цикла.

Node *detect_cycle(Node *head) {
    Node *slow = head, *fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;

        if (slow == fast) {
            slow = head;

            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }

            return slow;
        }
    }

    return NULL;
}

Сложность:

O(n) по времени
O(1) по памяти

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

🔥 Приглашаем на бесплатный открытый вебинар курса «Программист С»: «Указатели в Си — от адреса к управлению памятью»

🗓 Когда: 24 сентября, 20:00 (мск)

Указатели — это не просто синтаксис, а ключ к пониманию того, как Си общается с памятью. Без них невозможно осознанно работать с массивами, строками, структурами и динамическими данными. На вебинаре разберём указатели от самого основания — адресов и операторов — до передачи параметров по ссылке, чтобы вы перестали бояться звёздочек и начали управлять памятью уверенно.

Что будет на вебинаре:
• Разбор ключевых понятий: адрес переменной, операторы & и *, объявление и разыменовывание указателей — разберём, как Си работает с памятью напрямую;

• Пошаговый анализ связи указателей, массивов и функций — выясним, как передавать параметры по ссылке и заставлять функции изменять переменные вызывающего кода.

👉 Зарегистрируйтесь https://otus.pw/BLgM/?erid=2W5zFHuFYrV


Реклама. ООО "ОТУС ОНЛАЙН-ОБРАЗОВАНИЕ". ИНН 9705100963.

⚡️ В Linux даже обычный syscall начинается с макроса.

Например:

SYSCALL_DEFINE3(write, unsigned int, fd, const char __user *, buf, size_t, count)

После препроцессора это превращается сразу в несколько функций:

- sys_write
- __se_sys_write
- __do_sys_write

Одна строка описывает системный вызов, а C-препроцессор через макросы и token pasting собирает остальную обвязку автоматически.

Именно поэтому код ядра Linux часто выглядит коротко, пока не начнёшь разворачивать макросы.

🔥 Почему в Redis Cluster именно 16 384 hash slot и при чём тут `{}`

Redis Cluster распределяет ключи не напрямую по нодам, а сначала по 16 384 hash slots.

Формула по сути такая:

CRC16(key) % 16384

Но есть важный трюк — hash tags.

Если ключ содержит часть в фигурных скобках, Redis хеширует только содержимое внутри {}:

{user100}:cart
{user100}:orders

Оба ключа будут вычислены по user100, поэтому попадут в один и тот же hash slot и, соответственно, на одну ноду.

Это нужно для multi-key операций в cluster mode.

Именно поэтому такие конструкции позволяют нормально использовать:

- MGET
- MSET
- транзакции
- Lua-скрипты с несколькими ключами

На уровне кода Redis сначала ищет {, затем }, и если внутри есть непустая строка — хеширует только её.

Небольшая деталь синтаксиса, которая на самом деле решает важную проблему распределённых операций в Redis Cluster.

💡 C++: std::map<std::string, ...> не обязан создавать временный std::string при каждом поиске

Если ключ уже приходит как std::string_view, можно использовать transparent comparator:

std::map<std::string, int, std::less<>> status_codes{
    {"not_found", 404},
    {"timeout", 504}
};

std::string_view key = "timeout";

auto match = status_codes.find(key);

🔥 Хочешь расти в IT быстрее остальных? Перестань учиться в одиночку

Можно годами смотреть курсы, читать документацию и всё равно топтаться на месте.

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

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

AI: t.me/ai_machinelearning_big_data
Python: t.me/pythonl
Linux: t.me/linuxacademiya
Хакинг: t.me/linuxkalii
DevOps: t.me/DevOPSitsec
Docker: https://t.me/+90Z5TAyfuNU5YmRi
Golang: t.me/Golang_google
Rust: t.me/rust_code
C++: t.me/cpluspluc
C#: t.me/csharp_ci
Java: t.me/javatg
JavaScript: t.me/javascriptv
React: t.me/react_tg
Frontend: t.me/front
PHP: t.me/phpshka
Android: t.me/android_its
Мобильная разработка: t.me/mobdevelop
Базы данных: t.me/sqlhub
Data Science: t.me/data_analysis_ml
Big Data: t.me/bigdatai
Математика: t.me/data_math
Физика: t.me/fizmat
Kubernetes: t.me/kubernetc
GameDev: https://t.me/gamedev
Haskell: t.me/haskell_tg

Собеседования и карьера:

DS собеседования: t.me/machinelearning_interview
Python собеседования: t.me/python_job_interview

Папка с вакансиями: t.me/addlist/_zyy_jQ_QUsyM2Vi
Папка Go разработчика: t.me/addlist/MUtJEeJSxeY2YTFi
Папка Python разработчика: t.me/addlist/eEPya-HF6mkxMGIy
Папка ML: https://t.me/addlist/2Ls-snqEeytkMDgy
Папка Frontend: https://t.me/addlist/mzMMG3RPZhY2M2Iy

Полезное сверху:

ИТ-мемы: t.me/memes_prog
Английский для программистов: t.me/english_forprogrammers
ИИ и технологии: t.me/vistehno
954 ГБ open-source курсов: https://t.me/+rKBQEMccAA01MTcy
ИТ-книги бесплатно: https://t.me/addlist/BkskQciUW_FhNjEy

Max Ai: https://max.ru/ai_machinelearning_big_data
Max python: https://max.ru/pythonl
ТЕХНО: https://max.ru/vistehno
Max Go: https://max.ru/Golang_google
Max Linux: https://max.ru/linuxkalii
Devops: https://max.ru/DevOPSitsec
C#: https://max.ru/csharp_ci
C++: https://max.ru/cpluspluc
SQL: https://max.ru/sqlhub
Java: https://max.ru/javatg

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

📚 Отличная подборка материалов по современному C++

На Modernes C++ собрали большой структурированный каталог статей по языку - от базовых концепций до сложных тем из современного стандарта.

Что есть внутри:

- templates и metaprogramming;
- concurrency и multithreading;
- smart pointers и управление ресурсами;
- ranges, concepts и coroutines;
- STL и алгоритмы;
- memory model;
- best practices и типичные ошибки;
- новые возможности C++20/23 и дальше.

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

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

https://modernescpp.com/index.php/table-of-content/

#Cpp #CPlusPlus #Programming #STL #ModernCpp

🛠 Как автоматически закрывать файлы из C-библиотеки в C++

FILE* можно обернуть в std::unique_ptr с собственным обработчиком освобождения:

#include <cstdio>
#include <memory>

struct FileCloser {
    void operator()(std::FILE* file) const noexcept {
        std::fclose(file);
    }
};

using File = std::unique_ptr<std::FILE, FileCloser>;

Использование внутри функции:

File file{std::fopen("data.txt", "r")};

if (!file) {
    return;
}

// Передаём FILE* в функции C-библиотеки
int ch = std::fgetc(file.get());

Когда file выйдет из области видимости, unique_ptr вызовет fclose. Это работает при обычном завершении функции, раннем return и раскрутке стека при исключении.

Так устроен RAII: время жизни ресурса связано со временем жизни объекта. Если fopen вернул nullptr, обработчик освобождения вызван не будет.

🐢 Все пытаются ускорить процессоры. А этот проект делает наоборот.

Новый проект CPU deoptimization ищет самые медленные инструкции, которые когда-либо выполнялись на x86.

Идея простая:

Не «как заставить CPU работать быстрее», а:

«Какую самую ужасную инструкцию можно заставить выполнить процессор?»

Результат уже впечатляет:

💀 Рекорд x86:
198 002 498 236 тактов CPU
≈ 62 секунды на выполнение одной инструкции

Это целая «галерея позора» для ассемблера:

- странные инструкции;
- неожиданные микроархитектурные эффекты;
- случаи, когда одна команда превращается в вечность.

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

Assembly Hall of Shame:
https://github.com/xoreaxeaxeax/asm-hall-of-shame

🚀 Как ядро Linux создаёт пакеты переменной длины без лишних копирований

В C есть мощный паттерн — flexible array member.

Вместо хранения заголовка и данных отдельно:

header → отдельно
payload → отдельно

можно сделать один непрерывный блок памяти:

+----------------+
| struct msg     |
| len            |
+----------------+
| payload data[] |
+----------------+

Код:

struct msg {
    uint32_t len;
    uint8_t data[];
};

struct msg *m = malloc(sizeof(*m) + n);

Один malloc() → один блок памяти → один free().

Почему это любят в системном коде:

✅ меньше аллокаций
✅ лучше работа с CPU cache
✅ проще сериализация
✅ нет лишних указателей и разрозненных данных

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

До C99 часто писали:

uint8_t data[1];

и вручную обходили ограничения языка.

Теперь data[] — официальный способ сказать:

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

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

Redis не доверяет обычным строкам C - и вот почему

В C строка заканчивается нулевым байтом \0. Из-за этого strlen() каждый раз проходит весь буфер, а хранить произвольные бинарные данные становится неудобно.

Поэтому Redis использует собственную структуру SDS — Simple Dynamic Strings.

В памяти она выглядит примерно так:

[len][alloc][flags][данные...\0]
                   ↑
                  sds

Перед самими данными Redis хранит метаданные:

- len — текущую длину;
- alloc — размер выделенной памяти;
- flags — тип заголовка.

Благодаря этому длина строки определяется за O(1), а свободное место известно заранее. При добавлении данных Redis не обязан каждый раз заново вычислять размер и перевыделять память.

SDS также остаётся совместимой со многими функциями C: указатель ведёт прямо на буфер, а в конце всё равно находится \0.

Но Redis не зависит от этого терминатора — длина хранится отдельно. Поэтому внутри строки могут находиться нулевые байты, изображения, сериализованные объекты и другие бинарные данные.

Важный нюанс: структура sdshdr из старых примеров сегодня упрощена. Современный Redis выбирает компактный заголовок sdshdr5, sdshdr8, sdshdr16, sdshdr32 или sdshdr64 в зависимости от размера строки.

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

Источник:
https://redis.io/docs/latest/operate/oss_and_stack/reference/internals/internals-sds/
https://github.com/redis/redis/blob/unstable/src/sds.h

🔥 Python + AI без игрушечных демок. Курс для тех, кто хочет собирать рабочие системы.

Stepik: «Python современный AI для разработчика и автоматизации задач»

63 урока, 382 шага, практика с кодом и автопроверкой.

Внутри: RAG, tool calling, агенты, evals, MCP, Ollama, vLLM, pgvector + HNSW, безопасный text-to-SQL, prompt injection, кэш, очереди и sandbox для агентного кода.

Плюс реальные автоматизации: почта, отчёты, боты, вебхуки и браузерные сценарии.

Для тех, кто уже знает Python и хочет перейти к production AI.

⏳ 72 часа скидка 55%

https://stepik.org/a/295921

🔥 Quickselect быстрый, пока не выберет плохой pivot

Обычный Quickselect в среднем работает за O(n), но неудачный выбор опорного элемента может превратить поиск k-го элемента в O(n²).

В 1973 году Блум, Флойд, Пратт, Ривест и Тарьян предложили алгоритм median of medians, который гарантирует линейное время даже в худшем случае.

Идея:

1. Разделить массив на группы по 5 элементов.
2. Найти медиану каждой группы.
3. Рекурсивно найти медиану полученных медиан.
4. Использовать её как pivot для Quickselect.

int mom_pivot(int *arr, int n)
{
    if (n <= 5) {
        sort(arr, n);
        return arr[n / 2];
    }

    int medians[(n + 4) / 5];

    for (int i = 0; i < n; i += 5) {
        int len = (n - i < 5) ? n - i : 5;

        sort(arr + i, len);
        medians[i / 5] = arr[i + len / 2];
    }

    return mom_pivot(medians, (n + 4) / 5);
}

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

Итоговая сложность поиска:

Средний случай: O(n)
Худший случай: O(n)
Дополнительная память: зависит от реализации

На практике randomized Quickselect часто быстрее из-за меньших констант. Median of medians нужен там, где важна строгая гарантия времени: real-time системы, adversarial input и библиотеки с предсказуемой производительностью.

Согласны ?)

Разбор одной из тех Win32-задач, где C++ быстро превращается в борьбу с ручным управлением памятью.

На этот раз речь про LPPROC_THREAD_ATTRIBUTE_LIST, который нужен при расширенном создании процессов и потоков.

Проблема в API простая:

- сначала нужно отдельно узнать размер буфера
- потом вручную выделить память
- вызвать InitializeProcThreadAttributeList
- после работы обязательно вызвать DeleteProcThreadAttributeList
- и только потом освободить сам буфер

Chen предлагает обернуть всё это в RAII через WIL, чтобы очистка происходила автоматически.

Из интересного:

- отдельный helper для освобождения списка
- безопасное получение нужного размера
- разбор того, почему CTAD здесь не помогает
- перегрузки через SFINAE, чтобы не ловить неоднозначность с int
- возможность сразу предзаполнить список атрибутами
- можно заранее оставить место под дополнительные атрибуты, которые добавятся позже

В итоге работа с LPPROC_THREAD_ATTRIBUTE_LIST становится заметно аккуратнее и меньше похожа на ручной Win32-ритуал с кучей cleanup-кода.

https://devblogs.microsoft.com/oldnewthing/20260813-00/?p=112611