python merge tree set-intersection equivalence-classes

Python: fusión simple de listas basada en intersecciones



intersection python (15)

Usando manipulaciones de matriz

Permítanme comenzar esta respuesta con el siguiente comentario:

ESTA ES LA FORMA INCORRECTA DE HACER ESTO. ES IMPRESCINDIBLE PARA LA INESTABILIDAD NUMÉRICA Y ES MUCHO MÁS LENTO QUE LOS OTROS MÉTODOS PRESENTADOS, USO BAJO SU PROPIO RIESGO.

Dicho esto, no pude resistirme a resolver el problema desde un punto de vista dinámico (y espero que obtengas una nueva perspectiva del problema). En teoría, esto debería funcionar todo el tiempo, pero los cálculos de valores propios a menudo pueden fallar. La idea es pensar en tu lista como un flujo de filas a columnas. Si dos filas comparten un valor común, hay un flujo de conexión entre ellas. Si tuviéramos que pensar en estos flujos como agua, veríamos que los flujos se agrupan en pequeños charcos cuando hay un camino de conexión entre ellos. Para simplificar, voy a usar un conjunto más pequeño, aunque también funciona con tu conjunto de datos:

from numpy import where, newaxis from scipy import linalg, array, zeros X = [[0,1,3],[2],[3,1]]

Necesitamos convertir los datos en un flujograma. Si la fila i fluye hacia el valor j lo ponemos en la matriz. Aquí tenemos 3 filas y 4 valores únicos:

A = zeros((4,len(X)), dtype=float) for i,row in enumerate(X): for val in row: A[val,i] = 1

En general, deberá cambiar el 4 para capturar la cantidad de valores únicos que tiene. Si el conjunto es una lista de enteros comenzando desde 0 como lo tenemos, simplemente puede hacer que este sea el número más grande. Ahora realizamos una descomposición de valores propios. Una SVD para ser exactos, ya que nuestra matriz no es cuadrada.

S = linalg.svd(A)

Queremos mantener solo la porción de 3x3 de esta respuesta, ya que representará el flujo de las piscinas. De hecho, solo queremos los valores absolutos de esta matriz; solo nos importa si hay un flujo en este espacio de grupo .

M = abs(S[2])

Podemos pensar en esta matriz M como una matriz de Markov y hacerla explícita mediante la normalización de filas. Una vez que tenemos esto, calculamos la descomposición de autovalores (izquierda). de esta matriz.

M /= M.sum(axis=1)[:,newaxis] U,V = linalg.eig(M,left=True, right=False) V = abs(V)

Ahora, una matriz de Markov desconectada (no ergódica) tiene la agradable propiedad de que, para cada grupo no conectado, existe un valor propio de unidad. Los autovectores asociados con estos valores de unidad son los que queremos:

idx = where(U > .999)[0] C = V.T[idx] > 0

Tengo que usar .999 debido a la inestabilidad numérica antes mencionada. En este punto, ¡hemos terminado! Cada grupo independiente ahora puede extraer las filas correspondientes:

for cluster in C: print where(A[:,cluster].sum(axis=1))[0]

Que da, como se pretendía:

[0 1 3] [2]

Cambie X a su lst y obtendrá: [ 0 1 3 4 5 10 11 16] [2 8] .

Apéndice

¿Por qué esto podría ser útil? No sé de dónde provienen los datos subyacentes, pero ¿qué sucede cuando las conexiones no son absolutas? Supongamos que la fila 1 tiene la entrada 3 80% del tiempo. ¿Cómo podría generalizar el problema? El método de flujo anterior funcionaría muy bien, y estaría completamente parametrizado por ese valor .999 , cuanto más alejado esté de la unidad, más flexible será la asociación.

Representación visual

Como una imagen vale 1K palabras, aquí están las gráficas de las matrices A y V para mi ejemplo y su lst respectivamente. Observe cómo en V divide en dos grupos (es una matriz de bloques diagonales con dos bloques después de la permutación), ya que para cada ejemplo solo había dos listas únicas.

Implementación más rápida

En retrospectiva, me di cuenta de que puedes omitir el paso SVD y calcular solo una descompilación:

M = dot(A.T,A) M /= M.sum(axis=1)[:,newaxis] U,V = linalg.eig(M,left=True, right=False)

La ventaja de este método (además de la velocidad) es que M ahora es simétrico, por lo tanto, el cálculo puede ser más rápido y más preciso (no hay valores imaginarios de los que preocuparse).

Considere que hay algunas listas de enteros como:

