cpluspluc | Unsorted

Telegram-канал cpluspluc - C++ Academy

16151

По всем вопросам- @haarrp @itchannels_telegram - 🔥 best it channels РКН: clck.ru/3FmxJF

Subscribe to a channel

C++ Academy

C23 сделал enum в C заметно удобнее для низкоуровневого кода.

Раньше базовый тип перечисления обычно выбирал компилятор, и enum часто занимал размер обычного int:


enum status {
OK = 0,
ERROR = -1
};


На многих системах это 4 байта.

В C23 можно явно указать базовый тип:


enum status8 : int8_t {
OK8 = 0,
ERR8 = -1
};


Теперь такой enum занимает 1 байт.

Можно и наоборот использовать большой тип:


enum status64 : uint64_t {
OK64 = 0,
ERR64 = UINT64_C(0xFFFFFFFFFFFFFFFF)
};


Это особенно полезно там, где важен точный layout структуры, ABI, сетевые протоколы, embedded и работа с бинарными форматами.

В C23 размер enum теперь можно контролировать явно, а не полагаться на выбор компилятора.

Читать полностью…

C++ Academy

🐧 Linux Cheat Sheet - шпаргалка по командам Linux

Самая удобная шпаргалка по Linux и Bash на русском: теория простым языком (как устроены файлы, процессы, права, память, загрузка и сеть), команды терминала, права доступа, процессы, сеть, SSH, systemd, grep/sed/awk, Vim и готовые однострочники - с примерами.

А для тех, кто идёт дальше, - продвинутый уровень: Bash для профи, LVM и RAID, трассировка и производительность, ядро, безопасность, контейнеры, восстановление системы и вопросы с собеседований.

https://github.com/justxor/Linux-/

Читать полностью…

C++ Academy

😂 Собеседование на C++ прошло успешно

HR: у вас есть опыт с C++?

Я: конечно, отлично знаю оператор `goes to`.


int x = 10;

while (x --> 0) {
std::cout << x << '\n';
}


Никакого специального --> оператора в C++ тут нет.

Это просто:


x-- > 0


Сначала берётся текущее значение x и сравнивается с 0, а затем x уменьшается на единицу.

Поэтому код выведет:


9
8
7
6
5
4
3
2
1
0


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

Читать полностью…

C++ Academy

⚡️ Как спроектировать ИИ-агента над корпоративными данными

6 октября в 17:00 мск пройдёт новая встреча Архитектурного клуба Яндекс 360 — открытого сообщества для архитекторов и инженеров высоконагруженных систем.

Даниил Смирнов, руководитель службы бэкенд-разработки Антиспама Яндекс 360 , разберёт архитектуру корпоративного агента: оркестратор, инструменты, память, EVAL и наблюдаемость.

На эфире обсудят:

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


📅 6 октября, 17:00 мск
💻 Онлайн, участие бесплатное

→ Зарегистрироваться на встречу

Читать полностью…

C++ Academy

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

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

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

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

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

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

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

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

Читать полностью…

C++ Academy

⚙️ 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++ Academy

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

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

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

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

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

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

Читать полностью…

C++ Academy

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

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

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

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

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

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


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

Читать полностью…

C++ Academy

🔥 Почему в 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++ Academy

🔥 Хочешь расти в 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: /channel/+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: /channel/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: /channel/addlist/2Ls-snqEeytkMDgy
Папка Frontend: /channel/addlist/mzMMG3RPZhY2M2Iy

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

ИТ-мемы: t.me/memes_prog
Английский для программистов: t.me/english_forprogrammers
ИИ и технологии: t.me/vistehno
954 ГБ open-source курсов: /channel/+rKBQEMccAA01MTcy
ИТ-книги бесплатно: /channel/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++ Academy

🛠 Как автоматически закрывать файлы из 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, обработчик освобождения вызван не будет.

Читать полностью…

C++ Academy

🚀 Как ядро 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, которая помогает писать быстрый код на уровне ядра.

Читать полностью…

C++ Academy

🔥 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

Читать полностью…

C++ Academy

Разбор одной из тех 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

Читать полностью…

C++ Academy

3D-фрактал Mandelbulb можно отрендерить примерно в 100 строках C++ - вообще без полноценного 3D-движка.

В основе всего несколько идей:

- Mandelbulb строится через сферическую итерацию в степени 8
- distance estimator примерно определяет расстояние до поверхности фрактала
- sphere tracing двигает луч большими шагами через пустое пространство
- когда луч приближается к поверхности, конечные разности вычисляют нормаль для освещения
- результат записывается напрямую в обычный PPM-файл

То есть сложнейший на вид 3D-фрактал получается из математики, ray marching и небольшого количества C++.

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

Читать полностью…

C++ Academy

Minimum-Cost Maximum-Flow всего в ~110 строках C++

Хороший компактный пример одного из самых полезных алгоритмов на графах.

Задача MCMF: провести через сеть максимально возможный поток и одновременно сделать его стоимость минимальной.

В этой реализации:

