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

Это не настоящий ответ, скорее наблюдение: эта проблема выглядит так, как будто ее можно эффективно распараллелить или даже распределить, что, по крайней мере, сократит время работы до O (n / количество ядер)

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

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). К сожалению, это будет иметь значительные накладные расходы на память из-за построения обратного отображения ( element_haystacks ).

Я уверен, что вы могли бы немного улучшить это, если бы сохранили отсортированные векторов вместо наборов и element_haystacks могли бы быть вектором из 50 элементов вместо hash_map .

Если вы собираетесь повысить производительность, вам придется сделать что-нибудь необычное, чтобы уменьшить количество выполняемых вами сравнений наборов.

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

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

Или, возможно, сгруппируйте их в 50 групп, указав «этот элемент данных содержит N» для N = 1..50.

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

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

Индексы наборов, соответствующих критерию поиска, напоминают сами наборы. Вместо того, чтобы иметь уникальные индексы меньше 50, у нас есть уникальные индексы меньше 50000.Поскольку вы не возражаете против использования небольшого количества памяти, вы можете предварительно вычислить соответствующие наборы в массиве из 50 элементов из 50000-битных целых чисел. Затем вы индексируете предварительно вычисленные совпадения и в основном просто выполняете свой ((set & data) == set), но на 50000-битных числах, которые представляют совпадающие наборы. Вот что я имею в виду.

#include <iostream>

enum
{
    max_sets = 50000, // should be >= 64
    num_boxes = max_sets / 64 + 1,
    max_entry = 50
};

uint64_t sets_containing[max_entry][num_boxes];

#define _(x) (uint64_t(1) << x)

uint64_t sets[] =
{
    _(1) | _(2) | _(4) | _(7) | _(8) | _(12) | _(18) | _(23) | _(29),
    _(3) | _(4) | _(6) | _(7) | _(15) | _(23) | _(34) | _(38),
    _(4) | _(7) | _(12) | _(18),
    _(1) | _(4) | _(7) | _(12) | _(13) | _(14) | _(15) | _(16) | _(17) | _(18),
    _(2) | _(4) | _(6) | _(7) | _(13) | _(15),
    0,
};

void big_and_equals(uint64_t lhs[num_boxes], uint64_t rhs[num_boxes])
{
    static int comparison_counter = 0;
    for (int i = 0; i < num_boxes; ++i, ++comparison_counter)
    {
        lhs[i] &= rhs[i];
    }
    std::cout
        << "performed "
        << comparison_counter
        << " comparisons"
        << std::endl;
}

int main()
{
    // Precompute matches
    memset(sets_containing, 0, sizeof(uint64_t) * max_entry * num_boxes);

    int set_number = 0;
    for (uint64_t* p = &sets[0]; *p; ++p, ++set_number)
    {
        int entry = 0;
        for (uint64_t set = *p; set; set >>= 1, ++entry)
        {
            if (set & 1)
            {
                std::cout
                    << "sets_containing["
                    << entry
                    << "]["
                    << (set_number / 64)
                    << "] gets bit "
                    << set_number % 64
                    << std::endl;

                uint64_t& flag_location =
                    sets_containing[entry][set_number / 64];

                flag_location |= _(set_number % 64);
            }
        }
    }

    // Perform search for a key
    int key[] = {4, 7, 12, 18};
    uint64_t answer[num_boxes];
    memset(answer, 0xff, sizeof(uint64_t) * num_boxes);

    for (int i = 0; i < sizeof(key) / sizeof(key[0]); ++i)
    {
        big_and_equals(answer, sets_containing[key[i]]);
    }

    // Display the matches
    for (int set_number = 0; set_number < max_sets; ++set_number)
    {
        if (answer[set_number / 64] & _(set_number % 64))
        {
            std::cout
                << "set "
                << set_number
                << " matches"
                << std::endl;
        }
    }

    return 0;
}

Выполнение этой программы дает:

