Search
Write a publication
Pull to refresh
78
0.1
Роман @RomeoGolf

инженер-программист

Send message

Описание алгоритмов сортировки и сравнение их производительности

Reading time24 min
Views719K

Вступление


На эту тему написано уже немало статей. Однако я еще не видел статьи, в которой сравниваются все основные сортировки на большом числе тестов разного типа и размера. Кроме того, далеко не везде выложены реализации и описание набора тестов. Это приводит к тому, что могут возникнуть сомнения в правильности исследования. Однако цель моей работы состоит не только в том, чтобы определить, какие сортировки работают быстрее всего (в целом это и так известно). В первую очередь мне было интересно исследовать алгоритмы, оптимизировать их, чтобы они работали как можно быстрее. Работая над этим, мне удалось придумать эффективную формулу для сортировки Шелла.

Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.
Читать дальше →

Отсутствие динамической аллокации в embedded мире

Level of difficultyEasy
Reading time5 min
Views6.2K

Когда мы разрабатываем под embedded, нам приходится сталкиваться с такими флагами компиляции как -nostdlib -fno-exceptions -fno-rtti.

Во многих средах нет malloc/free (new/delete) и вообще нет встроенного выделения памяти.

Использование «больших» стандартных контейнеров C++ (например, std::vector) нередко исключено

В результате приходится решать задачу «ручного» управления памятью. Ниже рассмотрим два подхода:

Читать далее

Debian 12, QEMU, и сетевые мосты (bridge) в 2025

Level of difficultyMedium
Reading time7 min
Views5.1K

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

Стоит знать перед началом
- Чем коммутатор отличается от маршрутизатора
- Первые 3 уровня модели OSI
- Хотя бы примерно понимать как работает коммутатор
Без этих знаний возможно у Вас не получится понять и правильно использовать информацию из этой статьи.
Сетевые мосты нужны чтобы виртуальная машина могла взаимодействовать с локальными сетями а не просто иметь доступ в Интернет. Если на Вашей виртуальной машине нужен только Интернет, используйте в QEMU режим сети "user".

Читать далее

Как собрать Docker-образ, который можно запускать в проде (а не только у себя на ноуте)

Level of difficultyEasy
Reading time4 min
Views31K

Если ты пишешь Dockerfile, скорее всего, он работает. Но вопрос не в том, работает ли. Вопрос в другом: будет ли он работать через неделю, на другом сервере, в CI/CD, на чужом железе — и будет ли это безопасно?

Читать далее

Руководство по сборке Qt под Windows из исходников с MinGW

Level of difficultyEasy
Reading time10 min
Views3.8K

Официальный способ установки готовых бинарников Qt - через онлайн инсталлятор. Однако он требует обязательной регистрации. Да еще и недоступен на территории РФ. Есть и другие способы получить бинарники, или собрать с компилятором от Microsoft, однако не всегда эти способы приемлемы. Сборка из исходников под Windows может оказаться несколько нетривиальна для новичков, потому сделал небольшую инструкцию по сборке Qt 5 и Qt 6. А так же рассмотрена базовая настройка QT Creator.

Читать далее

Огромный гайд по настройке рабочего окружения: Linux, VScode, Python

Level of difficultyEasy
Reading time29 min
Views59K

Привет всем!

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

Я люблю и одновременно ненавижу статьи-обзоры в стиле «10 программ для {whatever}». Ненавижу — потому что их очень легко делать, вбил в гугл «программа для X», взял первые 10 ссылок, статья готова. Я называю такие статьи «лёгкий рейтинг». А люблю я их за то, что даже если 9 пунктов — чушь полная, то десятый, как правило, годный, я узнаю что-то новое, это что-то облегчает мне жизнь и позволяет мне быть более продуктивным.

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

Статья получилась ОГРОМНАЯ, и у меня был большой соблазн разбить её на сотню статей поменьше, чтобы в каждой ставить ссылки на свой телеграм-канал и получать гонорар за каждую по отдельности. Но я не буду. Пусть знания будут сгруппированы вместе. Welcome!

Читать далее

Настройка SSH для коммитов в репозиторий

Level of difficultyEasy
Reading time4 min
Views2.5K

Итак вам надо клонировать репозиторий с компанейского репозитория и git просит какие-то непонятные пароли.
Знакома ситуация?

