Однажды по работе мне прилетела задача по сборке и запуску Linux на одноплатном ПК. Тогда я, будучи разработчиком ПО для микроконтроллеров, встал в небольшой ступор — задачка явно не решалась установкой IDE и нажатием в ней кнопки «Собрать проект». Гугл помог узнать о том, что существует некий Buildroot. В материалах по теме всё выглядело довольно просто: скачай, настрой, дерни пару команд, загрузи результат на одноплатник — и можно запускать! Получается, процесс не многим сложнее установки дистрибутива Linux или Windows на обычный ПК? Конечно же, нет. Ведь если у тебя в руках кастомный одноплатник неизвестного китайского бренда, а не BeagleBone или Raspberry Pi, то зарыться в Buildroot придётся с головой...

Задача
Три айтишника — Маша, Вася и Петя — пошли в поход. После ужина они решают, кто будет мыть посуду. Петя дежурит один, а Маша с Васей — вдвоём. Значит, нужно выбрать Петю с вероятностью ⅓, а Машу с Васей — с вероятностью ⅔. Под рукой — только честная монетка. Как с её помощью устроить такой жребий?

Когда мы обсуждали эту задачу со студентами, они предложили такой способ. Бросим монету дважды: если выпали два орла — дежурит Петя; если один орёл и одна решка — Маша с Васей; если две решки — перебрасываем

Чтобы выбрать дежурного так, в среднем уходит 8⁄3 броска (чуть позже мы это докажем). Можно ли сделать это быстрее? Существует ли алгоритм, для которого ожидаемое число бросков меньше?

Оказывается, можно придумать простой, но неочевидный метод, позволяющий смоделировать событие с вероятностью ⅓ — и в среднем требует не больше двух бросков. Он называется алгоритмом Кнута–Яо

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

В финале мы обобщим эту идею: научимся моделировать любую вероятность p от 0 до 1 — и любое дискретное распределение. Заодно познакомимся с важным понятием, называемым энтропией

А в самом конце, как всегда — красивая задача

Привет! На связи Антон Полухин из Техплатформы Городских сервисов Яндекса, и сейчас я расскажу о софийской встрече Международного комитета по стандартизации языка программирования C++, в которой принимал активное участие. Это была последняя встреча, на которой новые фичи языка, с предодобренным на прошлых встречах дизайном, ещё могли попасть в C++26.

И результат превзошёл все ожидания:

• compile-time-рефлексия
• рефлексия параметров функций
• аннотации
• `std::optional<T&‍>`
• параллельные алгоритмы

На прошлой неделе в Софии, столице Болгарии, закончилась работа над стандартом C++26, который помимо контрактов, std::execution и всего прочего теперь включает и рефлексию.

В этой статье будет продемонстрирован один из примеров её использования: преобразование строк в формате JSON в объекты C++ на этапе компиляции.

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

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

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

Предлагаемый цикл я рассматриваю как дополнение к популярным введениям и обзорам геометрической алгебры, хотя оно может быть полезным и как первое знакомство с предметом. Его отличает больший чем обычно акцент на алгебраическую часть, а также следование оригинальному подходу Эрика Ленгэля (Eric Lengyel) к построению геометрических алгебр, который мне представляется наиболее последовательным и логически непротиворечивым.

Новый стандарт C++, C++23, впервые с C++11 расширил всем привычную линейку контейнеров: помимо знакомых array, vector, (unordered_)set, (unordered_)map и прочим в нее теперь входят непонятные flat_set, flat_map, flat_multiset и flat_multimap. Ответим на вопросы, что это за контейнеры, когда они могут быть полезны, сравним дизайн стандартизированных «плоских» контейнеров с дизайном плоских контейнеров из Boost и ETL и, конечно, произведём замеры и сравним производительность flat_ и не flat_ контейнеров.

Тонкая настройка Вселенной – последний оплот сторонников разумного замысла в сражении с атеистами, прибежище для тех, кто уже не в силах отрицать законы физики и дарвиновскую эволюцию, но всё ещё верит в сверхъестественную силу, которая заблаговременно позаботилась о нашем благополучии и предопределила наперёд всю космологическую эволюцию. Якобы невозможность существования разумной жизни во вселенных с другими значениями фундаментальных констант – самое явное доказательство, что мир был сотворён Богом, настроившим физические параметры так, чтобы мы могли появиться и жить в разумно устроенном мире. Научной альтернативой этому объяснению считается инфляционная мультивселенная, в которой существуют все возможные миры со всеми значениями констант. Большинство этих миров необитаемы, а наша вселенная пригодна для жизни просто потому, что в других вселенных некому задавать вопросы о тонкой настройке. В данной статье мы попробуем кратко разобрать столь обширную тему с точки зрения современной космологии и понять, какая теория ближе всех подошла к решению этой проблемы. В процессе мы выясним, поставила ли наука точку в вопросе о наличии или отсутствии в эволюции Вселенной разумного замысла, а также узнаем, есть ли сегодня хоть какое-то основание для антропоцентризма и веры в Творца.