sets_containing[1][0] gets bit 0
sets_containing[2][0] gets bit 0
sets_containing[4][0] gets bit 0
sets_containing[7][0] gets bit 0
sets_containing[8][0] gets bit 0
sets_containing[12][0] gets bit 0
sets_containing[18][0] gets bit 0
sets_containing[23][0] gets bit 0
sets_containing[29][0] gets bit 0
sets_containing[3][0] gets bit 1
sets_containing[4][0] gets bit 1
sets_containing[6][0] gets bit 1
sets_containing[7][0] gets bit 1
sets_containing[15][0] gets bit 1
sets_containing[23][0] gets bit 1
sets_containing[34][0] gets bit 1
sets_containing[38][0] gets bit 1
sets_containing[4][0] gets bit 2
sets_containing[7][0] gets bit 2
sets_containing[12][0] gets bit 2
sets_containing[18][0] gets bit 2
sets_containing[1][0] gets bit 3
sets_containing[4][0] gets bit 3
sets_containing[7][0] gets bit 3
sets_containing[12][0] gets bit 3
sets_containing[13][0] gets bit 3
sets_containing[14][0] gets bit 3
sets_containing[15][0] gets bit 3
sets_containing[16][0] gets bit 3
sets_containing[17][0] gets bit 3
sets_containing[18][0] gets bit 3
sets_containing[2][0] gets bit 4
sets_containing[4][0] gets bit 4
sets_containing[6][0] gets bit 4
sets_containing[7][0] gets bit 4
sets_containing[13][0] gets bit 4
sets_containing[15][0] gets bit 4
performed 782 comparisons
performed 1564 comparisons
performed 2346 comparisons
performed 3128 comparisons
set 0 matches
set 2 matches
set 3 matches

3128 сравнений uint64_t лучше 50000 сравнений, так что вы выигрываете. Даже в худшем случае, когда это будет ключ, содержащий все 50 элементов, вам нужно будет выполнить только сравнение num_boxes * max_entry, которое в данном случае равно 39100. Все же лучше, чем 50000.

Я не могу этого доказать, но вполне уверен, что не существует решения, которое могло бы легко превзойти границу O (n). Ваша проблема «слишком общая»: каждый набор имеет m = 50 свойств (а именно, свойство k состоит в том, что оно содержит число k), и дело в том, что все эти свойства независимы друг от друга . Нет никаких умных комбинаций свойств, которые могут предсказать наличие других свойств. Сортировка не работает, потому что проблема очень симметрична, любая перестановка ваших 50 чисел приведет к той же проблеме, но испортит любой порядок. Если ваш ввод не имеет скрытой структуры , вам не повезло.

Однако есть место для компромисса между скоростью и памятью. А именно, вы можете предварительно вычислить ответы на небольшие запросы . Пусть Q будет набором запросов, а надмножества (Q) будет набором наборов, которые содержат Q , то есть решение вашей проблемы. Тогда ваша проблема имеет следующее ключевое свойство

Q ⊆ P  =>  supersets(Q) ⊇ supersets(P)

Другими словами, результаты для P = {1,3,4} являются частью результатов для Q = {1,3 } .

Теперь предварительно вычислите все ответы на небольшие запросы. Для демонстрации возьмем все запросы размера <= 3. Вы получите таблицу

supersets({1})
supersets({2})
...
supersets({50})
supersets({1,2})
supersets({2,3})
...
supersets({1,2,3})
supersets({1,2,4})
...

supersets({48,49,50})

с O (m ^ 3) записями. Чтобы вычислить, скажем, надмножеств ({1,2,3,4}) , вы ищите надмножество ({1,2,3}) и запускаете свой линейный алгоритм на этом коллекция.Дело в том, что в среднем надмножество ({1,2,3}) не будет содержать полных n = 50 000 элементов, а будет содержать только часть n / 2 ^ 3 = 6250 из них, что дает 8-кратное увеличение скорости.

(Это обобщение метода «обратного индекса», предложенного в других ответах.)

Однако в зависимости от вашего набора данных использование памяти будет довольно ужасным. Но вы могли бы опустить некоторые строки или ускорить алгоритм, заметив, что такой запрос, как {1,2,3,4} , может быть вычислен из нескольких различных предварительно вычисленных ответов, таких как надмножества ( {1,2,3}) и надмножества ({1,2,4}) , и вы будете использовать наименьшее из них.

Другая идея состоит в том, чтобы полностью предварительно охотиться на ваших слонов.

Настройка

Создание 64-битного массива X 50 000 битов элементов.

Проанализируйте свой поисковый набор и установите соответствующие биты в каждой строке.

Сохраните битовую карту на диск, чтобы ее можно было перезагрузить при необходимости.

Поиск

Загрузить элемент битового массива в память.

Создайте массив битовых карт, 1 X 50000. Установите все значения в 1. Это битовый массив поиска.

Возьмите иглу и пройдитесь по каждому значению. Используйте его как индекс в битовом массиве элемента. Возьмите соответствующий битовый массив, затем И в массив поиска.

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

Reconstruct

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

Я удивлен, что никто не упомянул, что STL содержит алгоритм для обработки таких вещей за вас. Следовательно, вы должны использовать includes. По описанию он выполняет максимум 2*(N+M)-1 сравнений для наихудшего случая производительности O(M+N).

Следовательно:

bool isContained = includes( myVector.begin(), myVector.end(), another.begin(), another.end() );

если вам нужно время O( log N), то я вынужден уступить другим респондентам.