Структура данных для совпадающих наборов

Question

У меня есть приложение, в котором у меня есть несколько наборов.Набор может быть
{4, 7, 12, 18}
уникальных чисел и все меньше 50.

Тогда у меня есть несколько элементов данных:
1 {1, 2, 4, 7, 8, 12, 18, 23, 29}
2 {3, 4, 6, 7, 15, 23, 34, 38}
3 {4, 7, 12, 18}
4 {1, 4, 7, 12, 13, 14, 15, 16, 17, 18}
5 {2, 4, 6, 7, 13, 15}

Элементы данных 1, 3и 4 соответствуют набору, потому что они содержат все элементы в наборе.

Мне нужно спроектировать структуру данных, которая очень быстро определяет, является ли элемент данных членом набора, который включает в себя все члены, которые являются частью набора (поэтому элемент данных является надмножеством набора).Мои лучшие оценки на данный момент предполагают, что будет менее 50 000 наборов.

Моя текущая реализация содержит мои наборы и данные в виде 64-разрядных целых чисел без знака и наборы, хранящиеся в списке.Затем, чтобы проверить элемент данных, я перебираю список, сравнивая ((set & data) == set).Он работает и экономит место, но работает медленно (O (n)), и я был бы рад обменять часть памяти на некоторую производительность.У кого-нибудь есть идеи о том, как это организовать?

Редактировать: Большое спасибо за все ответы.Похоже, мне нужно предоставить больше информации о проблеме.Сначала я получаю наборы, а затем по одному получаю элементы данных.Мне нужно проверить, соответствует ли элемент данных одному из наборов.
Наборы, скорее всего, будут «слипшимися», например, для данной задачи 1, 3 и 9 могут содержаться в 95% наборов;Я могу предсказать это до некоторой степени заранее (но не очень хорошо).

Для тех, кто предлагает запоминание: это структура данных для запомненной функции.Наборы представляют общие решения, которые уже были вычислены, а элементы данных являются новыми входными данными для функции.Сопоставляя элемент данных с общим решением, я могу избежать большой обработки.

Answer 1

Поместите свои наборы в массив (не связанный список) и сортируйте их. Критериями сортировки могут быть: 1) количество элементов в наборе (количество 1-бит в представлении набора) или 2) самый низкий элемент в наборе. Например, пусть A={7, 10, 16} и B={11, 17}. Затем B<A по критерию 1) и A<B по критерию 2). Сортировка - это O (n log n), но я предполагаю, что вы можете позволить себе некоторое время предварительной обработки, то есть, что структура поиска является статической.

Когда приходит новый элемент данных, вы можете использовать бинарный поиск (логарифмическое время), чтобы найти начальный набор кандидатов в массиве. Затем вы выполняете линейный поиск в массиве и проверяете элемент данных на соответствие множеству в массиве, пока элемент данных не станет «большим», чем набор.

Вы должны выбрать свой критерий сортировки, основанный на распространении ваших наборов. Если все наборы имеют 0 как самый низкий элемент, вы не должны выбирать критерий 2). И наоборот, если распределение установленных мощностей неравномерно, не следует выбирать критерий 1).

Еще одним, более надежным критерием сортировки будет вычисление диапазона элементов в каждом наборе и сортировка их в соответствии с этим. Например, самый низкий элемент в наборе A равен 7, а самый высокий - 16, поэтому вы должны закодировать его диапазон как 0x1007; Точно так же диапазон B был бы 0x110B. Сортируйте наборы в соответствии с «кодом диапазона» и снова используйте бинарный поиск, чтобы найти все наборы с тем же «кодом диапазона», что и у вашего элемента данных.

В обычном C вычисление «span-кода» идет медленно, но это можно сделать быстро, если вы прибегаете к сборке - у большинства процессоров есть инструкции, которые находят наиболее / наименее значимый бит установки.

Answer 2

Поскольку числа меньше 50, вы можете построить однозначный хеш, используя 64-разрядное целое число, а затем использовать побитовые операции для проверки множеств за O (1).Создание хэша также будет O (1).Я думаю, что XOR с последующим тестом на ноль или AND с последующим тестом на равенство будет работать.(Если я правильно понял проблему.)

Answer 3

Вы можете построить обратный индекс списков "стога сена", которые содержат каждый элемент:

std::set<int> needle;  // {4, 7, 12, 18}
std::vector<std::set<int>> haystacks;
// A list of your each of your data sets:
// 1 {1, 2, 4, 7, 8, 12, 18, 23, 29}
// 2 {3, 4, 6, 7, 15, 23, 34, 38}
// 3 {4, 7, 12, 18}
// 4 {1, 4, 7, 12, 13, 14, 15, 16, 17, 18}
// 5 {2, 4, 6, 7, 13, 

std::hash_map[int, set<int>>  element_haystacks;
// element_haystacks maps each integer to the sets that contain it
// (the key is the integers from the haystacks sets, and 
// the set values are the index into the 'haystacks' vector):
// 1 -> {1, 4}  Element 1 is in sets 1 and 4.
// 2 -> {1, 5}  Element 2 is in sets 2 and 4.
// 3 -> {2}  Element 3 is in set 3.
// 4 -> {1, 2, 3, 4, 5}  Element 4 is in sets 1 through 5.  
std::set<int> answer_sets;  // The list of haystack sets that contain your set.
for (set<int>::const_iterator it = needle.begin(); it != needle.end(); ++it) {
  const std::set<int> &new_answer = element_haystacks[i];
  std::set<int> existing_answer;
  std::swap(existing_answer, answer_sets);
  // Remove all answers that don't occur in the new element list.
  std::set_intersection(existing_answer.begin(), existing_answer.end(),
                        new_answer.begin(), new_answer.end(),
                        inserter(answer_sets, answer_sets.begin()));
  if (answer_sets.empty()) break;  // No matches :(
}

// answer_sets now lists the haystack_ids that include all your needle elements.
for (int i = 0; i < answer_sets.size(); ++i) {
  cout << "set: " << element_haystacks[answer_sets[i]];
}

Если я не ошибаюсь, это будет иметь максимальное время выполнения O(k*m), где среднее значениечисло наборов, к которым принадлежит целое число, а m - средний размер набора игл (<50).К сожалению, из-за построения обратного сопоставления у него будут существенные накладные расходы памяти (<code>element_haystacks).

Я уверен, что вы могли бы немного улучшить это, если бы вы хранили отсортированные vectors вместо setsи element_haystacks может представлять собой 50 элементов vector вместо hash_map.