В этой статье рассмотрим создание легковесной, типобезопасной библиотеки для ранжирования объектов по множеству критериев с использованием битовых масок. Библиотека bitrank позволяет оценивать объекты, присваивая им битовый ранг, где каждый бит соответствует выполнению определенного правила.
Проблема многокритериального ранжирования
Проблема многокритериального ранжирования заключается в сложности упорядочения альтернатив при наличии нескольких, часто противоречивых показателей. Главная аналитическая трудность здесь связана с тем, что улучшение одного параметра практически всегда ведет к ухудшению другого, как это происходит при поиске баланса между ценой и качеством. Кроме того, исходные данные нередко измеряются в совершенно разных шкалах — от стоимостных и временных величин до субъективных экспертных оценок, что исключает возможность их прямого суммирования.
Практическая реализация многокритериального ранжирования ограничена тремя барьерами: непрозрачностью, сложностью калибровки и аппаратными издержками. Свёртка разнородных метрик лишает оценку прозрачности, из-за чего нельзя объяснить причину полученного балла. Ручная настройка весов требует трудозатрат экспертов и вносит субъективность. Масштабирование упирается в производительность: вычисления с плавающей точкой на аппаратном уровне медленнее целочисленных.
double score = importance * 0.3 + priority * 0.2 + penalty * 0.5;
Иной подход: битовые маски
Использование битовых масок для ранжирования дает высокую скорость за счет побитовых операций на уровне процессора и автоматически гарантирует сортировку по жестким приоритетам. В этой математике любое старшее правило всегда перевешивает любую сумму младших правил, что исключает размытие приоритетов, но не позволяет сделать два правила равнозначными в одной битовой цепочке. Другое ограничение — лимит в 32 или 64 правила для стандартных типов данных, после чего приходится переходить на массивы битов вроде BitSet. На практике эту схему часто модернизируют до гибридной: битовая маска определяет общую группу приоритета, а внутри нее объекты сортируются по обычным метрикам вроде цены или расстояния. Также под правила одинаковой важности можно выделять многобитовые слоты, записывая туда обычные числа, например количество совпавших тегов. Для гибкости маски выносят в динамическую конфигурацию, что позволяет менять логику на лету без перекомпиляции кода.
Архитектура библиотеки
Matchers (Правила)
1. Генерация уникальных битов
Сердце системы является функция next_bit(), которая автоматически назначает уникальные биты:
inline uint64_t next_bit() { static uint64_t bit = 1; uint64_t current = bit; bit <<= 1; return current;}
Принцип работы функции: static переменная хранит текущий бит между вызовами. При первом вызове возвращается 1 (бит 0). При втором — 2 (бит 1). При третьем — 4 (бит 2). И так далее до 2^63. Максимальное количество правил ограничено 64 (размер uint64_t). В большинстве практических задач это более чем достаточно.
Пояснение: Статическая переменная в функции — это простой способ реализовать глобальный счетчик без загрязнения глобального пространства имен. Она инициализируется при первом вызове и сохраняет значение между вызовами.
2. Базовый класс правил — field_matcher
Класс field_matcher проверяет равенство поля объекта ожидаемому значению:
template<typename T, typename FieldType, typename ValueType>class field_matcher { FieldType T::* field; ValueType expected; uint64_t bit; bool reverse;public: field_matcher(FieldType T::* f, const ValueType& v, uint64_t b, bool rev = false) : field(f), expected(v), bit(b), reverse(rev) { } bool match(const T& obj) const { bool ok = (obj.*field) == expected; return reverse ? !ok : ok; } uint64_t weight() const { return bit; }};
Разбор класса:
FieldType T::* field; — это указатель на член класса типа FieldType
Справка по поводу странного синтаксиса
Указатель на член класса — стандартная возможность C++, позволяющая хранить «ссылку» на поле объекта, но лучше писать более читаемые альтернативы, если это не вредит производительности
Флаг reverse позволяет создавать инвертированные правила
Пример использования:
// Использование указателя на член классаauto rule = field_matcher<Price, int, int>(&Price::importance, 10, 1);// Использование флага reverseauto not_penalty = bitrank::make_field_matcher(&Price::penalty, 0, true);
3. Правила для массивов — array_matcher
Класс array_matcher проверяет наличие значения в контейнере:
template<typename T, typename FieldType, typename ValueType>class array_matcher { std::vector<FieldType> T::* field; ValueType expected; uint64_t bit; bool reverse;public: array_matcher(std::vector<FieldType> T::* f, const ValueType& v, uint64_t b, bool rev = false) : field(f), expected(v), bit(b), reverse(rev) { } bool match(const T& obj) const { const auto& arr = obj.*field; bool ok = std::find(arr.begin(), arr.end(), expected) != arr.end(); return reverse ? !ok : ok; } uint64_t weight() const { return bit; }};
Класс использует указатель на поле типа std::vector (именно контейнер как массив), использование std::find для поиска в контейнере, и работает с типа поддерживающий operator==
Пример использования:
auto premium_rule = bitrank::make_array_matcher // массив данных - std::vector<T> &Price::tags, // искомое значение std::string("premium") );
4. Правила с произвольной логикой — predicate_matcher
Это наиболее гибкий класс, принимающий любую функцию-предикат:
template<typename T, typename Predicate>class predicate_matcher { Predicate pred; uint64_t bit; bool reverse;public: predicate_matcher(Predicate p, uint64_t b, bool rev = false) : pred(p), bit(b), reverse(rev) { } bool match(const T& obj) const { bool ok = pred(obj); return reverse ? !ok : ok; } uint64_t weight() const { return bit; }};
Пример использования:
auto expensive_rule = bitrank::make_predicate_matcher( [](const Price& p) { return p.importance > 5 && p.priority < 3; });auto not_expensive_rule = bitrank::make_predicate_matcher( [](const Price& p) { return p.importance > 5; }, // Инвертированное условие true);
Преимущество заключается в реализации любой бизнес-логику без изменения библиотеки
Функции-фабрики
Для удобства создания правил реализованы функции-фабрики:
template<typename T, typename FieldType, typename ValueType>auto make_field_matcher(FieldType T::* field, const ValueType& value, bool reverse = false) { return field_matcher<T, FieldType, ValueType>(field, value, next_bit(), reverse);}template<typename T, typename FieldType, typename ValueType>auto make_array_matcher(std::vector<FieldType> T::* field, const ValueType& value, bool reverse = false) { return array_matcher<T, FieldType, ValueType>(field, value, next_bit(), reverse);}template<typename T, typename Predicate>auto make_predicate_matcher(Predicate pred, bool reverse = false) { return predicate_matcher<T, Predicate>(pred, next_bit(), reverse);}
Использование auto позволяет компилятору вывести точный тип возвращаемого значения. Это делает код более читаемым и избавляет от необходимости явно указывать шаблонные параметры.
Структура ранжированного объекта
template<typename T>struct ranked_object { T object; uint64_t rank; bool operator<(const ranked_object& other) const { return rank > other.rank; }};
Класс хранит уникальный объект и его ранг который будет позволять декодировать его. Переопределение оператора < в системе рангов считается лучшим если соответствует большему количеству правил
Ядро системы — apply_rules
Рассмотрим поподробнее класс:
template<typename Container, typename... Rules>std::vector<ranked_object<typename Container::value_type>>apply_rules(const Container& container, const Rules&... rules) { using T = typename Container::value_type; auto rule_tuple = std::make_tuple(rules...); constexpr size_t rule_count = sizeof...(Rules); std::vector<ranked_object<T>> result; result.reserve(container.size()); for (const auto& obj : container) { uint64_t rank = 0; [&] <std::size_t... Is>(std::index_sequence<Is...>) { ((rank |= (std::get<Is>(rule_tuple).match(obj) ? std::get<Is>(rule_tuple).weight() : 0)), ...); }(std::index_sequence_for<Rules...>{}); result.push_back({ obj, rank }); } std::sort(result.begin(), result.end(), [](const auto& a, const auto& b) { return a.rank > b.rank; }); return result;}
Вариативные шаблоны (Variadic Templates):
template<typename Container, typename... Rules>
typename... Rules означает, что функция может принимать любое количество правил разных типов.
// Создание кортежа:auto rule_tuple = std::make_tuple(rules...);
Все правила упаковываются в std::tuple для удобного доступа по индексам
Fold expression (C++17):
((rank |= (std::get<Is>(rule_tuple).match(obj) ? std::get<Is>(rule_tuple).weight() : 0)), ...);
Это оператор свертки, появившийся в C++17. Раскрывается в последовательность операций:
rank |= (rule0.match(obj) ? rule0.weight() : 0);rank |= (rule1.match(obj) ? rule1.weight() : 0);rank |= (rule2.match(obj) ? rule2.weight() : 0);
std::index_sequence_for
[&] <std::size_t... Is>(std::index_sequence<Is...>) { /* ....... */}(std::index_sequence_for<Rules...>{});
Эта библиотечная функция создает последовательность индексов 0, 1, 2, -> N-1, где N — количество правил, позволяющая обращаться к элементам кортежа по индексам.
Сортировка:
std::sort(result.begin(), result.end(), [](const auto& a, const auto& b) { return a.rank > b.rank; });
Стандартная сортировка по убыванию ранга
Фильтрация нулевых рангов
template<typename Container, typename... Rules>std::vector<ranked_object<typename Container::value_type>>apply_rules_sort_filtered(const Container& container, const Rules&... rules) { auto all = apply_rules(container, rules...); all.erase( std::remove_if(all.begin(), all.end(), [](const auto& item) { return item.rank == 0; }), all.end() ); return all;}
Полный пример использования
#pragma once#include <vector>#include <algorithm>#include <cstdint>#include <tuple>#include <iostream>#include <string>namespace bitrank { template<typename T, typename FieldType, typename ValueType> class field_matcher { FieldType T::* field; ValueType expected; uint64_t bit; bool reverse; public: field_matcher(FieldType T::* f, const ValueType& v, uint64_t b, bool rev = false) : field(f), expected(v), bit(b), reverse(rev) { } bool match(const T& obj) const { bool ok = (obj.*field) == expected; return reverse ? !ok : ok; } uint64_t weight() const { return bit; } }; template<typename T, typename FieldType, typename ValueType> class array_matcher { std::vector<FieldType> T::* field; ValueType expected; uint64_t bit; bool reverse; public: array_matcher(std::vector<FieldType> T::* f, const ValueType& v, uint64_t b, bool rev = false) : field(f), expected(v), bit(b), reverse(rev) { } bool match(const T& obj) const { const auto& arr = obj.*field; bool ok = std::find(arr.begin(), arr.end(), expected) != arr.end(); return reverse ? !ok : ok; } uint64_t weight() const { return bit; } }; template<typename T, typename Predicate> class predicate_matcher { Predicate pred; uint64_t bit; bool reverse; public: predicate_matcher(Predicate p, uint64_t b, bool rev = false) : pred(p), bit(b), reverse(rev) { } bool match(const T& obj) const { bool ok = pred(obj); return reverse ? !ok : ok; } uint64_t weight() const { return bit; } }; inline uint64_t next_bit() { static uint64_t bit = 1; uint64_t current = bit; bit <<= 1; return current; } template<typename T, typename FieldType, typename ValueType> auto make_field_matcher(FieldType T::* field, const ValueType& value, bool reverse = false) { return field_matcher<T, FieldType, ValueType>(field, value, next_bit(), reverse); } template<typename T, typename FieldType, typename ValueType> auto make_array_matcher(std::vector<FieldType> T::* field, const ValueType& value, bool reverse = false) { return array_matcher<T, FieldType, ValueType>(field, value, next_bit(), reverse); } template<typename T, typename Predicate> auto make_predicate_matcher(Predicate pred, bool reverse = false) { return predicate_matcher<T, Predicate>(pred, next_bit(), reverse); } template<typename T> struct ranked_object { T object; uint64_t rank; bool operator<(const ranked_object& other) const { return rank > other.rank; } }; template<typename Container, typename... Rules> std::vector<ranked_object<typename Container::value_type>> apply_rules(const Container& container, const Rules&... rules) { using T = typename Container::value_type; auto rule_tuple = std::make_tuple(rules...); constexpr size_t rule_count = sizeof...(Rules); std::vector<ranked_object<T>> result; result.reserve(container.size()); for (const auto& obj : container) { uint64_t rank = 0; [&] <std::size_t... Is>(std::index_sequence<Is...>) { ((rank |= (std::get<Is>(rule_tuple).match(obj) ? std::get<Is>(rule_tuple).weight() : 0)), ...); }(std::index_sequence_for<Rules...>{}); result.push_back({ obj, rank }); } std::sort(result.begin(), result.end(), [](const auto& a, const auto& b) { return a.rank > b.rank; }); return result; } template<typename Container, typename... Rules> std::vector<ranked_object<typename Container::value_type>> apply_rules_sort_filtered(const Container& container, const Rules&... rules) { auto all = apply_rules(container, rules...); all.erase( std::remove_if(all.begin(), all.end(), [](const auto& item) { return item.rank == 0; }), all.end() ); return all; }} // namespace bitrank// Структураstruct Price { std::string name; int importance; int priority; int penalty; std::vector<std::string> tags; std::vector<int> categories;};// Тест-данныеstd::vector<Price> create_test_data() { return { {"Product A", 10, 5, 0, {"premium", "new"}, {1, 2}}, {"Product B", 7, 8, 3, {"standard"}, {2, 3}}, {"Product C", 10, 7, 1, {"premium", "sale"}, {1, 3}}, {"Product D", 3, 2, 10, {"old"}, {4}}, {"Product E", 10, 9, 0, {"premium", "new", "top"}, {1, 2, 5}} };};int main() { auto prices = create_test_data(); // Правила ранжирования auto rule1 = bitrank::make_field_matcher(&Price::importance, 10); auto rule2 = bitrank::make_field_matcher(&Price::priority, 7); auto rule3 = bitrank::make_field_matcher(&Price::penalty, 0); auto rule4 = bitrank::make_array_matcher(&Price::tags, std::string("premium")); auto rule5 = bitrank::make_array_matcher(&Price::categories, 1); // Применение правил auto ranked = bitrank::apply_rules(prices, rule1, rule2, rule3, rule4, rule5); std::cout << "=== Ранжированные товары ===\n"; for (const auto& item : ranked) { std::cout << item.object.name << " | Rank: 0x" << std::hex << item.rank << std::dec << "\n"; } // Получение только релевантных товаров auto filtered = bitrank::apply_rules_sort_filtered( prices, rule1, rule2, rule3, rule4, rule5 ); // Декодирование std::cout << "\n=== Декодирование ===\n"; for (const auto& item : filtered) { std::cout << item.object.name << " (0x" << std::hex << item.rank << std::dec << "):"; if (item.rank & 0x1) std::cout << " importance=10"; if (item.rank & 0x2) std::cout << " priority=7"; if (item.rank & 0x4) std::cout << " penalty=0"; if (item.rank & 0x8) std::cout << " has 'premium'"; if (item.rank & 0x10) std::cout << " has category 1"; std::cout << "\n"; } return 0;}
Заключение
Библиотека bitrank решает задачу многокритериального ранжирования в C++20 за счет использования битовых операций и шаблонов без виртуальных вызовов, для высокой производительности. Данный подход оптимален для систем поиска, фильтрации, рекомендательных алгоритмов, A/B-тестирования и быстрого прототипирования. Однако библиотека не подходит для задач, где используется более 64 критериев, требуется поддержка отрицательных весов или необходим точный скоринг с плавающими коэффициентами вместо жестких битовых приоритетов.
Ссылка на GitHub
ссылка на оригинал статьи https://habr.com/ru/articles/1064706/