Python: extracción rápida de intersecciones entre todas las posibles 2 combinaciones en un gran número de listas

Tengo un conjunto de datos de ca. Listas de 9K de longitud variable (1 a 100K elementos). Necesito calcular la longitud de la intersección de todas las combinaciones posibles de 2 listas en este conjunto de datos. Tenga en cuenta que los elementos de cada lista son únicos, por lo que se pueden almacenar como conjuntos en python.

¿Cuál es la forma más eficiente de realizar esto en python?

Editar Olvidé especificar que debo tener la capacidad de hacer coincidir los valores de intersección con el par de listas correspondiente. ¡Gracias a todos por la pronta respuesta y disculpas por la confusión!

Si tus sets están almacenados en s, por ejemplo:

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

Luego puede usar itertools.combinations para tomarlos de dos en dos y calcular la intersección (tenga en cuenta que, como señaló Alex, las combinations solo están disponibles desde la versión 2.6). Aquí con una lista de comprensión (solo por el ejemplo):

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

O, en un bucle, que es probablemente lo que necesitas:

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

Entonces, para tener la longitud de cada uno de ellos, ese “procesamiento” sería:

  l = len(inter) 

Esto sería bastante eficiente, ya que está utilizando iteradores para calcular cada combinación y no los prepara de antemano.


Edición : Tenga en cuenta que con este método, cada conjunto de la lista “s” puede ser otra cosa que devuelva un conjunto , como un generador. La lista en sí misma podría ser simplemente un generador si tiene poca memoria. Sin embargo, podría ser mucho más lento, dependiendo de cómo genere estos elementos, pero no necesitaría tener toda la lista de conjuntos en la memoria al mismo tiempo (no es que deba ser un problema en su caso).

Por ejemplo, si cada conjunto está hecho a partir de una función 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)) 

Edición 2 : Cómo recostackr índices (siguiendo el comentario de redrat).

Además de la solución rápida que respondí en el comentario, una forma más eficiente de recostackr los índices establecidos sería tener una lista de (index, set) lugar de una lista de set .

Ejemplo con nuevo formato:

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

Si está creando esta lista para calcular las combinaciones de todos modos, debería ser sencillo adaptarse a sus nuevos requisitos. El bucle principal se convierte en:

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

En el bucle, i[0] e i[1] serían una tupla (index, set) , por lo que i[0][1] es el primer conjunto, i[0][0] su índice.

Como necesita producir una matriz de resultados (N por N / 2), es decir, salidas O (N al cuadrado), ningún enfoque puede ser menor que O (N al cuadrado) en cualquier idioma, por supuesto. (N es “sobre 9K” en tu pregunta). Por lo tanto, no veo nada intrínsecamente más rápido que (a) hacer los N conjuntos que necesita, y (b) iterar sobre ellos para producir la salida, es decir, el enfoque más simple. 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 

Este código ya está intentando agregar una pequeña optimización (por ejemplo, evitando cortar o desprenderse del frente de las listas, lo que podría agregar otros factores O (N al cuadrado)).

Si tiene muchos núcleos y / o nodos disponibles y está buscando algoritmos paralelos, es un caso diferente, por supuesto, si ese es su caso, ¿puede mencionar el tipo de clúster que tiene, su tamaño, la forma en que los nodos y los núcleos pueden comunicarse mejor? , ¿Etcétera?

Edición : como el OP ha mencionado casualmente en un comentario (!) Que realmente necesitan los números de los conjuntos que se intersectan (en realidad, ¿por qué omitir esas partes cruciales de las especificaciones? Al menos, edite la pregunta para aclararlas …) , esto solo requeriría cambiar esto a:

  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 

(Si necesita “contar desde 1” para los identificadores progresivos, de lo contrario, será un cambio obvio).

Pero si eso es parte de las especificaciones, también podrías usar un código más simple: olvida los conjuntos de herramientas y:

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

esta vez suponiendo que desea “contar desde 0” en su lugar, solo por variedad 😉

Prueba esto:

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

Y para obtener los índices:

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

Aclamaciones,

José María García

PD: Perdón, entendí mal la pregunta