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

Ответ 1

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

Например, если у вас есть множества 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], что означает только набор B включен в {1, 4}.

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

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

Ответ 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. Вы получите таблицу

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 = 50 000 элементов, но только фракция n/2 ^ 3 = 6250 из них, что дает 8-кратное увеличение скорости.

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

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

Ответ 3

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

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

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

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

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

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

Ответ 4

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

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

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

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

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

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

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

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

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

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

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

Зла.

Ответ 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) с огромным набором индексов.

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

Ответ 6

Индекс наборов, соответствующих критерию поиска, напоминает сами наборы. Вместо уникальных индексов меньше 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.

Ответ 7

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

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

Я уверен, что вы можете немного улучшить это, если вы сохранили отсортированный vectors вместо sets и element_haystacks мог бы быть 50 элементов vector вместо hash_map.

Ответ 8

Поскольку числа меньше 50, вы можете создать хеш-код один-к-одному с использованием 64-разрядного целого числа, а затем использовать побитовые операции для тестирования наборов в O (1) раз. Создание хэша также будет O (1). Я думаю, что либо XOR, за которым следует тест на ноль, либо И, за которым следует тест на равенство, будет работать. (Если я правильно понял проблему.)

Ответ 9

Поместите свои наборы в массив (не связанный список) и SORT THEM. Критерии сортировки могут быть: 1) количеством элементов в наборе (количество 1 бит в заданном представлении) или 2) наименьшим элементом в наборе. Например, пусть A={7, 10, 16} и B={11, 17}. Тогда B<A по критерию 1) и A<B по критерию 2). Сортировка - O (n log n), но я предполагаю, что вы можете позволить себе некоторое время предварительной обработки, т.е. Что структура поиска статична.

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

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

Еще один, более надежный, критерий сортировки - это вычисление пролета элементов в каждом наборе и сортировка их в соответствии с этим. Например, самый низкий элемент в наборе A равен 7, а наивысший - 16, поэтому вы должны кодировать его диапазон как 0x1007; аналогичным образом B-диапазон будет 0x110B. Сортируйте наборы в соответствии с "кодом прогона" и снова используйте двоичный поиск, чтобы найти все наборы с тем же "кодом пролета", что и ваш элемент данных.

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

Ответ 10

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

Ответ 11

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

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

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

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

Ответ 12

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

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

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

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

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

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

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

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

Ответ 13

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

Настройка

Создайте 64-битный массив бит размером 50 бит.

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

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

Поиск

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

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

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

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

Reconstruct

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