Вычисление подмножества списка целых чисел

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

Это очень похоже на то, что делается в запросе AND при поиске инвертированного индекса в поле поиск информации.

В вашем примере у вас будет:

1 -> [set1, set2, set3, ..., set1000000]
3 -> [set1, set3]
5 -> [set2]
7 -> [set1, set7]
8 -> [set2]
...

EDIT:
В инвертированном индексе в IR для экономии места мы иногда используем d-gap, то есть сохраняем смещение между документами, а не фактическое число. Например, [2,5,10] станет [2,3,5]. Это и использование дельта-кодирования для представления чисел очень помогает, когда речь идет о пространстве.
(Конечно, есть и обратная сторона: нужно прочитать весь список, чтобы найти, есть ли в нем конкретный набор/документ, и нельзя использовать бинарный поиск, но иногда он того стоит, особенно если это разница между размещением индекса в ОЗУ или нет).

Как насчет хранения списка наборов, содержащих каждое число?

1 -- 1, 2, 3, 1000000
3 -- 1, 3
5 -- 2
etc. 

Расширяя решение Амита, вместо сохранения фактических чисел вы можете просто хранить интервалы и связанные с ними наборы.

Например, используя размер интервала 5:

 (1-5): [1,2,3,1000000]
 (6-10): [2,1000000]
 (11-15): [3]
 (16-20): [1000000]

В случае (1,7) следует рассматривать интервалы (1-5) и (5-10) (которые можно определить, просто зная размер интервала). Пересечение этих диапазонов дает вам [2,1000000]. Бинарный поиск наборов показывает, что (1,7) действительно существует в обоих наборах.

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

Вероятно, вам следует сохранить его, чтобы можно было использовать двоичный поиск для проверки значений, поэтому диапазон подмножества должен быть примерно таким (min + max)/N, где 2N — это максимальное количество значений, которые необходимо будет найти в двоичном формате. каждый набор. Например, «содержит ли набор 3 какие-либо значения от 5 до 10?» это делается путем нахождения ближайших значений к 5 (3) и 10 (11), в данном случае нет это не так. Вам нужно будет просмотреть каждый набор и выполнить двоичный поиск значений интервала, которые могут быть в наборе. Это означает, что вы не будете искать 100, когда набор достигает только 10.

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

По-прежнему будет сложно выбрать, какой диапазон использовать, слишком велик, и потребуется много времени для построения структуры данных (1000 * миллионов * log (N)). Слишком маленький, и вы начнете сталкиваться с проблемами свободного места. Идеальный размер диапазона, вероятно, таков, что он гарантирует, что количество наборов, связанных с каждым диапазоном, приблизительно равно, а также гарантирует, что общее количество диапазонов не слишком велико.

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

1. Начните поиск с наибольшего числа (7) входного набора и исключите другие подмножества (будут возвращены Set1 и Set1000000).

2. Поиск других входных элементов (1) в оставшихся наборах.