В этой заметке я написал как настроить ssh ключи.

Читать далее

Лаконичный макрос defer для C++17

Level of difficultyMedium
Reading time5 min
Views6.3K

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

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

Читать далее

Плоские контейнеры в C++23

Level of difficultyMedium
Reading time22 min
Views6.9K

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

Читать далее

Что будет, если заинлайнить всё

Reading time25 min
Views13K

Усаживайтесь поудобнее, ребята! Сегодня мы с вами разберём следующий увлекательный вопрос: что будет, если заинлайнить вообще всё?

Если вы пока не знакомы с техникой встраивания (inlining) то примите к сведению, что в сообществе специалистов по разработке компиляторов многие, в том числе очень авторитетные фигуры (например, Чендлер Каррут) считают этот приём наиважнейшим при оптимизации компиляторов. Подробнее о том, как устроено встраивание, рассказано здесь — мы беззастенчиво хвалимся той презентацией, с которой выступили перед участниками конференции LLVM Developers' Meeting по межпроцедурной оптимизации. Я рассказывал о встраивании и очень рекомендую вам посмотреть хотя бы первые 6 минут. В этом видео я рассказываю, почему встраивание — очень простое преобразование, а вот тут вашему вниманию предлагается реализация встраивания, предложенная великим Крисом Латтнером уже около 20 лет назад — в ней всего около 200 строк кода. К сожалению, сегодня даже само преобразование пропорционально выросло: в качестве примера взгляните хотя бы на InlineFunction.cpp.

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

Читать далее

Ссылки и указатели в C++

Level of difficultyEasy
Reading time6 min
Views9.9K

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

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

Читать далее

Как ускорить сложение и вычитание при помощи 2^51

Level of difficultyEasy
Reading time8 min
Views10K

Помните, как долго выполняется сложение на бумаге?

¹¹ ¹
6876
+ 3406
------
10282

Начиная с единиц, мы складываем 6 + 6 = 12, записываем 2 и переносим 1. Затем пошагово двигаемся влево, пока складываемые разряды не закончатся.

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

Но сначала я задам вопрос: почему сложение столбиком мы начинаем с самого младшего разряда? Почему бы не начать слева?

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

Читать далее

Образцовый джун

Level of difficultyEasy
Reading time6 min
Views5.7K

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

Читать далее

Как СМИ, консультанты, инфоцыгане и прочие провоцируют переработки и корпоративную шизу. Часть 4

Level of difficultyEasy
Reading time42 min
Views16K

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

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

Вы представляете себе, насколько разрушительны для общества современные медиа и СМИ?

Знаете ли вы, что консультанты настолько любят переработки, что буквально не приносят никакой долгосрочной пользы для бизнеса?

Что инфоцыгане провоцируют иррациональную веру в простые, быстрые и работающие техники?

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

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

Найти простые пути к корпоративной шизе

Девять desktop- и embedded-систем для создания собственного Linux-дистрибутива: какой выбрать для вашего проекта

Level of difficultyMedium
Reading time20 min
Views3.5K

Привет, Хабр! На связи команда авторов совместной лаборатории ЛЭТИ и YADRO. Часто компаниям нужно контролировать программное обеспечение в инфраструктуре, включая серверы и ПК сотрудников. А еще — управлять версиями ПО из пакетной базы дистрибутивов, особенно для частных систем, где требуются определенные версии. Здесь компании могут либо довериться стороннему вендору, либо разработать собственный дистрибутив.

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

В этой статье мы рассмотрим технологии создания загрузочных образов и инфраструктуры для поддержки собственных дистрибутивов на базе Linux, исследуем системы сборки, в том числе Yocto Project, Buildroot и Open Build Service, а также подскажем, как выбрать лучшее для вашего проекта. 

Читать далее

Дискретное преобразование Фурье в живых картинках для девятиклассников

Level of difficultyMedium
Reading time19 min
Views30K

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

В виртуальную лабораторию!

Краткая история бесконечности. Часть 1

Level of difficultyEasy
Reading time9 min
Views9.4K

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

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

Читать далее

Контейнер с нуля

Level of difficultyHard
Reading time9 min
Views3.6K

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

Читать далее

Information

Rating
3,636-th
Location
Свердловская обл., Россия
Date of birth
Registered
Activity