#-------------------------------------- 0 [0,1,3] 1 [1,0,3,4,5,10,...] 2 [2,8] 3 [3,1,0,...] ... n [] #--------------------------------------

La cuestión es fusionar listas que tengan al menos un elemento común. Entonces, los resultados solo para la parte dada serán los siguientes:

#-------------------------------------- 0 [0,1,3,4,5,10,...] 2 [2,8] #--------------------------------------

¿Cuál es la forma más eficiente de hacer esto en datos grandes (los elementos son solo números)? ¿Es tree estructura del tree algo en lo que pensar? Hago el trabajo ahora convirtiendo listas en sets e iterando para intersecciones, ¡pero es lento! ¡Además tengo la sensación de que es muy elemental! Además, la implementación carece de algo (desconocido) porque algunas listas no se mezclan alguna vez. Una vez dicho esto, si propones la auto-implementación, sé generoso y proporciona un código de muestra simple [aparentemente Python es mi favorito :)] o pesudo-código.
Actualización 1: Aquí está el código que estaba usando:

#-------------------------------------- lsts = [[0,1,3], [1,0,3,4,5,10,11], [2,8], [3,1,0,16]]; #--------------------------------------

La función es (con errores !! ):

#-------------------------------------- def merge(lsts): sts = [set(l) for l in lsts] i = 0 while i < len(sts): j = i+1 while j < len(sts): if len(sts[i].intersection(sts[j])) > 0: sts[i] = sts[i].union(sts[j]) sts.pop(j) else: j += 1 #---corrected i += 1 lst = [list(s) for s in sts] return lst #--------------------------------------

El resultado es:

#-------------------------------------- >>> merge(lsts) >>> [0, 1, 3, 4, 5, 10, 11, 16], [8, 2]] #--------------------------------------

Actualización 2: Para mi experiencia, el código proporcionado por Niklas Baumstark a continuación mostró ser un poco más rápido para los casos simples. Todavía no se ha probado el método dado por "Hooked", ya que es un enfoque completamente diferente (por cierto, parece interesante). El procedimiento de prueba para todos estos podría ser realmente difícil o imposible de garantizar los resultados. El conjunto de datos reales que usaré es tan grande y complejo, por lo que es imposible rastrear cualquier error simplemente repitiendo. Es decir, necesito estar 100% satisfecho de la confiabilidad del método antes de empujarlo en su lugar dentro de un código grande como módulo. Simplemente por ahora, el método de Niklas es más rápido y la respuesta para conjuntos simples es correcta, por supuesto.
Sin embargo, ¿cómo puedo estar seguro de que funciona bien para un conjunto de datos realmente grande? ¡Ya que no podré rastrear los errores visualmente!

Actualización 3: tenga en cuenta que la fiabilidad del método es mucho más importante que la velocidad para este problema. Esperemos que pueda traducir el código de Python a Fortran para el máximo rendimiento finalmente.

Actualización 4:
Hay muchos puntos interesantes en este post y respuestas generosamente dadas, comentarios constructivos. Yo recomendaría leer todo a fondo. Por favor, acepte mi agradecimiento por el desarrollo de la pregunta, respuestas sorprendentes y comentarios constructivos y discusión.

Aquí está mi respuesta. No lo he comparado con el lote de respuestas de hoy.

Los algoritmos basados ​​en intersecciones son O (N ^ 2) ya que comprueban cada nuevo conjunto contra todos los existentes, así que utilicé un enfoque que indexa cada número y se ejecuta cerca de O (N) (si aceptamos que las búsquedas de diccionario son O (1)). Luego ejecuté los puntos de referencia y me sentí como un completo idiota porque corría más lento, pero en una inspección más cercana resultó que los datos de prueba terminan con solo un puñado de conjuntos de resultados distintos, por lo que los algoritmos cuadráticos no tienen mucho trabajo para hacer. Pruébalo con más de 10-15 contenedores diferentes y mi algoritmo es mucho más rápido. Pruebe los datos de prueba con más de 50 contenedores diferentes, y es mucho más rápido.

(Editar: También hubo un problema con la forma en que se ejecuta el índice de referencia, pero me equivoqué en mi diagnóstico. Alteré mi código para que funcione con la forma en que se ejecutan las pruebas repetidas).

