C++ *

Я знаю многих программистов и руководителей в IT компаниях, которые недолюбливают математиков и в частности считают их далёкими от жизни идиотами из-за их утверждений в духе "нельзя отсортировать последовательность быстрее, чем за nlogn" -- ведь это очевидным образом неверно, есть же сортировка подсчетом и radix sort. Нюанс в том, что описанное выше -- это распространённая некорректная трактовка одной из ключевых теорем об алгоритмах сортировок, корректное утверждение выглядит так: "не существует алгоритма, который бы гарантированно находил перестановку n элементов, приводящую к возрастающему порядку, быстрее чем за nlogn используя только операции попарного сравнения". В этом утверждении больше слов, оно более сложно в плане когнитивного восприятия, ключевой момент обозначил жирным шрифтом, чувствуете разницу?

В статье хочу рассказать об этой теореме и ещё о двух, на которые я наткнулся когда вел занятия по информатике в 9-11 классах будучи студентом старших курсов. Эти теоремы для меня были удивительным открытием, радовался вне себя когда вывел сам одну из них - её я не встречал ни в одном учебнике по информатике. В последствии все три теоремы были найдены в недрах Кнута, но чёрт побери, их поиск был сложнее, чем вывод!

Если я ещё не убедил Вас прочитать статью, то вот моя последняя попытка: в статье объясню почему пузырёк -- это бесполезная фигня, но внезапно практически также работающая сортировка вставками -- это супер важная сортировка, являющаяся частью std::sort в MSVC, GCC и Clang. Расскажу, каким интересным свойством оптимальности обладает сортировка выбором, являющаяся в теории такой же неэффективной как пузырёк.

Построение множества Мандельброта — классический пример чрезвычайно параллельной задачи (embarrassingly parallel problem).

На первом курсе я впервые столкнулся с такой проблемой: тогда мы изучали SIMD-инструкции в курсе архитектур вычислительных систем. Эта тема сразу меня увлекла, и я захотел углубиться в дальнейшие оптимизации, но в течение семестра мне не хватало ни времени, ни знаний. Спустя год я решил восполнить этот пробел.

Вначале мы разберем наивную реализацию, поиграемся с интринсиками (intrinsics) и, не теряя переносимости, заставим компилятор генерировать нам SIMD-инструкции. Далее добавим многопоточность и в заключение обесценим все наши старания несколькими строчками на CUDA.

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

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

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

Но мне кажется, что есть очень простой способ устранить циклические ссылки в программе, который можно реализовать практически в любом типизированном языке программирования, конечно, если при этом не использовать все разрешающее ключевое слово unsafe для Rust или оператор reinterpret_cast в случае С++.

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

Сегодня мы рассмотрим, как создать безопасные FFI-интерфейсы в Rust для интеграции с C/C++ библиотеками

Если говорить проще, FFI (foreign function interface — интерфейс вызова внешних функций) – это способ «позаимствовать» функциональность из другого языка. В контексте нашей статьи, с одной стороны у нас Rust, где каждый байт памяти охраняется компилятором, а на другой C++, где свобода обращения с памятью может обернуться утечками или, что еще хуже, непредсказуемым UB (англ. undefined behavior, в ряде источников непредсказуемое поведение). И наша задача – сделать так, чтобы эти два мира не конфликтовали, а работали в унисон.

Mask R-CNN 3D – это расширение знаменитой модели Mask R-CNN для работы с трехмерными данными (объёмными изображениями или облаками точек). Классическая Mask R-CNN предназначена для instance segmentation (сегментации отдельных объектов) на 2D-изображениях и состоит из двух основных частей: (1) сети предложений областей (Region Proposal Network, RPN) и (2) головы (Head) с несколькими выходными ветвями для классификации, регрессии ограничивающих рамок и сегментации масок . В версии 3D эта же концепция перенесена в трехмерное пространство.

Входом модели Mask R-CNN 3D обычно является объёмный данных – например, медицинский 3D снимок (CT/MRI) размером (D×H×W) или облако точек, представляющее 3D-сцену. Backbone-сеть (обычно сверточная нейросеть типа ResNet) извлекает из входных данных многомасштабные признаки. В 3D версии backbone заменяет все 2D-операции (свертки, пулинг) на 3D-аналоги, позволяя обрабатывать объёмные данные напрямую. (Если 3D-данные заданы как облако точек, возможно предварительное преобразование, например, вокселизация пространства или проекция на несколько 2D-плоскостей – об этом подробнее в разделе 6.) Backbone формирует карты признаков – объёмные тензоры с пониженным разрешением, но содержащие высокоуровневую информацию о структуре объектов в сцене.

Далее вступает Region Proposal Network (RPN) – небольшая сеть, скользящая по картам признаков и генерирующая набор предположительных объектов (region proposals) в виде ограничивающих 3D-рамок (прямоугольных параллелепипедов в координатах исходного объёма). RPN использует заранее заданные «якоря» (anchor boxes) – шаблонные 3D-боксы разных размеров и соотношений сторон, размещенные по всей карте признаков . Для каждого такого anchor RPN предсказывает два значения: объектность (есть объект/фон) и смещение рамки (на сколько нужно подвинуть и масштабировать anchor, чтобы точнее охватить объект). После этого выбираются топ-N наиболее перспективных предложений с помощью non-maximum suppression (NMS) – подавления пересекающихся рамок с меньшей оценкой.

Система сборки CMake имеет в арсенале достаточно мощный инструмент - пресеты, шаблоны, называйте как угодно. В данной статье будет рассмотрено применение пресетов на примере модульной библиотеки реализующей функционал engine-а для OpenSSL и описано как перенести опции для кросскомпиляции в пресеты.

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

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

