Быстрое пересечение двух наборов N^4

Непонятно, к какой цели производительности вы стремитесь. Обычное пересечение множеств, содержащее не более 4096 элементов, должно быть не таким медленным, по крайней мере, для пересечения общих множеств. Обычно наихудший сценарий (пересечение полного набора сам с собой) занимает около 70 мкс при стандартном наборе OCaml на моем компьютере, тогда как сценарий наилучшего случая (пересечение двух пустых наборов) занимает 6 нс. В частности, вычисление только длины в O(n) и отказ от построения набора результатов, похоже, не улучшают производительность в худшем случае.

Таким образом, мы рассматриваем оптимизацию констант путем подгонки алгоритма к набору данных. Поскольку ваши наборы содержат не более 4096 элементов, их можно представить в виде строк длиной 4096/8 = 512. При таком представлении пересечение двух наборов сводится к взятию логического and двух строк. Мы можем оптимизировать дальше, вычисляя длину на лету:

 let inter x y =
    let r = ref 0 in
    for i = 0 to set_size - 1 do
      r := !r + popcount (Char.code x.[i] land Char.code y.[i])
    done;
    !r

Этого достаточно, чтобы уменьшить время вычислений до 200 нс с помощью реализации popcount в OCaml (которая подсчитывает количество 1 бита в символе).

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

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

number = tuple[0] | tuple[1] << 3 | tuple[2] << 6 | tuple[3] << 9

Что касается пересечения сетов, то в большинстве случаев вам не удастся побить время O(n) в меньшем из двух сетов. Если вы знаете что-нибудь о распределении наборов или о том, насколько уникальными они должны быть, возможно, мы сможем придумать какую-нибудь эвристику, чтобы ускорить пересечение на практике.

Обновлять

Вот пример того, как можно ускорить вычисления, зная распределение. Допустим, мы знаем, что подавляющее большинство элементов встречаются между наборами, которые вы собираетесь предварительно обработать, очень редко. Что вы могли бы сделать, так это разбить наборы на две отдельные структуры данных: одна, которая сопоставляет пару наборов с общими для них необычными элементами, а вторая содержит оставшиеся (общие) элементы для каждого набора. Первый вариант будет простым O(1) поиском и может быть ограничен небольшим управляемым размером. Второй потребует O(n) наивного пересечения, как и раньше, но наборы будут значительно меньше, поскольку мы сказали, что подавляющее большинство элементов являются необычными.

Вот реализация на Python:

from itertools import combinations
from collections import Counter, defaultdict
from random import sample

N = 10 ** 7
K = 10 ** 5
S = 100

input_sets = [set(sample(range(N), k=K)) for _ in range(S)]

# get frequency of each element
counts = Counter()
for input_set in input_sets:
    counts.update(input_set)

# mark all elements occurring in less than 5 sets as uncommon
uncommon = {val for val, count in counts.items() if count < 5}

# break each input_set into common / uncommon parts
common_sets   = [input_set - uncommon for input_set in input_sets]
uncommon_sets = [input_set & uncommon for input_set in input_sets]

# create reverse lookup table from values to sets containing them
uncommon_lookup = defaultdict(list)
for idx, uncommon_set in enumerate(uncommon_sets):
    for val in uncommon_set:
        uncommon_lookup[val].append(idx)

# create mapping of input set pairs to shared uncommon elements
uncommon_matrix = defaultdict(set)
for val, indices in uncommon_lookup.items():
    for i, j in combinations(indices, 2): 
        uncommon_matrix[i, j].add(val)

При выполнении теста производительности мы видим, что он работает примерно в 30 раз быстрее.

from timeit import timeit

test_pairs = [sample(range(S), k=2) for _ in range(100)]

def naive_benchmark():
    for i, j in test_pairs:
        input_sets[i] & input_sets[j]

def fast_benchmark():
    for i, j in test_pairs:
        (common_sets[i] & common_sets[j]) | uncommon_matrix[i, j]

print(timeit("naive_benchmark()", setup = "from __main__ import naive_benchmark", number=10) / 10)
print(timeit("fast_benchmark()", setup = "from __main__ import fast_benchmark", number=10) / 10)

Выход:

0.3008148681998136
0.009065380399988499

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