Бла-бла-бла

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

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

Вчера меня озарило после разговора с Пашей Бейзманом, выступавшим на днях с докладом на HighLoad++. Битовые операции!!! Да, я прекрасно понимаю мощь битовых операций, но я их неправильно готовил ;) Результаты тестов превзошли мои самые оптимистичные ожидания.

Недавно, на хабрахабре была опубликована статья, целиком и полностью посвященная диаграммам Вороного. В статье автор подробно описывает алгоритм Форчуна, применяемый для построения Диаграммы Вороного за O(n*log(n)). Стоит отметить, что описание этого алгоритма не раз появлялось в рунете, в то время как о других алгоритмах (с той же асимптотикой) рассказано ровным счетом ничего. Данная статья исправляет это недоразумение, а также является отличным дополнением к уже опубликованному ранее материалу.

Ниже я расскажу о алгоритме 'разделяй и властвуй' построения диаграммы Вороного за O(n*log(n)), а также, основываясь на своем практическом опыте, о по-настоящему крутых штуках, в которых это применимо. Вообще, алгоритмы типа 'разделяй и властвуй' являются своего рода классикой программирования (думаю, про сортировку данным методом слышал каждый программист), хорошо параллелятся и легко читаются (если, конечно, знать основную идею алгоритма).

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

Кому интересно, добро пожаловать под кат!

Хочу представить небольшое готовое решение для тех, кому может понадобится написать большой (или не очень) кусок кода, который программа должна выполнить ровно 1 раз; причём поместить его может потребоваться куда угодно (в пределах разумного и правил синтаксиса C++). Если потребность в этом возникает чаще, чем пару раз во всём проекте, хорошо бы иметь на этот случай хоть какое-то более-менее работающее и, по возможности, не очень костыльное решение.

Постановка задачи

Есть двигатель постоянного тока. Задача — разработать, собрать и протестировать устройство, позволяющиее реализовать контур тока применительно к этому двигателю. Желаемое время переходного процесса на застопоренном двигателе (без противо-ЭДС) — не более 10мс. Интерфес связи с внешним управляющим контроллером — SPI.

Двигатель постоянного тока, коллекторный, максимальное напряжение 24В, рабочий ток до 5А.

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

Я разбил этот текст на две статьи:

• 1. Измерение сопротивления и индуктивности двигателя
• 2. Разработка управляющего контура

Вот так выглядит макет управляющего железа:

Преамбула

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

Интервью с Qt

— Мне нужно чтобы ты понимал мой enum.

Около двух месяцев назад я написал статью о проверке компилятора GCC с помощью анализатора PVS-Studio. Идея статьи была следующая: предупреждения GCC — это хорошо, но недостаточно. Надо использовать специализированные инструменты анализа кода, например, PVS-Studio. В качестве подтверждения я показал ошибки, которые PVS-Studio смог найти в коде GCC. Ряд читателей заметили, что качество кода GCC и его диагностики так себе, в то время как компилятор Clang современен, качественен, свеж и молод. В общем Clang — это ого-го! Что ж, значит пришло время мне проверить с помощью PVS-Studio проект LLVM.

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

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

Структура программы

Программа состоит из трех частей

• набор вспомогательных функций и классов — mycrypto.cpp mycrypto.hpp
• блочный шифр «Кузнечик» — Kuznyechik.cpp Kuznyechik.hpp
• режим шифрования Cipher Feed Back — modes.hpp

В сети огромное количество площадок формата Q&A где задаются вопросы из разряда:

• Предложите С++ логер? (C++ logging framework suggestions)
• Какой наиболее эффективный потоко-безопасный С++ логер? (What is the most efficient thread-safe C++ logger)
• Библиотека логирования для игр (Logging library for c games)
• Асинхронный потоко-безопасный С++ логер? (Asynchronous thread-safe logging in C++)

Люди делятся своим опытом и знаниями, но формат таких площадок позволяет лишь показать личные предпочтения отвечающего. К примеру, одним из самых производительных логеров чаще всего называют Pantheios, который даже по тестам производителя тратит больше 100 секунд на запись 1M строк лога, на современном железе это около 30 секунд, быстро ли это?

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

Казалось бы, Chromium был рассмотрен нами неоднократно. Внимательный читатель задастся логичным вопросом: «Зачем нужна еще одна проверка? Разве было недостаточно?». Бесспорно, код Chromium отличается чистотой, в чем мы убеждались каждый раз при проверке, однако ошибки неизбежно продолжают выявляться. Повторные проверки хорошо демонстрируют, что чем чаще будет применяться статический анализ, тем лучше. Хорошо, если проект проверяется каждый день. Ещё лучше, если анализатор используется программистами непосредственно при работе (автоматический анализ изменённого кода).

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