Если вы не готовы писать и поддерживать свою STL, старайтесь, использовать vector, он хотя бы предсказуем по времени на всех платформах. Так вам скажет большинство разработчиков игр на C++, но проблема в том, что vector перераспределяет хранимые объекты в памяти при вставке новых элементов, а также при удалении любого элемента, кроме последнего. Это означает, что указатели на элементы вектора становятся недействительными, и тогда все зависимости и взаимодействия между элементами перестают работать.

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

Идея приложения состоит в демонстрации IoT - интеграция различных устройств, и передача данных по разным протоколам в Edge или Cloud. Допустим, наш автономный механизм работает без подключения к интернету, а нам необходимо сделать замеры поведения движений во времени. Мы подключаемся с помощью смартфона по Bluetooth LE к контроллеру механизма и в течении определенного времени делаем запись. При этом наш смартфон успешно подключается к облачному MQTT-брокеру и передает данные в IoT платформу. Платформа производит аналитику и предоставляет нам результат. А мы в это время на основании полученных данных можем внести требуемые значения характеристик механизма в контроллер по BLE.

В статье Machine learning на ESP32 мы начали разработку проекта распознавания жестов для ESP32. В данной статье продолжим реализацию подключение и отправку данных по BLE и MQTT с помощью Android-устройства. Хотя ESP 32 может напрямую подключаться к Wi-Fi и MQTT, как, например, показано в статье Платформа с web-камерой на ESP32, мы все же реализуем передачу данных по BLE, руководствуясь выше изложенными соображениями.

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

Привет, коллеги и доброжелательные критики! Сегодня я решил отвлечься от своей громоздкой работы, чтобы написать что-то простое, но с изюминкой — калькулятор с графическим интерфейсом на C++20 и SFML. Этот проект — не претензия на что-то грандиозное, а скорее лёгкий эксперимент, чтобы вспомнить, как приятно писать код, который сразу видно на экране. Заодно я поделюсь с вами своими мыслями, подходами и парой советов. Давайте разберём, как я это закрутил и почему выбрал именно SFML.

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

В этом примере используются измерения акселерометра MPU 6050 и машинное обучение (ML) для распознавания трех жестов рукой с помощью ESP32. Данные из сенсора распознаются на микроконтроллере и результат выводится в консоль в виде названия жеста и вероятности результата. Модель ML использует TensorFlow и Keras и обучается на выборке данных, представляющей три различных жеста: "circle" (окружность), "cross" (пересечение) и "pad" (поступательное движение).

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

В следующей части рассмотрим как настроить Bluetooth LE (BLE) на ESP32 и Android устройстве. Передадим квантированный набор ускорений сенсора по BLE. Настроим Модель ML для распознания жестов на Android.

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

Статья будет интересна тем, кто интересуется нетривиальными, но красивыми алгоритмами!

Привет, Хабр! В этой статье я хочу рассказать о своём проекте — библиотеке ProxyOrmModel для Qt, которая упрощает работу с данными в моделях. Если вы когда-нибудь сталкивались с необходимостью фильтровать, сортировать, группировать или агрегировать данные в QAbstractItemModel, то, вероятно, знаете, как это может быть утомительно. Я решил создать инструмент, который делает это проще и удобнее, вдохновившись идеями ORM (Object-Relational Mapping) из мира баз данных. Здесь я поделюсь архитектурой, ключевыми классами и уроками, которые я вынес из разработки.

Контроллер Лампы для Рассады

Умный контроллер освещения на базе ESP32 с управлением через Telegram бот. Проект выходного дня для любителей растениеводства.

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

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

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

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

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

Если разработку под устройства можно сравнить с тёмным лесом, то как в нём не заплутать?

Привет, путник! Меня зовут Денис Малых, я работаю в Яндексе и руковожу разработкой общих компонент для платформы, на которой работают наши устройства. А ещё — я член программного комитета конференции AppsConf, где мы обсуждаем разработку под мобильные ОС. В этой статье поделюсь опытом разработки под нестандартные устройства: чем она принципиально отличается от привычной мобильной разработки, и что нужно уметь, чтобы разрабатывать «умные вещи».

Продолжаем серию «C++, копаем вглубь». Цель этой серии — рассказать максимально подробно о разных особенностях языка, возможно довольно специальных. Это восьмая статья из серии, список предыдущих статей приведен в разделе 6.

C++ относится к языкам со статической типизацией, то есть тип переменных определяется на стадии компиляции, но в ряде случаев компилятору для компиляции без ошибок достаточно знать, что то или иное имя является именем какого-то пользовательского типа (класса, структуры, объединения, перечисления), а полное объявление типа не нужно. В этом случае можно использовать неполное объявление (incomplete declaration), называемое еще упреждающим или предваряющим (forward declaration). Типы с неполным объявлением называются неполными.

Использование неполных объявлений позволяет решить ряд проблем, традиционно свойственных коду, написанному на С++. Отметим следующие:

1. Можно уменьшить количество включений заголовочных файлов в другие файлы проекта, что сокращает время компиляции, снижает замусоривание пространств имен неиспользуемыми именами, предупреждает потенциальные конфликты имен;
2. Можно реализовать решения, полностью разделяющие интерфейс и реализацию (непрозрачные указатели);
3. Можно разрывать циклические зависимости;
4. Можно снизить использование нетипизированных указателей void*, что повышает надежность и читаемость кода.

Грамотное использование неполных объявлений — один из признаков профессионального кода.