def mergelists5(data): """Check each number in our arrays only once, merging when we find a number we have seen before. """ bins = range(len(data)) # Initialize each bin[n] == n nums = dict() data = [set(m) for m in data ] # Convert to sets for r, row in enumerate(data): for num in row: if num not in nums: # New number: tag it with a pointer to this row''s bin nums[num] = r continue else: dest = locatebin(bins, nums[num]) if dest == r: continue # already in the same bin if dest > r: dest, r = r, dest # always merge into the smallest bin data[dest].update(data[r]) data[r] = None # Update our indices to reflect the move bins[r] = dest r = dest # Filter out the empty bins have = [ m for m in data if m ] print len(have), "groups in result" return have def locatebin(bins, n): """ Find the bin where list n has ended up: Follow bin references until we find a bin that has not moved. """ while bins[n] != n: n = bins[n] return n

EDITAR: OK, las otras preguntas se han cerrado, publicando aquí.

¡Buena pregunta! Es mucho más simple si lo piensas como un problema de componentes conectados en un gráfico. El siguiente código utiliza la excelente biblioteca de gráficos de networkx y la función de pairs de esta pregunta .

def pairs(lst): i = iter(lst) first = prev = item = i.next() for item in i: yield prev, item prev = item yield item, first lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]] import networkx g = networkx.Graph() for sub_list in lists: for edge in pairs(sub_list): g.add_edge(*edge) networkx.connected_components(g) [[1, 2, 3, 5, 6], [8, 9, 10], [11, 12, 13]]

Explicación

Creamos un nuevo gráfico (vacío) g . Para cada sublista en lists , considere sus elementos como nodos del gráfico y agregue una ventaja entre ellos. (Dado que solo nos preocupa la conectividad, no necesitamos agregar todos los bordes, ¡solo los adyacentes!) Tenga en cuenta que add_edge toma dos objetos, los trata como nodos (y los agrega si no están ya allí), y agrega una ventaja entre ellos.

Entonces, solo encontramos los componentes conectados del gráfico, ¡un problema resuelto! - y darles salida como nuestros conjuntos que se cruzan.

Esta nueva función solo hace la cantidad mínima necesaria de pruebas de disociación, algo que las otras soluciones similares no logran. También utiliza un deque para evitar tantas operaciones de tiempo lineal como sea posible, como el corte y borrado de lista desde el principio de la lista.

from collections import deque def merge(lists): sets = deque(set(lst) for lst in lists if lst) results = [] disjoint = 0 current = sets.pop() while True: merged = False newsets = deque() for _ in xrange(disjoint, len(sets)): this = sets.pop() if not current.isdisjoint(this): current.update(this) merged = True disjoint = 0 else: newsets.append(this) disjoint += 1 if sets: newsets.extendleft(sets) if not merged: results.append(current) try: current = newsets.pop() except IndexError: break disjoint = 0 sets = newsets return results

Cuanta menos superposición entre los conjuntos en un conjunto dado de datos, mejor será esto en comparación con las otras funciones.

Aquí hay un caso de ejemplo. Si tiene 4 juegos, necesita comparar:

1, 2 1, 3 1, 4 2, 3 2, 4 3, 4

Si 1 se superpone con 3, entonces 2 necesita volver a analizarse para ver si ahora se superpone con 1, para omitir con seguridad las pruebas 2 contra 3.

Hay dos formas de lidiar con esto. El primero es reiniciar la prueba del conjunto 1 contra los otros conjuntos después de cada solapamiento y fusión. El segundo es continuar con las pruebas comparando 1 con 4, luego retrocediendo y volviendo a probar. Esto último da como resultado menos pruebas de desajuste, ya que se producen más fusiones en una sola pasada, por lo que en la pasada de nueva prueba, quedan pocos conjuntos para probar.

El problema es rastrear qué conjuntos deben volver a probarse. En el ejemplo anterior, 1 necesita volver a probarse contra 2, pero no contra 4, ya que 1 ya estaba en su estado actual antes de que 4 se probara la primera vez.

El contador disjoint permite rastrear esto.

Mi respuesta no ayuda con el problema principal de encontrar un algoritmo mejorado para la recodificación en FORTRAN; es lo que me parece que es la forma más simple y elegante de implementar el algoritmo en Python.

De acuerdo con mis pruebas (o la prueba en la respuesta aceptada), es un poco (hasta un 10%) más rápido que la siguiente solución más rápida.

def merge0(lists): newsets, sets = [set(lst) for lst in lists if lst], [] while len(sets) != len(newsets): sets, newsets = newsets, [] for aset in sets: for eachset in newsets: if not aset.isdisjoint(eachset): eachset.update(aset) break else: newsets.append(aset) return newsets

No es necesario contar con los contadores no pitonicos ( i , range ) o la mutación complicada ( del , pop , insert ) utilizados en las otras implementaciones. Utiliza solo iteraciones simples, combina conjuntos superpuestos de la manera más simple y crea una lista nueva y única en cada pasada a través de los datos.

