Dada la lista a = [1, 2, 2, 3] y su sublista b = [1, 2] encuentre una lista que complemente b de tal manera que sorted(a) == sorted(b + complement) . En el ejemplo anterior, el complement sería una lista de [2, 3] .
Es tentador usar la comprensión de listas:
complement = [x for x in a if x not in b]o conjuntos:
complement = list(set(a) - set(b)) Sin embargo, ambas formas devolverán complement = [3] .
Una forma obvia de hacerlo sería:
complement = a[:] for element in b: complement.remove(element)Pero eso se siente profundamente insatisfactorio y no muy pitónico . ¿Me estoy perdiendo un modismo obvio o es este el camino?
Como se señala a continuación, ¿qué pasa con el rendimiento? Esto es O(n^2) ¿Hay una forma más eficiente?
La única forma más declarativa y, por lo tanto, pitónica que me viene a la mente y que mejora el rendimiento para grandes b (y a ) es usar algún tipo de contador con decremento:
from collections import Counter class DecrementCounter(Counter): def decrement(self,x): if self[x]: self[x] -= 1 return True return FalseAhora podemos usar la comprensión de listas:
b_count = DecrementCounter(b) complement = [x for x in a if not b_count.decrement(x)] Aquí hacemos un seguimiento de los conteos en b , para cada elemento en a buscamos si es parte de b_count . Si ese es el caso, decrementamos el contador e ignoramos el elemento. En caso contrario lo añadimos al complement . Tenga en cuenta que esto solo funciona si estamos seguros de que existe dicho complement .
Después de haber construido el complement , puede verificar si el complemento existe con:
not bool(+b_count) Si esto es False , entonces dicho complemento no se puede construir (por ejemplo a=[1] y b=[1,3] ). Así que una implementación completa podría ser:
b_count = DecrementCounter(b) complement = [x for x in a if not b_count.decrement(x)] if +b_count: raise ValueError('complement cannot be constructed') Si la búsqueda en el diccionario se ejecuta en O(1) (lo que suele ocurrir, solo en raras ocasiones es O(n) ), entonces este algoritmo se ejecuta en O(|a|+|b|) (por lo que la suma de los tamaños de las listas). Mientras que el enfoque de remove generalmente se ejecutará en O(|a|×|b|) .
Para reducir la complejidad de su enfoque ya válido, puede usar collections.Counter . Contador (que es un diccionario especializado con búsqueda rápida) para contar elementos en ambas listas.
Luego, actualice el conteo restando valores y, al final, filtre la lista manteniendo solo los elementos cuyo conteo sea> 0 y reconstruya/encadene usando itertools.chain
from collections import Counter import itertools a = [1, 2, 2, 2, 3] b = [1, 2] print(list(itertools.chain.from_iterable(x*[k] for k,x in (Counter(a)-Counter(b)).items() if x > 0)))resultado:
[2, 2, 3]O(n registro n)
a = [1, 2, 2, 3] b = [1, 2] a.sort() b.sort() L = [] i = j = 0 while i < len(a) and j < len(b): if a[i] < b[j]: L.append(a[i]) i += 1 elif a[i] > b[j]: L.append(b[j]) j += 1 else: i += 1 j += 1 while i < len(a): L.append(a[i]) i += 1 while j < len(b): L.append(b[j]) j += 1 print(L)