Более быстрый способ поиска массива множеств

Question

У меня есть массив, содержащий 100 000 наборов. Каждый набор содержит натуральные числа ниже 1,000,000. Я должен найти количество упорядоченных пар {m, n}, где 0 < m < 1,000,000, 0 < n < 1,000,000 и m! = N, которые не существуют вместе ни в одном из 100 000 наборов. Наивный метод поиска по всем множествам приводит к 10^5 * (10^6 выбрать 2) числу поисков.

Например, у меня есть 2 набора set1 = {1,2,4} set2 = {1,3}. Все возможные упорядоченные пары чисел ниже 5 являются {1,2}, {1,3}, {1,4}, {2,3}, {2,4} и {3,4}. Упорядоченные пары чисел ниже 5, которые не существуют вместе в множестве 1, являются {1,3}, {2,3} и {3,4}. Упорядоченные пары ниже 5, отсутствующие в наборе 2, являются {1,2}, {1,4}, {2,3}, {2,4} и {3,4}. Упорядоченные пары, которые не существуют вместе в обоих множествах, являются {2,3} и {3,4}. Таким образом, количество числа упорядоченных пар отсутствует 2.

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

Обновление: Вот некоторые сведения о структуре моего набора данных. Количество элементов в каждом наборе варьируется от 2 до 500 000. Среднее число элементов составляет около 10 000 человек. Распределение достигает 10 000 и сужается в обоих направлениях. Объединение элементов в 100 000 наборов близко к 1 000 000.

Answer 1

В качестве опции вы можете построить Bloom Filter (ы) над вашими наборами.

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

Answer 2

Если возможно, у вас есть набор всех чисел и удалите каждое из чисел, когда вы вставляете в свой массив набора. Это будет иметь сложность пространства O (n).

Конечно, если вы не хотите иметь высокую сложность спецификации, возможно, у вас может быть вектор диапазона. Для каждого элемента в векторе у вас есть пара чисел, которые являются началом/концом диапазона.

Answer 3

Сначала позволяет решить более простую задачу подсчета количества элементов, отсутствующих в ваших наборах. Эта задача может быть переформулирована в более простой форме - вместо 100 000 наборов вы можете думать о 1 наборе, который содержит все ваши номера. Тогда число элементов, отсутствующих в этом наборе, равно x = 1000000 - len(set). Теперь вы можете использовать этот номер x для подсчета количества комбинаций. С повторениями: x * x, без повторений: x * (x - 1). Поэтому в нижней строке моего ответа стоит поставить все ваши номера в один большой набор и использовать его длину, чтобы найти количество комбинаций с помощью комбинаторики.

Update

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

Позволяет попытаться решить простую задачу первый:

• ваших наборы не все числа в них, никто не хватают
• каждого числа присутствует ровно в одном наборе, нет дубликатов в наборах

Как бы вы построили такие комбинации над такими множествами? Вы бы просто выбрали два элемента из разных наборов, и полученная комбинация не была бы ни в одном из наборов. Количество таких комбинаций можно пересчитать, используя следующий код (он принимает размеры множеств):

int count_combinations(vector<int>& buckets) { 
    int result = 0; 
    for (int i=0; i < buckets.size(); ++i) { 
    for (int j=i+1; j < buckets.size(); ++j) { 
     result += buckets[i] * buckets[j]; 
    } 
    } 
    return result; 
} 

Теперь давайте представим, что некоторые номера отсутствуют. Затем мы можем просто добавить дополнительный набор с теми недостающими числами в наши наборы (как отдельный набор). Но нам также нужно учитывать, что при наличии n отсутствующих номеров были бы n * (n-1) комбинации, построенные с использованием только этих недостающих чисел. Поэтому следующий код будет производить общее число комбинаций с учетом недостающих номеров:

int missing_numbers = upper_bound - all_numbers.size() - 1; 
int missing_combinations = missing_numbers * (missing_numbers - 1); 

return missing_combinations + count_combinations(sets, missing_numbers); 

Теперь давайте представим, что мы имеем дубликат через два набора: {a, b, c}, {a, d}. Какие типы ошибок они будут вводить? Следующие пары: {a, a} - повторение, {a, d} - комбинация, которая присутствует во втором комплекте. Итак, как лечить такие дубликаты? Нам нужно полностью исключить их из всех множеств. Даже один экземпляр дубликата даст комбинацию, присутствующую в некотором наборе. Потому что мы можем просто выбрать любой элемент из набора, в котором дубликат был удален, и создать такую ​​комбинацию (в моем примере - если мы сохраним a в первом наборе, затем выберите d со второго, чтобы произвести {a, d}, если мы сохраним a во втором сете , затем выберите b или c с первого, чтобы произвести {a, b} и {a, c}). Поэтому дубликаты должны быть удалены.

Update

Однако мы не можем просто удалить все дубликаты, рассмотреть этот контрпример: {a, b}{a, c}{d}. Если мы просто удалим a, мы приобретем {b}{c}{d} и потеряли информацию о несуществующей комбинации {a, d}. Рассмотрим другой контрпример: {a, b}{a, b, c}{b, d}. Если мы просто удалим дубликаты, мы получим {c}{d} и потеряем информацию о {a, d}.