Получение имени типа, не важно это структура или перечисление, в C++ — проблема. То, что тривиально известно компилятору на этапе парсинга исходников, не получится перевести в человеко-читаемый вид в рантайме. Можно использовать std::type_info::name, который не является переносимым решением, потому что зависит от реализации манглинга в компиляторе. Некоторые компиляторы (например, MSVC, IBM, Oracle) создают "удобное" имя типа, а вот gcc и clang, возвращают искаженное имя, котороe можно преобразовать в удобочитаемую форму с помощью дополнительных функций, например abi::__cxa_demangle. Чтобы вся эта магия работала нужно подключить RTTI, который тоже не всегда доступен, а иногда и вообще-то вреден, потому что сжирает драгоценную производительность, но можно сделать по другому.

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

Этими словами заканчивалось письмо Эвариста Галуа, написанное для своего друга Огюста Шевалье за два дня до его смерти от полученных на дуэли ран на 21 году жизни. Ни Якоби, ни Гаусс в его теоремах не разобрались, зато спустя 15 лет разобрался Жозеф Лиувилль и опубликовал работы Галуа, ставшие впоследствии фундаментом современной алгебры, известные сейчас как теория Галуа. В статье расскажу про одну из частей этой теории - поля Галуа, получившая настолько повсеместное применение в криптографии и избыточном кодировании, что Intel и AMD выпустили набор процессорных расширений для эффективной реализации операций над этими полями.

Заметка! Если вам довелось использовать/реализовывать поля Галуа, то большая часть статьи для вас скорее всего будет не интересна, но возможно в последних разделах будет что-то для вас новое.

Ручное управление ресурсами в низкоуровневом си-подобном коде на C++ — довольно хлопотное занятие. Создание достойных RAII-врапперов для каждого используемого сишного API не всегда практично, а использование подходов с goto cleanup или множеством вложенных if (success) вредит читаемости кода.

Макрос defer как никогда кстати! Отложенная лямбда будет выполнена при выходе из области видимости, независимо от того, будет ли выполнен return, брошено исключение, или даже выполнен goto наружу. Данный макрос по-настоящему zero-cost и не зависит от рантайма C или стандартной библиотеки, поэтому его можно использовать даже в разработке под ядро ОС.

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

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

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

В этой статье разберём мутный, но крайне важный инструмент ‒ std::launder. Мы поглядим, зачем его протащили в C++17 и что компилятор делает, когда видит launder.

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

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

Статья рассчитана на читателей, которые не являются гуру C++ или знатоками тонкостей языка, но в целом знакомы с языком и его идеями, хотя знание ассемблера x86 не требуется, я буду прикладывать ссылки на примеры кода quickbench, чтобы объяснить, почему даю те или иные советы.

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

Привет!
Меня зовут Мария Аксютина, я гейм-дизайнер, автора блога Хорошие маленькие игры и
я очень люблю рефлексировать свой опыт.

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

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

Отличный повод сделать перерыв — и вернуться с парой новых мыслей.

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

Сегодня разбираем &&* неувядающую классику C++ — ссылки & и указатели *. Казалось бы, два оператора, делов-то, но стгоит нырнуть под крышку — и выясняется: тут и разное время жизни, и несменяемость адреса, и прочие вещички. Разберемся в статье подробнее.

C++ уже десятки лет является краеугольным камнем, на котором строятся программы, ориентированные на высокую производительность. Он лежит в основе самых разных проектов, относящихся практически ко всем аспектам человеческой деятельности — от встроенных систем до платформ высокочастотной торговли. Его возможности по совмещению низкоуровневых средств управления вычислительными ресурсами с высокоуровневыми абстракциями превращают его в уникальный инструмент, подходящий для создания программ, при выполнении которых значение имеет каждая микросекунда. По мере того, как язык развивается, новые стандарты, вроде C++23 и ожидаемого C++26, вводят в него функционал, который улучшает и его возможности по созданию высокопроизводительных программ, и продуктивность пользующихся им программистов. Особенно это касается разработки высокопроизводительных служб — систем, которым требуются низкие задержки и высокие значения пропускной способности, которые нуждаются в эффективном использовании ресурсов. Среди них — аналитические системы, работающие в режиме реального времени, игровые серверы и распределённые системы управления базами данных.

Мало что настолько меня угнетает, как невозможность что‑либо понять так, чтобы потом объяснить это самому себе:) И хоть я уже давно не девятиклассник, этот период запомнился мне внезапным переходом от заучивания материала «чтобы не схватить парашу» к некоторой степени осознания «а как оно там устроено и почему именно так». Сложнее всего было с математикой и я постоянно изобретал для себя «объяснялки». Этот навык, к счастью, прижился и стал привычкой.

Мы рассмотрим, чем опасны шаблоны для проекта на C++ и как минимизировать эти риски. В оптимизации нам помогут инлайн-файлы, явные инстанциации и даже модули из C++20.