Mi (más rápida y simple) versión del código de prueba:

import random tenk = range(10000) lsts = [random.sample(tenk, random.randint(0, 500)) for _ in range(2000)] setup = """ def merge0(lists): newsets, sets = [set(lst) for lst in lists if lst], [] while len(sets) != len(newsets): sets, newsets = newsets, [] for aset in sets: for eachset in newsets: if not aset.isdisjoint(eachset): eachset.update(aset) break else: newsets.append(aset) return newsets def merge1(lsts): sets = [set(lst) for lst in lsts if lst] merged = 1 while merged: merged = 0 results = [] while sets: common, rest = sets[0], sets[1:] sets = [] for x in rest: if x.isdisjoint(common): sets.append(x) else: merged = 1 common |= x results.append(common) sets = results return sets lsts = """ + repr(lsts) import timeit print timeit.timeit("merge0(lsts)", setup=setup, number=10) print timeit.timeit("merge1(lsts)", setup=setup, number=10)

Intenté resumir todo lo que se dijo y se hizo sobre este tema en esta pregunta y en la pregunta duplicada .

Traté de probar y programar cada solución (todo el código here ).

Pruebas

Este es el TestCase del módulo de prueba:

class MergeTestCase(unittest.TestCase): def setUp(self): with open(''./lists/test_list.txt'') as f: self.lsts = json.loads(f.read()) self.merged = self.merge_func(deepcopy(self.lsts)) def test_disjoint(self): """Check disjoint-ness of merged results""" from itertools import combinations for a,b in combinations(self.merged, 2): self.assertTrue(a.isdisjoint(b)) def test_coverage(self): # Credit to katrielalex """Check coverage original data""" merged_flat = set() for s in self.merged: merged_flat |= s original_flat = set() for lst in self.lsts: original_flat |= set(lst) self.assertTrue(merged_flat == original_flat) def test_subset(self): # Credit to WolframH """Check that every original data is a subset""" for lst in self.lsts: self.assertTrue(any(set(lst) <= e for e in self.merged))

Esta prueba supone una lista de conjuntos como resultado, por lo que no pude probar un par de suturas que funcionaron con listas.

No pude probar lo siguiente:

katrielalex steabert

Entre los que pude probar, dos fallaron :

-- Going to test: agf (optimized) -- Check disjoint-ness of merged results ... FAIL -- Going to test: robert king -- Check disjoint-ness of merged results ... FAIL

Sincronización

Las actuaciones están fuertemente relacionadas con la prueba de datos empleada.

Hasta ahora, tres respuestas intentaron cronometrar la suya y la de los demás. Como usaron diferentes datos de prueba, tuvieron resultados diferentes.

  1. Niklas benchmark es muy versátil. Con su marca registrada, uno podría hacer diferentes pruebas cambiando algunos parámetros.

    He usado los mismos tres parámetros que usó en su propia respuesta, y los puse en tres archivos diferentes:

    filename = ''./lists/timing_1.txt'' class_count = 50, class_size = 1000, list_count_per_class = 100, large_list_sizes = (100, 1000), small_list_sizes = (0, 100), large_list_probability = 0.5, filename = ''./lists/timing_2.txt'' class_count = 15, class_size = 1000, list_count_per_class = 300, large_list_sizes = (100, 1000), small_list_sizes = (0, 100), large_list_probability = 0.5, filename = ''./lists/timing_3.txt'' class_count = 15, class_size = 1000, list_count_per_class = 300, large_list_sizes = (100, 1000), small_list_sizes = (0, 100), large_list_probability = 0.1,

    Estos son los resultados que obtuve:

    Del archivo: timing_1.txt

    Timing with: >> Niklas << Benchmark Info: 5000 lists, average size 305, max size 999 Timing Results: 10.434 -- alexis 11.476 -- agf 11.555 -- Niklas B. 13.622 -- Rik. Poggi 14.016 -- agf (optimized) 14.057 -- ChessMaster 20.208 -- katrielalex 21.697 -- steabert 25.101 -- robert king 76.870 -- Sven Marnach 133.399 -- hochl

    Del archivo: timing_2.txt

    Timing with: >> Niklas << Benchmark Info: 4500 lists, average size 305, max size 999 Timing Results: 8.247 -- Niklas B. 8.286 -- agf 8.637 -- Rik. Poggi 8.967 -- alexis 9.090 -- ChessMaster 9.091 -- agf (optimized) 18.186 -- katrielalex 19.543 -- steabert 22.852 -- robert king 70.486 -- Sven Marnach 104.405 -- hochl

    Del archivo: timing_3.txt

    Timing with: >> Niklas << Benchmark Info: 4500 lists, average size 98, max size 999 Timing Results: 2.746 -- agf 2.850 -- Niklas B. 2.887 -- Rik. Poggi 2.972 -- alexis 3.077 -- ChessMaster 3.174 -- agf (optimized) 5.811 -- katrielalex 7.208 -- robert king 9.193 -- steabert 23.536 -- Sven Marnach 37.436 -- hochl

  2. Con los datos de prueba de Sven obtuve los siguientes resultados:

    Timing with: >> Sven << Benchmark Info: 200 lists, average size 10, max size 10 Timing Results: 2.053 -- alexis 2.199 -- ChessMaster 2.410 -- agf (optimized) 3.394 -- agf 3.398 -- Rik. Poggi 3.640 -- robert king 3.719 -- steabert 3.776 -- Niklas B. 3.888 -- hochl 4.610 -- Sven Marnach 5.018 -- katrielalex

  3. Y finalmente con el punto de referencia de Agf obtuve:

    Timing with: >> Agf << Benchmark Info: 2000 lists, average size 246, max size 500 Timing Results: 3.446 -- Rik. Poggi 3.500 -- ChessMaster 3.520 -- agf (optimized) 3.527 -- Niklas B. 3.527 -- agf 3.902 -- hochl 5.080 -- alexis 15.997 -- steabert 16.422 -- katrielalex 18.317 -- robert king 1257.152 -- Sven Marnach

