Ответ 1
Вот несколько компромиссов, которые вы можете сделать. Предположим, что у вас есть два набора элементов, 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 + -tree), которые могут быть повторены в постоянном пространстве.
Алгоритм: для каждого элемента из T в порядке поиска S линейно для этого элемента. Помните, где вы остановились на каждом поиске, и начните следующий поиск там. Если каждый поиск удался, то S≥T.
Сложность времени: about O ( | S | Log | S | + | T | Log | T | ), чтобы создать отсортированный списки, O ( max (| S |, | T |) ) для сравнения.
Сложная сложность: about O ( | S | + | T | )
Пример (С++)
#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 | )
Пример (С++)
#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 | )
Пример: (С++)
#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 могут звучать как ужасная идея. Однако они имеют определенное применение. Как правило, можно использовать фильтры Bloom для быстрого выполнения многих проверок включения, а затем использовать более медленный детерминированный метод, чтобы гарантировать правильность, когда это необходимо. Связанная статья Википедии упоминает некоторые приложения с использованием фильтров Bloom.
Структура данных: Bloom filter - это фантастический набор битов. Обязательно выберите размер фильтра и хэш-функции.
Алгоритм (эскиз): Инициализировать битсет до 0. Чтобы добавить элемент в фильтр цветения, хешируйте его с каждой хэш-функцией и установите соответствующий бит в битете. Определение включения работает так же, как для битов.
Сложность времени: O ( размер фильтра )
Сложность пространства: O ( размер фильтра )
Вероятность правильности: всегда правильно, если она отвечает за "S не включает T". Что-то вроде 0.6185 ^ (| S | x | T |/(filter size))), если он отвечает "S включает T". В частности, размер фильтра должен быть пропорционален произведению | S | и | T | чтобы дать разумную вероятность точности.