- residual graph хранит оставшиеся возможности для потока
- SPFA каждый раз ищет самый дешёвый увеличивающий путь
- после поиска определяется bottleneck - сколько потока реально можно протолкнуть по найденному пути
- поток отправляется по пути
- процесс повторяется, пока путь из источника в сток больше найти нельзя

Особенно красивый трюк - обратные рёбра.

Прямое и обратное ребро добавляются подряд, поэтому получить индекс пары можно через:


id ^ 1

Если id чётный, id ^ 1 даст следующее нечётное ребро. Если нечётный - вернёт предыдущее чётное.

MCMF пригодится там, где мало просто найти максимальный поток и у каждого решения есть цена:

• назначение сотрудников на задачи
• логистика
• маршрутизация
• matching с разной стоимостью
• распределение ресурсов
• расписания

Компактный пример того, как residual network, shortest path и greedy augmentation собираются в один мощный алгоритм.

Читать полностью…

C++ Academy

`🤖 В SourceCraft появилась команда цифровых разработчиков
Агентам можно назначать задачи прямо в GitLab. Они работают под собственными учётными записями, выполняют поручения и возвращают результат разработчику.
Если по ходу работы чего-то не хватает, агент сам запрашивает данные или согласование у команды — то есть не останавливается на первом незаполненном месте.
Ещё можно подключить собственного агента, в том числе созданного в Yandex AI Studio.

Читать полностью…

C++ Academy

Физически корректный ray tracer всего в 99 строках C++

smallpt от Kevin Beason - один из самых известных примеров того, насколько компактным может быть настоящий path tracer.

В этих 99 строках есть:

* отражения
* преломления
* мягкие тени
* color bleeding
* зеркальные и стеклянные поверхности

Основа при этом минимальная: векторы, лучи, сферы и одна рекурсивная функция radiance().

Если дать рендеру тысячи samples per pixel, он собирает полноценный Cornell Box с зеркальной и стеклянной сферами.

Проект появился ещё в 2008 году и до сих пор отлично показывает базовую механику path tracing.

Читать полностью…

C++ Academy

Лицо C++-разработчика, когда он написал 6000 строк кода, чтобы обогнать твои 4 строки на Python на 0,000438 секунды.

Читать полностью…

C++ Academy

Разработчики 3D-графики, все сюда

Если вы пишете рендер на C++ с отдельным RenderThread, то знаете эту боль: данные грузятся в фоне, а GPU-ресурсы всё равно создаются в потоке отрисовки. И пока RenderThread в длинном цикле создаёт буферы и текстуры, он не рисует — он стоит, пока не обработает список загруженных ресурсов.

Мы это исправили! В новой статье на Хабре рассказываем, как пришли к новому подходу:
1. как вынесли создание буферов и текстур на потоки загрузки,
2. что сделали для Metal, а что для Vulkan,
3. и какие ограничения графических API пришлось учесть.

Другие инженерные инсайты от 2ГИС → в Telegram-канале RnD

Читать полностью…

C++ Academy

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

Читать полностью…

C++ Academy

💡 Алгоритм Флойда находит цикл в связном списке всего с двумя указателями и `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) по памяти


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

Читать полностью…

C++ Academy

⚡️ В 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 часто выглядит коротко, пока не начнёшь разворачивать макросы.

Читать полностью…

C++ Academy

💡 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);

Читать полностью…

C++ Academy

📚 Отличная подборка материалов по современному 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++ Academy

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

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

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

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

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

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

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

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

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

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

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

Читать полностью…

C++ Academy

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

Читать полностью…

C++ Academy

🔥 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 и библиотеки с предсказуемой производительностью.

Читать полностью…

C++ Academy

Bare Metal C++: как писать прошивки на C++ без ОС и тяжёлого runtime

Practical Guide to Bare Metal C++ - бесплатная практическая книга для разработчиков, которые хотят использовать C++ напрямую на микроконтроллерах и ARM-платформах.

Внутри:

- анализ машинного кода, который генерирует компилятор
- запуск C++ без стандартного runtime
- работа без исключений, RTTI и динамической памяти
- шаблоны и статические структуры данных
- event loop и компонентная архитектура драйверов
- прерывания, таймеры, UART, GPIO, I2C и SPI
- сборка bare-metal приложений для Raspberry Pi

Автор показывает, как применять возможности C++ там, где ограничены память, процессорное время и размер прошивки.

Это не учебник для новичков. Материал рассчитан на разработчиков, которые уже знают C++ и хотят понять, во что превращается их код на уровне железа.

https://arobenko.github.io/bare_metal_cpp/

#cpp #cplusplus #embedded #baremetal

Читать полностью…

C++ Academy

🔥 Джулиан Сторер - разработчик с более чем 30-летним опытом C++

Он создал сразу несколько заметных проектов в мире аудио-разработки:

- Tracktion DAW
- JUCE C++ Framework
- Cmajor DSP language

Особенно интересно тем, кто работает с:

- C++
- аудио и музыкой
- DSP
- DAW
- real-time приложениями

У него много сильного open-source кода и проектов, которые стоит изучить разработчикам из audio/software engineering.

https://github.com/julianstorer

Читать полностью…
Subscribe to a channel