Кроме того, мы не можем просто применить такую ​​логику для пар множеств, простого счетчика, например, для чисел < 3: {1, 2}{1}{2}. Здесь количество отсутствующих комбинаций равно 0, но мы будем неправильно подсчитывать {1, 2}, если мы применим удаление дубликатов в пару наборов. Суть в том, что я не могу придумать хорошую технику, которая поможет правильно обрабатывать повторяющиеся элементы на множестве.

Answer 4

Если вы ищете комбинации через комплекты, есть способ значимо сконденсировать ваш набор данных, как показано на странице frenzykryger's answer.Однако, из ваших примеров, то, что вы ищете, - это количество доступных комбинаций в пределах каждого набора, то есть каждый набор содержит неприводимую информацию. Кроме того, вы не можете использовать комбинаторика, чтобы просто получить количество комбинаций из каждого набора; вы в конечном счете хотите дедуплицировать комбинации во всех наборах, поэтому фактические комбинации имеют значение.

Зная все это, трудно представить себе какие-либо крупные прорывы, которые вы могли бы сделать. Допустим, у вас есть i наборов и максимум k элементов в каждом наборе. Наивный подход будет:

• Если ваши наборы, как правило, плотные (т.е. содержит большинство чисел от 1 до 1.000.000), заменить их дополнение множества вместо
• Создать набор из 2 кортежей (использовать набор структуру, которая обеспечивает вставку идемпотентна)
• Для каждого множества O (I):
  • оценить все комбинации и вставить в набор комбинаций: O (K выбирают 2)

В худшем случае сложность этого невелика, но при условии, что у вас есть сценарии, в которых набор содержит большую часть чисел от 0 до 1 000 000, или почти ни одного из них, вы должны увидеть значительное улучшение производительности.

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

Answer 5

Что вы можете сделать, в зависимости от требований к памяти, воспользоваться заказом Set и умножать ценности. Что-то вроде кода ниже (непроверенный). Вы будете перебирать все свои наборы, а затем для каждого из ваших наборов вы будете перебирать их значения. Для каждого из этих значений вы проверите все значения в наборе после них. Наша сложность сводится к числу множеств, умноженных на квадрат их размеров. Вы можете использовать различные методы для отслеживания найденного/необоснованного счета, но использование набора должно быть прекрасным, поскольку вставка - это просто O(log(n)), где n - не более 499999500000. Теоретически с использованием карты множеств (отображение на основе первое значение) может быть немного быстрее, но в любом случае стоимость минимальна.

long long numMissing(const std::array<std::set<int>, 100000>& sets){ 
    std::set<pair<int, int> > found; 
    for (const auto& s : sets){ 
     for (const auto& m : s){ 
      const auto &n = m; 
      for (n++; n != s.cend(); n++){ 
       found.emplace(m, n); 
      } 
     } 
    } 
    return 499999500000 - found.size(); 
} 

Answer 6

Физическое хранение каждой возможной пары занимает слишком много памяти. У нас есть 100 тыс. Наборов, а средний набор имеет 10 тыс. Чисел = 50 М пар = 400 МБ с int32 (и set<pair<int, int>> требуется гораздо больше 8 байтов на элемент).

Мое предложение основывается на двух идеях:

• не храним, рассчитывать только Недостающая парам
• использование интервала, установленного для компактного хранения и быстрого набора операций (как и boost interval set)

Алгоритм по-прежнему квадратичен по числу элементов в наборах, но требует гораздо меньше пространства.

Алгоритм:

• Создание union_set отдельных наборов.
• Нам также нужна структура данных, назовем ее sets_for_number, чтобы ответить на этот вопрос: какие наборы содержат определенное число? Для простейшего случая это может быть unordered_map<int, vector<int>> (индексы векторных магазинов 0..99999)

• Также создайте обратные наборы для каждого набора. Используя интервальные наборы, это занимает в среднем всего 10k * 2 * sizeof(int) места.

  dynamic_bitset<> union_set = ...; //union of individual sets (can be vector<bool>) 
  vector<interval_set<int>> inverse_sets = ...; // numbers 1..999999 not contained in each set 
  int64_t missing_count = 0; 
  
  for(int n = 1; n < 1000000; ++n) 
      // count the missing pairs whose first element is n 
      if (union_set.count(n) == 0) { 
       // all pairs are missing 
       missing_count += (999999 - n); 
      } else { 
       // check which second elements are not present 
       interval_set<int> missing_second_elements = interval_set<int>(n+1, 1000000); 
       // iterate over all sets containing n 
       for(int set_idx: sets_for_number.find(n)) { 
        // operator&= is in-place intersection 
        missing_second_elements &= inverse_sets[set_idx]; 
       } 
       // counting the number of pairs (n, m) where m is a number 
       // that is not present in any of the sets containing n 
       for(auto interval: missing_second_elements) 
        missing_count += interval.size() 
      } 
  }