Вот несколько компромиссов, которые вы можете сделать. Предположим, что у вас есть два набора элементов, S и T, взятых из юниверса U. Мы хотим определить, является ли S≥T. В одном из приведенных примеров мы имеем
S = {1,2,3,4}
Т = {3,4,5}
U = {1,2,3,4,5}
1. Сортированные списки (или сбалансированное дерево поиска)
Метод, предложенный большинством авторов. Если у вас уже есть отсортированные списки или вы не заботитесь о времени, которое требуется для их создания (скажем, вы делаете это не часто), то этот алгоритм в основном линейный по времени и пространству. Обычно это лучший вариант.
(Чтобы быть справедливым по отношению к другим вариантам здесь, временные и пространственные границы должны фактически содержать факторы «Log | U |» в соответствующих местах, но это обычно не является релевантным)
Структуры данных : отсортированный список для каждого из S и T. Или сбалансированное дерево поиска (например, дерево AVL, красно-черное дерево, дерево B +), которое можно перебирать в постоянном пространстве.
Алгоритм : Для каждого элемента в T по порядку ищите S линейно для этого элемента. Помните, где вы остановили каждый поиск, и начните следующий поиск там. Если каждый поиск успешен, то S≥T.
Сложность времени : около O ( | S | Log | S | + | T | Log | T | ) для создания отсортированных списков, O ( max (| S |, | T |) ) для сравнения.
Пространственная сложность : около O ( | S | + | T | )
Пример (C ++)
#include <set>
#include <algorithm>
std::set<int> create_S()
{
std::set<int> S;
// note: std::set will put these in order internally
S.insert(3);
S.insert(2);
S.insert(4);
S.insert(1);
return S;
}
std::set<int> create_T()
{
std::set<int> T;
// note std::set will put these in order internally
T.insert(4);
T.insert(3);
T.insert(5);
return T;
}
int main()
{
std::set<int> S=create_S();
std::set<int> T=create_T();
return std::includes(S.begin(),S.end(), T.begin(), T.end());
}
2. Хеш-таблицы
Лучшая средняя сложность по времени, чем с отсортированным списком, может быть получена с использованием хеш-таблиц. Улучшенное поведение для больших наборов достигается ценой, как правило, более низкой производительности для небольших наборов.
Как и в случае отсортированных списков, я игнорирую сложность, обусловленную размером вселенной.
Структура данных : Хеш-таблица для S, что-нибудь быстро повторяемое для T.
Алгоритм : вставьте каждый элемент S в его хеш-таблицу. Затем для каждого элемента в T проверьте, находится ли он в хеш-таблице.
Сложность времени : O ( | S | + | T | ) для настройки, O ( | T | ) для сравнения.
Пространственная сложность : O ( | S | + | T | )
Пример (C ++)
#include <tr1/unordered_set>
std::tr1::unordered_set<int> create_S()
{
std::tr1::unordered_set<int> S;
S.insert(3);
S.insert(2);
S.insert(4);
S.insert(1);
return S;
}
std::tr1::unordered_set<int> create_T()
{
std::tr1::unordered_set<int> T;
T.insert(4);
T.insert(3);
T.insert(5);
return T;
}
bool includes(const std::tr1::unordered_set<int>& S,
const std::tr1::unordered_set<int>& T)
{
for (std::tr1::unordered_set<int>::const_iterator iter=T.begin();
iter!=T.end();
++iter)
{
if (S.find(*iter)==S.end())
{
return false;
}
}
return true;
}
int main()
{
std::tr1::unordered_set<int> S=create_S();
std::tr1::unordered_set<int> T=create_T();
return includes(S,T);
}
3. Наборы битов
Если ваша вселенная особенно мала (скажем, вы можете иметь только элементы 0-32), тогда битрейт является разумным решением. Время работы (опять же, при условии, что вы не заботитесь о времени установки) по существу постоянно. В случае, если вы заботитесь о настройке, это все же быстрее, чем создание отсортированного списка.
К сожалению, наборы битов очень быстро становятся громоздкими даже для вселенной среднего размера.
Структура данных : битовый вектор (обычно машинное целое число) для каждого из S и T. Мы можем кодировать S = 11110 и T = 00111, в данном примере.
Алгоритм : Вычислить пересечение, вычисляя поразрядные 'и' каждого бита в S с соответствующим битом в T. Если результат равен T, то S≥T.
Сложность времени : O ( | U | + | S | + | T | ) для настройки, O ( | U | ) для сравнения.
Пространственная сложность : O ( | U | )
Пример: (C ++)
#include <bitset>
// bitset universe always starts at 0, so create size 6 bitsets for demonstration.
// U={0,1,2,3,4,5}
std::bitset<6> create_S()
{
std::bitset<6> S;
// Note: bitsets don't care about order
S.set(3);
S.set(2);
S.set(4);
S.set(1);
return S;
}
std::bitset<6> create_T()
{
std::bitset<6> T;
// Note: bitsets don't care about order
T.set(4);
T.set(3);
T.set(5);
return T;
}
int main()
{
std::bitset<6> S=create_S();
std::bitset<6> T=create_T();
return S & T == T;
}
4. Фильтры Блума
Все преимущества скорости в наборах битов, без досадных ограничений на размер юниверса, которые есть в наборах битов. Единственный недостаток: они иногда (часто, если вы неосторожны) дают неправильный ответ: если алгоритм говорит «нет», то у вас определенно нет включения. Если алгоритм говорит «да», вы можете или не можете. Лучшая точность достигается при выборе фильтра большого размера и хороших хэш-функций.
Учитывая, что они могут и будут давать неправильные ответы, фильтры Блума могут показаться ужасной идеей. Тем не менее, они имеют определенное использование. Как правило, можно было бы использовать фильтры Блума для быстрой проверки множества включений, а затем использовать более медленный детерминированный метод, чтобы гарантировать правильность при необходимости. В связанной статье Википедии упоминаются некоторые приложения, использующие фильтры Bloom.
Структура данных : A Фильтр Блума - необычный набор битов. Необходимо заранее выбрать размер фильтра и хэш-функции.
Алгоритм (эскиз): инициализировать набор битов равным 0. Чтобы добавить элемент в фильтр Блума, хешируйте его с каждой хэш-функцией и установите соответствующий бит в наборе битов. Определение включения работает так же, как и для битовых наборов.
Сложность времени : O ( Размер фильтра )
Пространство сложности : O ( размер фильтра )
Вероятность правильности : Всегда корректно, если отвечает «S не включает T». Что-то вроде 0,6185 ^ (| S | x | T | / ( размер фильтра ))), если ответ «S включает T». В частности, размер фильтра должен быть выбран пропорционально произведению | S | и | T | дать разумную вероятность точности.