Реализация множеств при помощи характеристических векторов

Предположим, в академической группе числится не более 32 студентов и их состав не меняется в течение семестра (вполне допустимое для типичного случая ограничение). Смоделировать множество студентов, сдавших тот или иной зачет, можно более оптимальным образом, воспользовавшись простой структурой информации. Для хранения факта сдачи конкретным студентом зачета достаточно 1 бита - сдал или не сдал. Представляется возможным компактно хранить данную информацию внутри переменной целого типа, воспользовавшись побитовыми операциями. Такую структуру данных принято называть характеристическим вектором. При этом, каждому студенту будет соответствовать собственный бит в числе:

unsigned intg_studentPassData;

Допустим студент под номером X в списке сдал зачет, запишем данную информацию в множество:

// битовая маска, содержащая 1 в бите X-1, остальные биты 0

g_studentPassData |= 1 << ( X - 1 );

Если требуется узнать, сдал ли зачет студент под номером Y, также применяем битовые маски

if( g_studentPassData & ( 1 << ( Y - 1 ) ) )

….

Предположим, выявлен плагиат, и преподаватель аннулировал сдачу зачета студентом Z:

g_studentPassData &= ~( 1 << ( Z - 1 ) );

Либо выявлен чудовищный обман, и деканат аннулировал результаты всей группы:

g_studentPassData = 0;

Представляется возможным реализовать подобную идею для множеств, содержащих и более 32 элементов. Во-первых, существуют 64-битные типы (например, __int64 в Visual C++ или long long в GCC). Во-вторых, можно получить множество и с большим максимальным количеством элементов, если реализовать собственный тип для больших чисел.

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

Пусть имеется информация о сдаче группой двух разных зачетов:

unsigned intg_studentPassData1;

unsigned intg_studentPassData2;

Множество студентов, получивших оба зачета (INTERSECT), можно получить так:

unsigned intg_studentsWith2Passes = g_studentPassData1 & g_studentPassData2;

Множество студентов, сдавших хотя бы один зачет (UNION), можно получить так:

unsigned intg_studentsWithAtLeast1Pass = g_studentPassData1 | g_studentPassData2;

Множество студентов, сдавших первый зачет, но не сдавших второй зачет (DIFFERENCE):

unsigned intg_studentsWithPass1ButWithoutPass2 =

g_studentPassData1 & ~( g_studentPassData2 );

Множество студентов, сдавших только один зачет - первый или второй (SYMMETRIC DIFFERENСE):

unsigned intg_studentsWithExactly1Pass = g_studentPassData1 ^ g_studentPassData2;

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

Выводы

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