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

Question

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

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

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

Answer 1

Если ваши наборы хранятся в 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] его индекс.

Answer 2

Поскольку вам нужно создать матрицу результатов (N на N/2), то есть выходных данных O (N в квадрате), ни один подход не может быть меньше, чем O (N в квадрате) - конечно, на любом языке.(В вашем вопросе N означает «около 9К»).Итак, я не вижу ничего быстрее, чем (а) создать 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», просто для разнообразия ;-)

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 ]

Ваше здоровье,

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

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