Использовать битовые массивы?

Question

Представьте, что есть фиксированный и постоянный набор «опций» (например, навыков).Каждый объект (например, человек) может иметь или не иметь никаких опций.

Должен ли я вести список опций члена для каждого объекта и заполнять его опциями?

ИЛИ:

Является ли более эффективным (более быстрым) использование битового массива, в котором каждый бит представляет статус выбранной (или не взятой) соответствующей опции?более конкретно, список навыков - это вектор строк (имен опций), который определенно короче, чем 256. Цель состоит в том, чтобы программа работала как можно быстрее (без проблем с памятью).

Answer 1

Это скорее зависит.Если число вариантов невелико, используйте несколько bool членов для их представления.Если список становится большим, то оба ваших варианта становятся жизнеспособными:

• битовый набор (который соответствует enum для символического представления параметров) занимает постоянный и очень маленький объем пространства, иполучение определенного параметра занимает O (1) времени;
• список параметров, или, скорее, std::set или unordered_set из них, может быть более экономичным, но только если количество опций огромно, и ожидается, что для каждого объекта будет установлено очень небольшое их число.

В случае сомнений используйте либо группу bool членов, либоbitset.Только если профилирование показывает, что сохранение параметров становится бременем, рассмотрите динамический список или представление набора (и даже в этом случае вам может потребоваться пересмотреть свой дизайн).Варианты, bitset будет занимать максимум 64 байта, что определенно превзойдет любой список или заданное представление с точки зрения памяти и вероятной скорости.Группа bool с или даже массив unsigned char могут все еще быть быстрее, потому что доступ к байту обычно быстрее, чем доступ к биту.Но копирование структуры будет медленнее, поэтому попробуйте несколько вариантов и оцените результат.YMMV.

Answer 2

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

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

Answer 3

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