Эффективный способ обеспечения новизны набора

Question

Для данного набора N = {1,...,n} рассмотрим P различных ранее существующих подмножеств N.Подмножество S_p характеризуется 0-1 n вектором x_p, где i th элемент равен 0 или 1 в зависимости от того, является ли элемент i th (из n) частьюподмножество или нет.Назовем такие x_p s индикаторные векторы .

Например, если N={1,2,3,4,5}, подмножество {1,2,5} представляется вектором (1,0,0,1,1).

Сейчасс учетом P ранее существовавших подмножеств и связанных с ними векторов x_p с.

Подсчитывается подмножество кандидатов, обозначенное вектором y.

Какой самый эффективный способ проверки* является ли y уже частью набора P ранее существовавших подмножеств или y действительно является новым подмножеством, не являющимся частью P подмножеств?

Ниже приведены методы, которые я могуПодумайте о:

(Метод 1) По сути, мы должны выполнить поэлементную проверку всех существующих наборов.Далее следует псевдокод:

for(int p = 0; p < P; p++){
     //(check if x_p == y by doing an element by element comparison)
     int i;
     for(i = 0; i < n; i++){
         if(x_pi != y_i){
             i = 999999;
         }             
     }
     if(i < 999999)
          return that y is pre-existing

}
return that y is new

(Метод 2) Еще одна мысль, которая приходит в голову, - сохранить десятичный эквивалент векторов индикатора x_p с (где векторы индикатора считаются двоичными представлениями) и сравнитьэто с десятичным эквивалентом y.То есть, если набор из P ранее существующих наборов: { (0,1,0,0,1), (1,0,1,1,0) }, сохраненные десятичные дроби для этого набора будут {9, 22}.Если y равно (0,1,1,0,0), мы вычисляем 12 и сверяем это с набором {9, 22}.Преимущество этого метода заключается в том, что для каждого нового y нам не нужно сравнивать элементы n каждого ранее существующего набора.Мы можем просто сравнить десятичные числа.

Вопрос 1. Мне кажется, что (Метод 2) должен быть более эффективным, чем (Метод 1).Для (Метод 2), существует ли эффективный способ (встроенная функция библиотеки в C / C ++), который преобразует x_p s и y из двоичного в десятичное?Каким должен быть тип данных этих индикаторных переменных?Например, bool y[5]; или char y[5];?

Вопрос 2. Есть ли какой-либо метод более эффективный, чем (Метод 2)?

Answer 1

Как вы заметили, между вашими индикаторами-индикаторами и N-битными целыми числами существует тривиальный изоморфизм.Это означает, что ответом на ваш вопрос 2 является «нет»: инструменты, доступные для поддержания набора и тестирования членства в нем, такие же, как целые числа (хеш-таблицы обеспечивают нормальный подход).В комментариях упоминаются наполнители Bloom, которые могут эффективно тестировать членство с риском некоторых ложных срабатываний, но фильтры Bloom обычно предназначены для гораздо больших объемов данных, чем вы смотрите.

Что касается вашего вопроса 1: Метод 2разумно, и это даже проще, чем вы думаете.Хотя vector<bool> не дает вам простого способа превратить его в целочисленные блоки, в реализациях, о которых я знаю, он уже реализован таким образом (стандарт C ++ допускает специальную обработку этого конкретного векторного типа, что обычно считается в наше время).было плохим решением, но которое иногда приносит некоторую пользу).И эти векторы являются хэшируемыми.Так что просто держите unordered_set<vector<bool>>, и вы получите производительность, которая достаточно близка к оптимальной.(Если вы знаете N во время компиляции, вы можете предпочесть bitset вместо vector<bool>.)

Answer 2

Метод 2 может быть оптимизирован путем вычисления десятичного эквивалента данного подмножества и хеширования его с использованием модуля 1e9 + 7.Это приводит к различным десятичным числам каждый раз, так как N <= 1000 (столкновения не происходит). </p>

#define M 1000000007  //big prime number
unordered_set<long long> subset;  //containing decimal representation of all the 
                                  //previous found subsets

/*fast computation of power of 2*/
long long Pow(long long num,long long pow){
    long long result=1;
    while(pow)
    {
        if(pow&1)
        {
            result*=num;
            result%=M;
        }
        num*=num;
        num%=M;
        pow>>=1;
    }
    return result;
}
/*checks if subset pre exists*/
bool check(vector<bool> booleanVector){
    long long result=0;
    for(int i=0;i<booleanVector.size();i++)
        if(booleanVector[i])
            result+=Pow(2,i);
    return (subset.find(result)==subset.end());
}