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

Ответ 1

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

Обновление

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

Попробуем сначала решить более простую проблему:

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

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

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}). Поэтому дубликаты должны быть удалены.

Обновление

Однако мы не можем просто удалить все дубликаты, рассмотрим этот контрпример: {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}, если мы применим удаление дубликатов в пару множеств. Суть в том, что я не могу придумать хорошую технику, которая поможет правильно обрабатывать повторяющиеся элементы на множестве.

Ответ 2

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

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

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

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

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

Ответ 3

Что вы можете сделать, в зависимости от требований к памяти, воспользоваться преимуществом заказа 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();
}

Ответ 4

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

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

Ответ 5

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

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

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

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

Алгоритм:

• Создайте 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()
      }
  }
  

Ответ 6

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

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