Como dije al principio, todo el código está disponible en here . Todas las funciones de fusión están en un archivo llamado core.py , cada función allí con su nombre que termina en _merge se cargará automáticamente durante las pruebas, por lo que no debería ser difícil agregar / probar / mejorar su propia solución.

Déjame saber también si hay algo mal, ha habido mucha codificación y podría usar un par de ojos nuevos :)

Mi intento:

def merge(lsts): sets = [set(lst) for lst in lsts if lst] merged = 1 while merged: merged = 0 results = [] while sets: common, rest = sets[0], sets[1:] sets = [] for x in rest: if x.isdisjoint(common): sets.append(x) else: merged = 1 common |= x results.append(common) sets = results return sets lst = [[65, 17, 5, 30, 79, 56, 48, 62], [6, 97, 32, 93, 55, 14, 70, 32], [75, 37, 83, 34, 9, 19, 14, 64], [43, 71], [], [89, 49, 1, 30, 28, 3, 63], [35, 21, 68, 94, 57, 94, 9, 3], [16], [29, 9, 97, 43], [17, 63, 24]] print merge(lst)

Punto de referencia:

import random # adapt parameters to your own usage scenario class_count = 50 class_size = 1000 list_count_per_class = 100 large_list_sizes = list(range(100, 1000)) small_list_sizes = list(range(0, 100)) large_list_probability = 0.5 if False: # change to true to generate the test data file (takes a while) with open("/tmp/test.txt", "w") as f: lists = [] classes = [range(class_size*i, class_size*(i+1)) for i in range(class_count)] for c in classes: # distribute each class across ~300 lists for i in xrange(list_count_per_class): lst = [] if random.random() < large_list_probability: size = random.choice(large_list_sizes) else: size = random.choice(small_list_sizes) nums = set(c) for j in xrange(size): x = random.choice(list(nums)) lst.append(x) nums.remove(x) random.shuffle(lst) lists.append(lst) random.shuffle(lists) for lst in lists: f.write(" ".join(str(x) for x in lst) + "/n") setup = """ # Niklas'' def merge_niklas(lsts): sets = [set(lst) for lst in lsts if lst] merged = 1 while merged: merged = 0 results = [] while sets: common, rest = sets[0], sets[1:] sets = [] for x in rest: if x.isdisjoint(common): sets.append(x) else: merged = 1 common |= x results.append(common) sets = results return sets # Rik''s def merge_rik(data): sets = (set(e) for e in data if e) results = [next(sets)] for e_set in sets: to_update = [] for i,res in enumerate(results): if not e_set.isdisjoint(res): to_update.insert(0,i) if not to_update: results.append(e_set) else: last = results[to_update.pop(-1)] for i in to_update: last |= results[i] del results[i] last |= e_set return results # katrielalex''s def pairs(lst): i = iter(lst) first = prev = item = i.next() for item in i: yield prev, item prev = item yield item, first import networkx def merge_katrielalex(lsts): g = networkx.Graph() for lst in lsts: for edge in pairs(lst): g.add_edge(*edge) return networkx.connected_components(g) # agf''s (optimized) from collections import deque def merge_agf_optimized(lists): sets = deque(set(lst) for lst in lists if lst) results = [] disjoint = 0 current = sets.pop() while True: merged = False newsets = deque() for _ in xrange(disjoint, len(sets)): this = sets.pop() if not current.isdisjoint(this): current.update(this) merged = True disjoint = 0 else: newsets.append(this) disjoint += 1 if sets: newsets.extendleft(sets) if not merged: results.append(current) try: current = newsets.pop() except IndexError: break disjoint = 0 sets = newsets return results # agf''s (simple) def merge_agf_simple(lists): newsets, sets = [set(lst) for lst in lists if lst], [] while len(sets) != len(newsets): sets, newsets = newsets, [] for aset in sets: for eachset in newsets: if not aset.isdisjoint(eachset): eachset.update(aset) break else: newsets.append(aset) return newsets # alexis'' def merge_alexis(data): bins = range(len(data)) # Initialize each bin[n] == n nums = dict() data = [set(m) for m in data ] # Convert to sets for r, row in enumerate(data): for num in row: if num not in nums: # New number: tag it with a pointer to this row''s bin nums[num] = r continue else: dest = locatebin(bins, nums[num]) if dest == r: continue # already in the same bin if dest > r: dest, r = r, dest # always merge into the smallest bin data[dest].update(data[r]) data[r] = None # Update our indices to reflect the move bins[r] = dest r = dest # Filter out the empty bins have = [ m for m in data if m ] return have def locatebin(bins, n): while bins[n] != n: n = bins[n] return n lsts = [] size = 0 num = 0 max = 0 for line in open("/tmp/test.txt", "r"): lst = [int(x) for x in line.split()] size += len(lst) if len(lst) > max: max = len(lst) num += 1 lsts.append(lst) """ setup += """ print "%i lists, {class_count} equally distributed classes, average size %i, max size %i" % (num, size/num, max) """.format(class_count=class_count) import timeit print "niklas" print timeit.timeit("merge_niklas(lsts)", setup=setup, number=3) print "rik" print timeit.timeit("merge_rik(lsts)", setup=setup, number=3) print "katrielalex" print timeit.timeit("merge_katrielalex(lsts)", setup=setup, number=3) print "agf (1)" print timeit.timeit("merge_agf_optimized(lsts)", setup=setup, number=3) print "agf (2)" print timeit.timeit("merge_agf_simple(lsts)", setup=setup, number=3) print "alexis" print timeit.timeit("merge_alexis(lsts)", setup=setup, number=3)