Предыстория и проблематика

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

Получилось похоже на MS Visio с определенной степенью кастомизации и плагинизации. Никаких технических сложностей здесь нету, однако есть ряд особенностей.

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

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

В-третьих, когда я сделал все, что хотел, и показал результаты другу (который даже не программист), то он потыкал и сказал, что неплохо бы сделать Ctrl+Z. Я загорелся идеей, но вот реализовать это оказалось не такой тривиальной задачей. В этой статье я опишу, к чему пришел в итоге.

В предыдущей статье про декларативный JSON-сериализатор я рассказал, как с помощью шаблонов C++ можно описывать структуры данных и сериализовать их. Это очень удобно, т.к. не только сокращает размер кода, но и минимизирует количество возможных ошибок.Концепция — если код компилируется, то он работает. Примерно такой же подход применен и в wjrpc, о которой речь пойдет в этой статье. Но поскольку wjrpc “выдран” из фреймворка, под интерфейсы которого он был разработан, я также затрону вопросы архитектуры и асинхронных интерфейсов.

Свершилось! Сегодня мы выпустили публичную версию анализатора PVS-Studio для Linux. Теперь разработчики Linux приложений получат новое мощное оружие для борьбы с багами в коде. Призываем разнести эту новость по миру. Расскажите своим коллегам по работе, напишите в Twitter и Facebook! Да будут программы надёжней и стабильней!

Не буду сильно углубляться в теорию. Что такое частичное применение легко найти в интернете. В том числе на Википедии.

Если кратко, то это механизм, позволяющий зафиксировать k аргументов функции от n аргументов, сделав из неё функцию от (n - k) аргументов.

// Пусть имеется функция f от четырёх аргументов:
int f (int a, int b, int c, int d)
{
    return a + b + c + d;
}

// Фиксируем первые два аргумента:
auto g = part(f, 1, 2); // 1 + 2 + ...

// Добрасываем оставшиеся два:
assert(g(3, 4) == 10); // ... + 3 + 4 = 10

На эту тему уже существует масса публикаций, в том числе и на Хабре:

1. C++ Variadic templates. Каррирование и частичное применение
2. Частичное применение и каррирование в C++
3. Каррируем на C++

А ветка "How should I make function curry?" на stackoverflow — просто кладезь для тех, кто впервые сталкивается с этой темой.

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

Замечательный факт №1. В упомянутых статьях присутствуют все техники, которые нужны для реализации правильного (по моему мнению) частичного применения.

Надо только всё внимательно проанализировать и сложить кубики в правильном порядке. Именно этим я и собираюсь заняться в данной статье.

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

В предыдущем уроке мы кратко коснулись темы “поверхностных шейдеров” и того, как их использовать. В данном уроке мы рассмотрим шейдеры подробнее и в частности шейдерный язык OpenGL (OpenGL Shading Language).

В этой статье мы рассмотрим один из вариантов реализации поведенческого шаблона проектирования Acyclic Visitor без ипользования RTTI.

Что такое филиппинский кроссворд.

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

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

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

25 октября 2016 года Майкл Фезерс, Director of R7K Research & Conveyance и автор книги «Working Effectively with Legacy Code», выступит на uDev Tech Events с лекцией на тему «Micro Refactoring and Macro Refactoring: Strategies and Techniques».

Эта статья полностью посвящена KD-Деревьям: я описываю тонкости построения KD-Деревьев, тонкости реализации функций поиска 'ближнего' в KD-Дереве, а также возможные 'подводные камни', которые возникают в процессе решения тех или иных подзадач алгоритма. Дабы не запутывать читателя терминологией(плоскость, гипер-плоскость и т.п), да и вообще для удобства, полагается что основное действо разворачивается в трехмерном пространстве. Однако же, где нужно я отмечаю, что мы работаем в пространстве другой размерности. По моему мнению статья будет полезна как программистам, так и всем тем, кто заинтересован в изучении алгоритмов: кто-то найдет для себя что-то новое, а кто-то просто повторит материал и возможно, в комментариях дополнит статью. В любом случае, прошу всех под кат.

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

Есть база пользователей 10 миллионов:

class User{
 int id; 
 time_t birthday; // дата рождения
 int gender;      // пол
 int city_id;     // место проживания
 time_t time_reg; // дата регистрации
};

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

• город;
• город, пол;
• пол, возраст.

Данные выдачи должны быть отсортированы по дате регистрации пользователей, и выдаваться постранично по 100 пользователей.

Подсказка 1: СУБД не даст нужной скорости.
Подсказка 2: Вспомнить сложность операций со множествами, сложность стандартных алгоритмов.
Подсказка 3: Проверить время поиска реализованного алгоритма, неплохой результат это порядка 0.005 сек.