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

Question

У меня есть набор данных ок. 9К списков переменной длины (от 1 до 100К элементов). Мне нужно вычислить длину пересечения всех возможных комбинаций из 2 списков в этом наборе данных. Обратите внимание, что элементы в каждом списке уникальны, поэтому они могут храниться как наборы в python.

Какой самый эффективный способ выполнить это в python?

Редактировать Я забыл указать, что мне нужно иметь возможность сопоставлять значения пересечения с соответствующей парой списков. Спасибо всем за быстрый ответ и извинения за путаницу!

Answer 1

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

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

Затем вы можете использовать itertools.combination , чтобы взять их два на два и рассчитать пересечение (обратите внимание, что, как указал Алекс, 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 : Как собирать индексы (после комментария редрата).

Помимо быстрого решения, на которое я ответил в комментарии, более эффективным способом сбора заданных индексов было бы использование списка (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] - его индекс.

Answer 2

Поскольку вам необходимо создать (N на N / 2) матрицу результатов, то есть O (N в квадрате) выходных данных, ни один подход не может быть меньше, чем O (N в квадрате) - конечно, на любом языке. (N в вашем вопросе около 9К). Итак, я не вижу ничего более быстрого, чем (а) создание необходимых вам N-наборов и (б) итерация по ним для получения результата, т. Е. Самый простой подход. IOW:

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» для прогрессивных идентификаторов - в противном случае очевидное изменение).

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

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

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

Answer 3

Попробуйте это:

_lists = [[1, 2, 3, 7], [1, 3], [1, 2, 3], [1, 3, 4, 7]]
_sets = map( set, _lists )
_intersection = reduce( set.intersection, _sets )

И для получения индексов:

_idxs = [ map(_i.index, _intersection ) for _i in _lists ]

Приветствия

Хосе Мария Гарсия

PS: Извините, я неправильно понял вопрос