Estos tiempos dependen obviamente de los parámetros específicos del punto de referencia, como el número de clases, el número de listas, el tamaño de la lista, etc. Adapte esos parámetros a su necesidad para obtener resultados más útiles.

A continuación hay algunos ejemplos de salidas en mi máquina para diferentes parámetros. Muestran que todos los algoritmos tienen sus puntos fuertes y débiles, según el tipo de información que obtienen:

===================== # many disjoint classes, large lists class_count = 50 class_size = 1000 list_count_per_class = 100 large_list_sizes = list(range(100, 1000)) small_list_sizes = list(range(0, 100)) large_list_probability = 0.5 ===================== niklas 5000 lists, 50 equally distributed classes, average size 298, max size 999 4.80084705353 rik 5000 lists, 50 equally distributed classes, average size 298, max size 999 9.49251699448 katrielalex 5000 lists, 50 equally distributed classes, average size 298, max size 999 21.5317108631 agf (1) 5000 lists, 50 equally distributed classes, average size 298, max size 999 8.61671280861 agf (2) 5000 lists, 50 equally distributed classes, average size 298, max size 999 5.18117713928 => alexis => 5000 lists, 50 equally distributed classes, average size 298, max size 999 => 3.73504281044 =================== # less number of classes, large lists class_count = 15 class_size = 1000 list_count_per_class = 300 large_list_sizes = list(range(100, 1000)) small_list_sizes = list(range(0, 100)) large_list_probability = 0.5 =================== niklas 4500 lists, 15 equally distributed classes, average size 296, max size 999 1.79993700981 rik 4500 lists, 15 equally distributed classes, average size 296, max size 999 2.58237695694 katrielalex 4500 lists, 15 equally distributed classes, average size 296, max size 999 19.5465381145 agf (1) 4500 lists, 15 equally distributed classes, average size 296, max size 999 2.75445604324 => agf (2) => 4500 lists, 15 equally distributed classes, average size 296, max size 999 => 1.77850699425 alexis 4500 lists, 15 equally distributed classes, average size 296, max size 999 3.23530197144 =================== # less number of classes, smaller lists class_count = 15 class_size = 1000 list_count_per_class = 300 large_list_sizes = list(range(100, 1000)) small_list_sizes = list(range(0, 100)) large_list_probability = 0.1 =================== niklas 4500 lists, 15 equally distributed classes, average size 95, max size 997 0.773697137833 rik 4500 lists, 15 equally distributed classes, average size 95, max size 997 1.0523750782 katrielalex 4500 lists, 15 equally distributed classes, average size 95, max size 997 6.04466891289 agf (1) 4500 lists, 15 equally distributed classes, average size 95, max size 997 1.20285701752 => agf (2) => 4500 lists, 15 equally distributed classes, average size 95, max size 997 => 0.714507102966 alexis 4500 lists, 15 equally distributed classes, average size 95, max size 997 1.1286110878

