Python: extração rápida de interseções entre todas as possíveis combinações em um grande número de listas

Question

Eu tenho um conjunto de dados de ca. 9k listas de comprimento variável (1 a 100k elementos). Eu preciso calcular o comprimento da interseção de Todas as combinações possíveis de 2 lista Neste conjunto de dados. Observe que os elementos em cada lista são únicos para que possam ser armazenados como conjuntos no Python.

Qual é a maneira mais eficiente de executar isso no Python?

Editar Esqueci de especificar que preciso ter a capacidade de corresponder aos valores de interseção com o par de listas correspondentes. Obrigado a todos pela pronta resposta e desculpas pela confusão!

Answer 1

Se seus conjuntos forem armazenados em S, por exemplo:

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

Então você pode usar ITERTOOLS.COMBINAÇÕES para levá -los dois por dois e calcular o cruzamento (observe que, como Alex apontou, combinations está disponível apenas desde a versão 2.6). Aqui com uma compreensão de lista (apenas por causa do exemplo):

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

Ou, em um loop, que provavelmente é o que você precisa:

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

Então, para ter o comprimento de cada um deles, que o "processamento" seria:

    l = len(inter)

Isso seria bastante eficiente, pois está usando iteradores para calcular todas as combinações e não prepara todos eles com antecedência.

---

Editar: Observe que com este método, cada um conjunto na lista "s" pode realmente ser outra coisa que Retorna um conjunto, como um gerador. A lista em si pode ser simplesmente um gerador se você tiver pouca memória. Pode ser muito mais lento, dependendo de como você gera esses elementos, mas não precisaria ter toda a lista de conjuntos na memória ao mesmo tempo (não que deve ser um problema no seu caso).

Por exemplo, se cada conjunto for feito de uma função 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))

---

Editar 2: Como coletar índices (seguindo o comentário de Redrat).

Além da solução rápida que respondi em comentar, uma maneira mais eficiente de coletar os índices definidos seria ter uma lista de (index, set) em vez de uma lista de set.

Exemplo com novo formato:

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

Se você estiver construindo esta lista para calcular as combinações de qualquer maneira, deve ser simples se adaptar aos seus novos requisitos. O loop principal se torna:

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))

No loop, i[0] e i[1] Seria uma tupla (index, set), assim i[0][1] é o primeiro conjunto, i[0][0] seu índice.

Answer 2

Como você precisa produzir uma matriz (n/2) de resultados, ou seja, as saídas O (n quadradas), nenhuma abordagem pode ser menor que O (n quadrado) - em qualquer idioma, é claro. (N é "cerca de 9k" em sua pergunta). Portanto, não vejo nada intrinsecamente mais rápido do que (a) fazer os n conjuntos de que você precisa e (b) iterando sobre eles para produzir a saída - ou seja, a abordagem mais simples. 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

Esse código já está tentando adicionar uma pequena otimização (por exemplo, evitando fatiar ou sair da frente das listas, o que pode adicionar outros fatores de O (n quadrado)).

Se você tem muitos núcleos e/ou nós disponíveis e está procurando algoritmos paralelos, é um caso diferente, é claro - se esse é o seu caso, você pode mencionar o tipo de cluster que você tem, seu tamanho, como nós e núcleos podem se comunicar melhor , e assim por diante?

Editar: Como o OP mencionou casualmente em um comentário (!) que eles realmente precisam do número de conjuntos sendo intercebidos (realmente, por que omitir partes tão cruciais das especificações?! Pelo menos edite a pergunta para esclarecê -los ...), Isso só exigiria alterar isso para:

  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

(Se você precisar "contar de 1" para os identificadores progressivos - alterações óbvias).

Mas se isso fizer parte das especificações, você também pode usar código mais simples - esqueça as mais.

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

Desta vez, assumindo que você deseja "contar de 0", apenas para variedade ;-)

Answer 3

Experimente isso:

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

E para obter os índices:

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

Saúde,

José María García

PS: Desculpe, eu entendi mal a pergunta