Проблема
Мне даны N массивов булевых C. Я хочу организовать их в структуру данных, которая позволяет мне выполнить следующую операцию как можно быстрее. Учитывая новый массив, верните true, если этот массив является "надмножеством" любого из хранимых массивов. С надмножеством я имею в виду это: A - это надмножество B, если A [i] истинно для каждого i, где B [i] истинно. Если B [i] неверно, то A [i] может быть любым.
Или, в терминах наборов вместо массивов:
Храните N наборов (каждый с C возможными элементами) в структуру данных, чтобы вы могли быстро найти, если данный набор является надмножеством любого из сохраненных наборов.
Построение структуры данных может занять как можно дольше, но поиск должен быть максимально эффективным, а структура данных не может занимать слишком много места.
Некоторый контекст
Я думаю, что это интересная проблема сама по себе, но для того, что я действительно пытаюсь решить, вы можете предположить следующее:
- N = 10000
- C = 1000
- Сохраненные массивы разрежены
- Выбранные массивы случайны (поэтому не разрежены)
То, что я придумал до сих пор
-
Поиск O (NC): просто переберите все массивы. Это слишком медленно, хотя.
-
Для поиска O (C): у меня было длинное описание здесь, но, как отметил Амит в комментариях, это было в основном BDD. Хотя это имеет большую скорость поиска, оно имеет экспоненциальное число узлов. При больших тактах N и C это занимает слишком много места.
Я надеюсь, что между этим решением O (N * C) и O (C) может быть решение O (log (N) * C), которое не требует экспоненциального объема пространства.
EDIT: новая идея, которую я придумал
-
Для поиска O (sqrt (N) C): Храните массивы в качестве префикса . При поиске массива A перейдите к соответствующему поддереву, если A [i] = 0, но посетите оба поддеревья, если A [i] = 1.
Моя интуиция подсказывает мне, что это должно сделать (среднюю) сложность поиска O (sqrt (N) C), если вы считаете, что сохраненные массивы случайны. Но: 1. Это не так, массивы редки. И 2. это только интуиция, я не могу это доказать.
Я попробую и эту новую идею, и метод BDD, и посмотрю, какая из двух из них лучше всего подходит.
Но пока эта проблема чаще возникает? Разве это не имя? Не было ли ранее проведенных исследований? Мне действительно кажется, что я изобретаю колесо здесь.