Firstly I''m not exactly sure if the benchmarks are fair:

Adding the following code to the start of my function:

c = Counter(chain(*lists)) print c[1] "88"

This means that out of all the values in all the lists, there are only 88 distinct values. Usually in the real world duplicates are rare, and you would expect a lot more distinct values. (of course i don''t know where your data from so can''t make assumptions).

Because Duplicates are more common, it means sets are less likely to be disjoint. This means the set.isdisjoint() method will be much faster because only after a few tests it will find that the sets aren''t disjoint.

Having said all that, I do believe the methods presented that use disjoint are the fastest anyway, but i''m just saying, instead of being 20x faster maybe they should only be 10x faster than the other methods with different benchmark testing.

Anyway, i Thought I would try a slightly different technique to solve this, however the merge sorting was too slow, this method is about 20x slower than the two fastest methods using the benchmarking:

I thought I would order everything

import heapq from itertools import chain def merge6(lists): for l in lists: l.sort() one_list = heapq.merge(*[zip(l,[i]*len(l)) for i,l in enumerate(lists)]) #iterating through one_list takes 25 seconds!! previous = one_list.next() d = {i:i for i in range(len(lists))} for current in one_list: if current[0]==previous[0]: d[current[1]] = d[previous[1]] previous=current groups=[[] for i in range(len(lists))] for k in d: groups[d[k]].append(lists[k]) #add a each list to its group return [set(chain(*g)) for g in groups if g] #since each subroup in each g is sorted, it would be faster to merge these subgroups removing duplicates along the way. lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]] print merge6(lists) "[set([1, 2, 3, 5, 6]), set([8, 9, 10]), set([11, 12, 13])]"" import timeit print timeit.timeit("merge1(lsts)", setup=setup, number=10) print timeit.timeit("merge4(lsts)", setup=setup, number=10) print timeit.timeit("merge6(lsts)", setup=setup, number=10) 5000 lists, 5 classes, average size 74, max size 1000 1.26732238315 5000 lists, 5 classes, average size 74, max size 1000 1.16062907437 5000 lists, 5 classes, average size 74, max size 1000 30.7257182826

Here''s a function (Python 3.1) to check if the result of a merge function is OK. It checks:

  • Are the result sets disjoint? (number of elements of union == sum of numbers of elements)
  • Are the elements of the result sets the same as of the input lists?
  • Is every input list a subset of a result set?
  • Is every result set minimal, ie is it impossible to split it into two smaller sets?
  • It does not check if there are empty result sets - I don''t know if you want them or not...

.

from itertools import chain def check(lsts, result): lsts = [set(s) for s in lsts] all_items = set(chain(*lsts)) all_result_items = set(chain(*result)) num_result_items = sum(len(s) for s in result) if num_result_items != len(all_result_items): print("Error: result sets overlap!") print(num_result_items, len(all_result_items)) print(sorted(map(len, result)), sorted(map(len, lsts))) if all_items != all_result_items: print("Error: result doesn''t match input lists!") if not all(any(set(s).issubset(t) for t in result) for s in lst): print("Error: not all input lists are contained in a result set!") seen = set() todo = list(filter(bool, lsts)) done = False while not done: deletes = [] for i, s in enumerate(todo): # intersection with seen, or with unseen result set, is OK if not s.isdisjoint(seen) or any(t.isdisjoint(seen) for t in result if not s.isdisjoint(t)): seen.update(s) deletes.append(i) for i in reversed(deletes): del todo[i] done = not deletes if todo: print("Error: A result set should be split into two or more parts!") print(todo)

