Python: Быстрое извлечение пересечений среди всех возможных 2-комбинаций в большом количестве списков

Если ваши наборы хранятся в s, например:

s = [set([1, 2]), set([1, 3]), set([1, 2, 3]), set([2, 4])]

Затем вы можете использовать itertools.combinations, чтобы взять их два на два и вычислить пересечение (обратите внимание, что, как указал Алекс, combinations доступно только с версии 2.6). Здесь со списком (просто для примера):

from itertools import combinations
[ i[0] & i[1] for i in combinations(s,2) ]

Или в цикле, что, вероятно, вам нужно:

for i in combinations(s, 2):
    inter = i[0] & i[1]
    # processes the intersection set result "inter"

Итак, чтобы иметь длину каждого из них, эта «обработка» будет:

    l = len(inter)

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

Изменить. Обратите внимание, что при использовании этого метода каждый набор в списке "s" может фактически быть чем-то другим, что возвращает набор, например генератором. Сам список может быть просто генератором, если у вас мало памяти. Это может быть намного медленнее, в зависимости от того, как вы генерируете эти элементы, но вам не нужно будет одновременно иметь весь список наборов в памяти (не то чтобы это должно быть проблемой в вашем случае).

Например, если каждый набор сделан из функции gen:

def gen(parameter):
    while more_sets():
        # ... some code to generate the next set 'x'
        yield x

with open("results", "wt") as f_results:
    for i in combinations(gen("data"), 2):
        inter = i[0] & i[1]
        f_results.write("%d\n" % len(inter))

Редактировать 2: Как собирать индексы (после комментария Redrat).

Помимо быстрого решения, на которое я ответил в комментарии, более эффективным способом сбора установленных индексов было бы иметь список (index, set) вместо списка set.

Пример с новым форматом:

s = [(0, set([1, 2])), (1, set([1, 3])), (2, set([1, 2, 3]))]

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

with open("results", "wt") as f_results:
    for i in combinations(s, 2):
        inter = i[0][1] & i[1][1]
        f_results.write("length of %d & %d: %d\n" % (i[0][0],i[1][0],len(inter))

В цикле i[0] и i[1] будут кортежем (index, set), поэтому i[0][1] — это первый набор, i[0][0] его индекс.

Поскольку вам нужно создать матрицу (N на N/2) результатов, то есть O(N в квадрате) выходных данных, ни один подход не может быть меньше, чем O(N в квадрате) — конечно, на любом языке. (N в вашем вопросе «около 9K»). Итак, я не вижу ничего более быстрого, чем (а) создание N наборов, которые вам нужны, и (б) итерация по ним для получения вывода, т. е. простейший подход. ИОВ:

def lotsofintersections(manylists):
  manysets = [set(x) for x in manylists]
  moresets = list(manysets)
  for  s in reversed(manysets):
    moresets.pop()
    for z in moresets:
      yield s & z

Этот код уже пытается добавить некоторую незначительную оптимизацию (например, избегая нарезки или извлечения из начала списков, что может добавить другие факторы O (N в квадрате)).

Если у вас есть много доступных ядер и/или узлов и вы ищете параллельные алгоритмы, это, конечно, другой случай — если это ваш случай, можете ли вы упомянуть тип кластера, который у вас есть, его размер, как узлы и ядра могут лучше всего взаимодействовать , и так далее?

Редактировать: как ОП случайно упомянул в комментарии (!), что им действительно нужны номера пересекаемых наборов (действительно, зачем опускать такие важные части спецификаций ?! хотя бы отредактируйте вопрос чтобы уточнить их...), для этого потребуется только изменить это на:

  L = len(manysets)
  for i, s in enumerate(reversed(manysets)):
    moresets.pop()
    for j, z in enumerate(moresets):
      yield L - i, j + 1, s & z

(если вам нужно «считать от 1» для прогрессивных идентификаторов - в противном случае очевидное изменение).

Но если это часть спецификации, вы можете использовать более простой код — забудьте о дополнительных наборах и:

  L = len(manysets)
  for i xrange(L):
    s = manysets[i]
    for j in range(i+1, L):
      yield i, j, s & manysets[z]

на этот раз предположим, что вместо этого вы хотите «считать с 0», просто для разнообразия ;-)