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

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

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

ДляНапример, если у вас есть наборы A = {2, 3} и B = {4} и C = {1, 3}, у вас будет следующее дерево

                      _NOT_HAVE_[1]___HAVE____
                      |                      |            
                _____[2]_____          _____[2]_____
                |           |          |           |
             __[3]__     __[3]__    __[3]__     __[3]__
             |     |     |     |    |     |     |     |
            [4]   [4]   [4]   [4]  [4]   [4]   [4]   [4]
            / \   / \   / \   / \  / \   / \   / \   / \
           .   B .   B .   B .   B    B C   B A   A A   A
                                            C     B C   B
                                                        C

После создания дерева вы 'просто нужно сделать 50 сравнений - или сколько всего элементов вы можете иметь в наборе.

Например, для {1, 4} вы переходите через дерево: вправо (в наборе 1), слева (не имеет 2), слева, справа, и вы получите [B], что означает, что в {1, 4} включен только набор B.

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

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

Answer 2

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

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

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

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

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

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) записями.Для вычисления, скажем, supersets({1,2,3,4}), вы ищите superset({1,2,3}) и запускаете свой линейный алгоритм для этой коллекции.Дело в том, что в среднем superset({1,2,3}) не будет содержать полных n = 50000 элементов, а только часть n / 2 ^ 3 = 6250 из них, что дает 8-кратное увеличение скорости.

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

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

Answer 3

Индекс наборов, которые соответствуют критерию поиска, напоминают сами наборы. Вместо того, чтобы иметь уникальные индексы менее 50, у нас есть уникальные индексы менее 50000. Поскольку вы не возражаете против использования небольшого объема памяти, вы можете предварительно вычислить соответствующие наборы в массиве из 50 элементов с 50000-битными целыми числами. Затем вы индексируете в предварительно вычисленные совпадения и в основном просто делаете ((набор и данные) == набор), но на 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.

Answer 4

Возможный способ разделить список растровых изображений - создать массив из (индикаторы скомпилированного полубайта)

Допустим, одно из ваших 64-битных растровых изображений имеет бит 0в бит 8 установлен.
В шестнадцатеричном виде мы можем рассматривать его как 0x000000000000001F

Теперь давайте превратим это в более простое и меньшее представление.У каждого 4-битного Nibble либо установлен хотя бы один бит, либо нет.Если это так, мы представляем его как 1, если не мы представляем его как 0.

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

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

Затем возьмите иглу.Скомпилируйте его в CNI форму.Используйте это значение, чтобы подписаться на заголовок списка.Все растровые изображения в этом списке могут совпадать.Все растровые изображения в других списках могут не совпадать.

Это способ их разделения.

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

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

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

Удачи вам, и, пожалуйста, дайте нам знать, что вы в итоге делаете.

Зло.

Answer 5

Вы можете использовать инвертированный индекс ваших элементов данных. Для вашего примера

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: {1, 4}
2: {1, 5}
3: {2}
4: {1, 2, 3, 4, 5}
5: {}
6: {2, 5}
...

Таким образом, для любого конкретного набора {x_0, x_1, ..., x_i} вам необходимо пересекать множества для x_0, x_1 и других. Например, для набора {2,3,4} вам необходимо пересечь {1,5} с {2} и с {1,2,3,4,5}. Поскольку вы можете отсортировать все наборы в инвертированном индексе, вы можете пересекать наборы за минимальные длины наборов, которые должны пересекаться.

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

Несколько слов о пересечении. Вы можете использовать отсортированные списки в инвертированном индексе и пересекать множества парами (в порядке увеличения длины). Или, поскольку у вас есть не более 50 КБ элементов, вы можете использовать сжатые наборы битов (около 6 КБ для каждого числа, меньше для разреженных наборов битов, около 50 номеров, не так жадно) и пересекать наборы битов по битам. Я думаю, что для разреженных наборов битов это будет эффективно.

Answer 6

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

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

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

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

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

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

Answer 7

Другая идея - полностью охотиться на слонов.

Настройка

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

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

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

Поиск

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

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

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

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

Реконструировать

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

Answer 8

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

Вот подход индексации:

1) Разделите 50-битное поле, например, на 10 5-битных подполей. Если у вас действительно наборы по 50К, то 3 17-битных блока могут быть ближе к отметке.

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

3) Для каждого возможного битового шаблона в каждом подполе запишите список наборов, которые выделены этому подполю и соответствуют этому шаблону, учитывая только подполе.

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

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

Дополнение: Сколько таблиц потребуется, чтобы гарантировать, что любые 2 бита всегда попадают в одну и ту же таблицу? Если вы посмотрите на комбинаторное определение в http://en.wikipedia.org/wiki/Projective_plane,, вы увидите, что есть способ извлечь наборы из 7 битов из 57 (= 1 + 7 + 49) битов 57 различными способами, так что для любых двух битов в по крайней мере, одна коллекция содержит их обоих. Возможно, не очень полезно, но это все еще ответ.

Answer 9

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

Таким образом:

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

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

Answer 10

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