Here''s an implementation using a disjoint-set data structure (specifically a disjoint forest), thanks to comingstorm''s hint at merging sets which have even one element in common . I''m using path compression for a slight (~5%) speed improvement; it''s not entirely necessary (and it prevents find being tail recursive, which could slow things down). Note that I''m using a dict to represent the disjoint forest; given that the data are int s, an array would also work although it might not be much faster.

def merge(data): parents = {} def find(i): j = parents.get(i, i) if j == i: return i k = find(j) if k != j: parents[i] = k return k for l in filter(None, data): parents.update(dict.fromkeys(map(find, l), find(l[0]))) merged = {} for k, v in parents.items(): merged.setdefault(find(v), []).append(k) return merged.values()

This approach is comparable to the other best algorithms on Rik''s benchmarks.

Just for fun...

def merge(mylists): results, sets = [], [set(lst) for lst in mylists if lst] upd, isd, pop = set.update, set.isdisjoint, sets.pop while sets: if not [upd(sets[0],pop(i)) for i in xrange(len(sets)-1,0,-1) if not isd(sets[0],sets[i])]: results.append(pop(0)) return results

and my rewrite of the best answer

def merge(lsts): sets = map(set,lsts) results = [] while sets: first, rest = sets[0], sets[1:] merged = False sets = [] for s in rest: if s and s.isdisjoint(first): sets.append(s) else: first |= s merged = True if merged: sets.append(first) else: results.append(first) return results

My solution, works well on small lists and is quite readable without dependencies.

def merge_list(starting_list): final_list = [] for i,v in enumerate(starting_list[:-1]): if set(v)&set(starting_list[i+1]): starting_list[i+1].extend(list(set(v) - set(starting_list[i+1]))) else: final_list.append(v) final_list.append(starting_list[-1]) return final_list

Benchmarking it:

lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]]

%timeit merge_list(lists)

100000 loops, best of 3: 4.9 µs per loop

This can be solved in O(n) by using the union-find algorithm. Given the first two rows of your data, edges to use in the union-find are the following pairs: (0,1),(1,3),(1,0),(0,3),(3,4),(4,5),(5,10)

This is slower than the solution offered by Niklas (I got 3.9s on the test.txt instead of 0.5s for his solution), but yields the same result and might be easier to implement in eg Fortran, since it doesn''t use sets, only sorting of the total amount of elements and then a single run through all of them.

It returns a list with the ids of the merged lists, so also keeps track of empty lists, they stay unmerged.

def merge(lsts): # this is an index list that stores the joined id for each list joined = range(len(lsts)) # create an ordered list with indices indexed_list = sorted((el,index) for index,lst in enumerate(lsts) for el in lst) # loop throught the ordered list, and if two elements are the same and # the lists are not yet joined, alter the list with joined id el_0,idx_0 = None,None for el,idx in indexed_list: if el == el_0 and joined[idx] != joined[idx_0]: old = joined[idx] rep = joined[idx_0] joined = [rep if id == old else id for id in joined] el_0, idx_0 = el, idx return joined

This would be my updated approach:

def merge(data): sets = (set(e) for e in data if e) results = [next(sets)] for e_set in sets: to_update = [] for i,res in enumerate(results): if not e_set.isdisjoint(res): to_update.insert(0,i) if not to_update: results.append(e_set) else: last = results[to_update.pop(-1)] for i in to_update: last |= results[i] del results[i] last |= e_set return results

Note: During the merging empty lists will be removed.

Update: Reliability.

You need two tests for a 100% reliabilty of success:

  • Check that all the resulting sets are mutually disjointed:

    merged = [{0, 1, 3, 4, 5, 10, 11, 16}, {8, 2}, {8}] from itertools import combinations for a,b in combinations(merged,2): if not a.isdisjoint(b): raise Exception(a,b) # just an example

  • Check that the merged set cover the original data. (as suggested by katrielalex)

I think this will take some time, but maybe it''ll be worth it if you want to be 100% sure.

lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]] import networkx as nx g = nx.Graph() for sub_list in lists: for i in range(1,len(sub_list)): g.add_edge(sub_list[0],sub_list[i]) print nx.connected_components(g) #[[1, 2, 3, 5, 6], [8, 9, 10], [11, 12, 13]]

Actuación:

5000 lists, 5 classes, average size 74, max size 1000 15.2264976415

Performance of merge1:

print timeit.timeit("merge1(lsts)", setup=setup, number=10) 5000 lists, 5 classes, average size 74, max size 1000 1.26998780571

So it is 11x slower than the fastest.. but the code is much more simple and readable!