python list optimization flatten

python - Aplanar una lista irregular de listas



optimization flatten (30)

Aquí está la implementación compiler.ast.flatten en 2.7.5:

def flatten(seq): l = [] for elt in seq: t = type(elt) if t is tuple or t is list: for elt2 in flatten(elt): l.append(elt2) else: l.append(elt) return l

Hay métodos mejores y más rápidos (si has llegado hasta aquí, ya los has visto)

También tenga en cuenta:

En desuso desde la versión 2.6: el paquete del compilador se ha eliminado en Python 3.

Sí, sé que este tema se ha tratado anteriormente ( here , here , here , here ), pero hasta donde sé, todas las soluciones, excepto una, fallan en una lista como esta

L = [[[1, 2, 3], [4, 5]], 6]

Donde la salida deseada es

[1, 2, 3, 4, 5, 6]

O quizás incluso mejor, un iterador. La única solución que vi que funciona para un anidamiento arbitrario se encuentra here :

def flatten(x): result = [] for el in x: if hasattr(el, "__iter__") and not isinstance(el, basestring): result.extend(flatten(el)) else: result.append(el) return result flatten(L)

¿Es este el mejor modelo? ¿Pasé por alto algo? ¿Algún problema?


Aquí está mi versión funcional de aplanamiento recursivo que maneja tanto las tuplas como las listas, y le permite agregar cualquier combinación de argumentos posicionales. Devuelve un generador que produce la secuencia completa en orden, arg por arg:

flatten = lambda *n: (e for a in n for e in (flatten(*a) if isinstance(a, (tuple, list)) else (a,)))

Uso:

l1 = [''a'', [''b'', (''c'', ''d'')]] l2 = [0, 1, (2, 3), [[4, 5, (6, 7, (8,), [9]), 10]], (11,)] print list(flatten(l1, -2, -1, l2)) [''a'', ''b'', ''c'', ''d'', -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]


Aquí hay otra respuesta que es aún más interesante ...

import re def Flatten(TheList): a = str(TheList) b,crap = re.subn(r''[/[,/]]'', '' '', a) c = b.split() d = [int(x) for x in c] return(d)

Básicamente, convierte la lista anidada en una cadena, usa una expresión regular para eliminar la sintaxis anidada y luego convierte el resultado de nuevo a una lista (aplanada).


Aquí hay otro enfoque de py2, no estoy seguro si es el más rápido o el más elegante ni el más seguro ...

from collections import Iterable from itertools import imap, repeat, chain def flat(seqs, ignore=(int, long, float, basestring)): return repeat(seqs, 1) if any(imap(isinstance, repeat(seqs), ignore)) or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs))

Puede ignorar cualquier tipo específico (o derivado) que le gustaría, devuelve un iterador, por lo que puede convertirlo a cualquier contenedor específico como lista, tupla, dict o simplemente consumirlo para reducir el espacio de memoria, para bien o para mal. puede manejar objetos iniciales no iterables como int ...

Tenga en cuenta que la mayor parte del trabajo pesado se realiza en C, ya que por lo que sé cómo se implementan sus herramientas, por lo que, si bien es recursivo, AFAIK no está limitado por la profundidad de recursión de python, ya que las llamadas a funciones están ocurriendo en C, aunque esto no significa que esté limitado por la memoria, especialmente en OS X, donde su tamaño de pila tiene un límite estricto a partir de hoy (OS X Mavericks) ...

hay un enfoque un poco más rápido, pero un método menos portátil, solo utilícelo si puede asumir que los elementos básicos de la entrada pueden determinarse explícitamente de lo contrario, obtendrá una recursión infinita, y OS X con su tamaño de pila limitado, lanzar una falla de segmentación bastante rápido ...

def flat(seqs, ignore={int, long, float, str, unicode}): return repeat(seqs, 1) if type(seqs) in ignore or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs))

aquí estamos usando conjuntos para verificar el tipo, por lo que se necesita O (1) vs O (número de tipos) para verificar si un elemento debe ignorarse o no, aunque, por supuesto, cualquier valor con el tipo derivado de los tipos ignorados declarados fallará , esta es la razón por la que usa str , unicode , así que utilízalo con precaución ...

pruebas:

import random def test_flat(test_size=2000): def increase_depth(value, depth=1): for func in xrange(depth): value = repeat(value, 1) return value def random_sub_chaining(nested_values): for values in nested_values: yield chain((values,), chain.from_iterable(imap(next, repeat(nested_values, random.randint(1, 10))))) expected_values = zip(xrange(test_size), imap(str, xrange(test_size))) nested_values = random_sub_chaining((increase_depth(value, depth) for depth, value in enumerate(expected_values))) assert not any(imap(cmp, chain.from_iterable(expected_values), flat(chain(((),), nested_values, ((),))))) >>> test_flat() >>> list(flat([[[1, 2, 3], [4, 5]], 6])) [1, 2, 3, 4, 5, 6] >>> $ uname -a Darwin Samys-MacBook-Pro.local 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun 3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64 $ python --version Python 2.7.5


Aquí hay una función simple que aplana las listas de profundidad arbitraria. Sin recursión, para evitar el desbordamiento de pila.

from copy import deepcopy def flatten_list(nested_list): """Flatten an arbitrarily nested list, without recursion (to avoid s). Returns a new list, the original list is unchanged. >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]])) [1, 2, 3, 4, 5] >> list(flatten_list([[1, 2], 3])) [1, 2, 3] """ nested_list = deepcopy(nested_list) while nested_list: sublist = nested_list.pop(0) if isinstance(sublist, list): nested_list = sublist + nested_list else: yield sublist


Aunque se ha seleccionado una respuesta elegante y muy pitónica, presentaría mi solución solo para la revisión:

def flat(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flat(i)) else: ret.append(i) return ret

Por favor, dime cuán bueno o malo es este código?


De mi respuesta anterior , esta función aplana la mayoría de los casos que se me ocurren. Creo que esto funciona hasta Python 2.3.

def flatten(item, keepcls=(), keepobj=()): if not hasattr(item, ''__iter__'') or isinstance(item, keepcls) or item in keepobj: yield item else: for i in item: for j in flatten(i, keepcls, keepobj + (item,)): yield j

Listas circulares

>>> list(flatten([1, 2, [...], 3])) [1, 2, [1, 2, [...], 3], 3]

Profundidad primeras listas

>>> list(flatten([[[1, 2, 3], [4, 5]], 6])) [1, 2, 3, 4, 5, 6]

Listas repetidas anidadas :

>>> list(flatten([[1,2],[1,[1,2]],[1,2]])) [1, 2, 1, 1, 2, 1, 2]

Listas con dados (u otros objetos para no aplanar)

>>> list(flatten([1,2, {''a'':1, ''b'':2}, ''text''], keepcls=(dict, str))) [1, 2, {''a'': 1, ''b'': 2}, ''text'']

Cualquier iterable

>>> list(flatten((x for x in [1,2, set([3,(4,5),6])]))) [1, 2, 4, 5, 3, 6]

Es posible que desee mantener algunas clases predeterminadas en keepcls para que la llamada a la función sea más concisa.


El uso de las funciones del generador puede hacer que su ejemplo sea un poco más fácil de leer y probablemente aumente el rendimiento.

Python 2

def flatten(l): for el in l: if isinstance(el, collections.Iterable) and not isinstance(el, basestring): for sub in flatten(el): yield sub else: yield el

Utilicé el Iterable ABC agregado en 2.6.

Python 3

En Python 3, la basestring ya no existe, pero puedes usar una tupla de str y bytes para obtener el mismo efecto allí.

El yield from operador devuelve un artículo de un generador de uno en uno. Esta sintaxis para delegar a un subgenerador se agregó en 3.3

def flatten(l): for el in l: if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)): yield from flatten(el) else: yield el


Esta versión de flatten evita el límite de recursión de Python (y, por lo tanto, funciona con iterables arbitrariamente profundos y anidados). Es un generador que puede manejar cadenas e iterables arbitrarios (incluso los infinitos).

import itertools as IT import collections def flatten(iterable, ltypes=collections.Iterable): remainder = iter(iterable) while True: first = next(remainder) if isinstance(first, ltypes) and not isinstance(first, basestring): remainder = IT.chain(first, remainder) else: yield first

Aquí hay algunos ejemplos que demuestran su uso:

print(list(IT.islice(flatten(IT.repeat(1)),10))) # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] print(list(IT.islice(flatten(IT.chain(IT.repeat(2,3), {10,20,30}, ''foo bar''.split(), IT.repeat(1),)),10))) # [2, 2, 2, 10, 20, 30, ''foo'', ''bar'', 1, 1] print(list(flatten([[1,2,[3,4]]]))) # [1, 2, 3, 4] seq = ([[chr(i),chr(i-32)] for i in xrange(ord(''a''), ord(''z'')+1)] + range(0,9)) print(list(flatten(seq))) # [''a'', ''A'', ''b'', ''B'', ''c'', ''C'', ''d'', ''D'', ''e'', ''E'', ''f'', ''F'', ''g'', ''G'', ''h'', ''H'', # ''i'', ''I'', ''j'', ''J'', ''k'', ''K'', ''l'', ''L'', ''m'', ''M'', ''n'', ''N'', ''o'', ''O'', ''p'', ''P'', # ''q'', ''Q'', ''r'', ''R'', ''s'', ''S'', ''t'', ''T'', ''u'', ''U'', ''v'', ''V'', ''w'', ''W'', ''x'', ''X'', # ''y'', ''Y'', ''z'', ''Z'', 0, 1, 2, 3, 4, 5, 6, 7, 8]

Aunque flatten puede manejar generadores infinitos, no puede manejar anidamientos infinitos:

def infinitely_nested(): while True: yield IT.chain(infinitely_nested(), IT.repeat(1)) print(list(IT.islice(flatten(infinitely_nested()), 10))) # hangs


Fue divertido tratar de crear una función que pudiera aplanar la lista irregular en Python, pero, por supuesto, para eso es Python (para que la programación sea divertida). El siguiente generador funciona bastante bien con algunas advertencias:

def flatten(iterable): try: for item in iterable: yield from flatten(item) except TypeError: yield iterable

Se aplanarán los tipos de datos que querrá dejar solos (como los objetos bytearray , bytes y str ). Además, el código se basa en el hecho de que solicitar un iterador de un no iterable genera un TypeError .

>>> L = [[[1, 2, 3], [4, 5]], 6] >>> def flatten(iterable): try: for item in iterable: yield from flatten(item) except TypeError: yield iterable >>> list(flatten(L)) [1, 2, 3, 4, 5, 6] >>>

Editar:

No estoy de acuerdo con la implementación anterior. El problema es que no debes poder aplanar algo que no sea un iterable. Es confuso y da la impresión equivocada del argumento.

>>> list(flatten(123)) [123] >>>

El siguiente generador es casi el mismo que el primero, pero no tiene el problema de intentar aplanar un objeto no iterable. Falla como uno esperaría cuando se le da un argumento inapropiado.

def flatten(iterable): for item in iterable: try: yield from flatten(item) except TypeError: yield item

La prueba del generador funciona bien con la lista que se proporcionó. Sin embargo, el nuevo código generará un TypeError cuando se le TypeError un objeto no iterable. A continuación se muestran ejemplos del nuevo comportamiento.

>>> L = [[[1, 2, 3], [4, 5]], 6] >>> list(flatten(L)) [1, 2, 3, 4, 5, 6] >>> list(flatten(123)) Traceback (most recent call last): File "<pyshell#32>", line 1, in <module> list(flatten(123)) File "<pyshell#27>", line 2, in flatten for item in iterable: TypeError: ''int'' object is not iterable >>>


Generador mediante recursión y escritura de pato (actualizado para Python 3):

def flatten(L): for item in L: try: yield from flatten(item) except TypeError: yield item list(flatten([[[1, 2, 3], [4, 5]], 6])) >>>[1, 2, 3, 4, 5, 6]


La forma más fácil es usar la biblioteca de morph usando pip install morph .

El código es:

import morph list = [[[1, 2, 3], [4, 5]], 6] flattened_list = morph.flatten(list) # returns [1, 2, 3, 4, 5, 6]


Me sorprende que nadie haya pensado en esto. Maldita recursión no recibo las respuestas recursivas que hicieron las personas avanzadas aquí. De todos modos aquí está mi intento de esto. advertencia es que es muy específico para el caso de uso del OP

import re L = [[[1, 2, 3], [4, 5]], 6] flattened_list = re.sub("[/[/]]", "", str(L)).replace(" ", "").split(",") new_list = list(map(int, flattened_list)) print(new_list)

salida:

[1, 2, 3, 4, 5, 6]


Mi solución:

def flatten(x): if isinstance(x, collections.Iterable): return [a for i in x for a in flatten(i)] else: return [x]

Un poco más conciso, pero más o menos lo mismo.


No estoy seguro de si esto es necesariamente más rápido o más efectivo, pero esto es lo que hago:

def flatten(lst): return eval(''['' + str(lst).replace(''['', '''').replace('']'', '''') + '']'') L = [[[1, 2, 3], [4, 5]], 6] print(flatten(L))

La función de flatten aquí convierte la lista en una cadena, quita todos los corchetes, vuelve a colocar los corchetes en los extremos y los convierte en una lista.

Aunque, si supiera que tendría corchetes en su lista en cadenas, como [[1, 2], "[3, 4] and [5]"] , tendría que hacer otra cosa.


No revisé todas las respuestas ya disponibles aquí, pero aquí hay un resumen que se me ocurrió, tomando prestado de la manera en que Lisp procesa la primera y la lista de descanso.

def flatten(l): return flatten(l[0]) + (flatten(l[1:]) if len(l) > 1 else []) if type(l) is list else [l]

Aquí hay un caso simple y uno no tan simple:

>>> flatten([1,[2,3],4]) [1, 2, 3, 4] >>> flatten([1, [2, 3], 4, [5, [6, {''name'': ''some_name'', ''age'':30}, 7]], [8, 9, [10, [11, [12, [13, {''some'', ''set''}, 14, [15, ''some_string''], 16], 17, 18], 19], 20], 21, 22, [23, 24], 25], 26, 27, 28, 29, 30]) [1, 2, 3, 4, 5, 6, {''age'': 30, ''name'': ''some_name''}, 7, 8, 9, 10, 11, 12, 13, set([''set'', ''some'']), 14, 15, ''some_string'', 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] >>>


No veo nada como esto publicado por aquí y acabo de llegar de una pregunta cerrada sobre el mismo tema, pero ¿por qué no hacer algo como esto (si conoce el tipo de lista que quiere dividir)?

>>> a = [1, 2, 3, 5, 10, [1, 25, 11, [1, 0]]] >>> g = str(a).replace(''['', '''').replace('']'', '''') >>> b = [int(x) for x in g.split('','') if x.strip()]

Necesitaría saber el tipo de elementos, pero creo que esto puede generalizarse y, en términos de velocidad, creo que sería más rápido.


Podría usar deepflatten del paquete de terceros deepflatten :

>>> from iteration_utilities import deepflatten >>> L = [[[1, 2, 3], [4, 5]], 6] >>> list(deepflatten(L)) [1, 2, 3, 4, 5, 6] >>> list(deepflatten(L, types=list)) # only flatten "inner" lists [1, 2, 3, 4, 5, 6]

Es un iterador, por lo que debe iterarlo (por ejemplo, ajustándolo con la list o usándolo en un bucle). Internamente utiliza un enfoque iterativo en lugar de un enfoque recursivo y está escrito como una extensión C para que pueda ser más rápido que los enfoques de python puro:

>>> %timeit list(deepflatten(L)) 12.6 µs ± 298 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) >>> %timeit list(deepflatten(L, types=list)) 8.7 µs ± 139 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) >>> %timeit list(flatten(L)) # Cristian - Python 3.x approach from https://.com/a/2158532/5393381 86.4 µs ± 4.42 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) >>> %timeit list(flatten(L)) # Josh Lee - https://.com/a/2158522/5393381 107 µs ± 2.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) >>> %timeit list(genflat(L, list)) # Alex Martelli - https://.com/a/2159079/5393381 23.1 µs ± 710 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Soy el autor de la librería iteration_utilities .


Prefiero respuestas simples. No hay generadores. No hay límites de recursión o recursión. Sólo iteración:

def flatten(TheList): listIsNested = True while listIsNested: #outer loop keepChecking = False Temp = [] for element in TheList: #inner loop if isinstance(element,list): Temp.extend(element) keepChecking = True else: Temp.append(element) listIsNested = keepChecking #determine if outer loop exits TheList = Temp[:] return TheList

Esto funciona con dos listas: un bucle for interno y un bucle while externo.

El bucle for interno se repite en la lista. Si encuentra un elemento de lista, (1) usa list.extend () para aplanar el nivel de anidamiento de esa parte uno y (2) cambia keepChecking a True. keepchecking se utiliza para controlar el bucle while externo. Si el bucle externo se establece en verdadero, activa el bucle interno para otra pasada.

Esos pases siguen ocurriendo hasta que no se encuentran más listas anidadas. Cuando finalmente se produce un pase donde no se encuentra ninguno, keepChecking nunca se desvía a verdadero, lo que significa que listIsNested permanece falso y el bucle while externo sale.

La lista aplanada se devuelve.

Prueba de funcionamiento

flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]])

[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]


Si te gusta la recursión, esta podría ser una solución de interés para ti:

def f(E): if E==[]: return [] elif type(E) != list: return [E] else: a = f(E[0]) b = f(E[1:]) a.extend(b) return a

De hecho, lo adapté de un código de Esquema de práctica que había escrito hace un tiempo.

¡Disfrutar!


Soy consciente de que ya hay muchas respuestas asombrosas, pero quería agregar una respuesta que use el método de programación funcional para resolver la pregunta. En esta respuesta hago uso de la doble recursión:

def flatten_list(seq): if not seq: return [] elif isinstance(seq[0],list): return (flatten_list(seq[0])+flatten_list(seq[1:])) else: return [seq[0]]+flatten_list(seq[1:]) print(flatten_list([1,2,[3,[4],5],[6,7]]))

salida:

[1, 2, 3, 4, 5, 6, 7]


Soy nuevo en Python y vengo de un fondo claro. Esto es lo que se me ocurrió (verifique los nombres var para lulz):

def flatten(lst): if lst: car,*cdr=lst if isinstance(car,(list,tuple)): if cdr: return flatten(car) + flatten(cdr) return flatten(car) if cdr: return [car] + flatten(cdr) return [car]

Parece funcionar. Prueba:

flatten((1,2,3,(4,5,6,(7,8,(((1,2)))))))

devoluciones:

[1, 2, 3, 4, 5, 6, 7, 8, 1, 2]


También podemos usar la función ''tipo'' de python. Al iterar la lista, verificamos si el elemento es una lista o no. Si no lo hacemos, lo agregamos, de lo contrario lo extendemos. Aquí hay un código de ejemplo:

l=[1,2,[3,4],5,[6,7,8]] x=[] for i in l: if type(i) is list: x.extend(i) else: x.append(i) print x

Salida:

[1, 2, 3, 4, 5, 6, 7, 8]

Para obtener más información sobre append () y extend () visite este sitio web: https://docs.python.org/2/tutorial/datastructures.html


Usando itertools.chain :

import itertools from collections import Iterable def list_flatten(lst): flat_lst = [] for item in itertools.chain(lst): if isinstance(item, Iterable): item = list_flatten(item) flat_lst.extend(item) else: flat_lst.append(item) return flat_lst

O sin encadenar:

def flatten(q, final): if not q: return if isinstance(q, list): if not isinstance(q[0], list): final.append(q[0]) else: flatten(q[0], final) flatten(q[1:], final) else: final.append(q)


Utilicé recursivo para resolver la lista anidada con cualquier profundidad.

def combine_nlist(nlist,init=0,combiner=lambda x,y: x+y): '''''' apply function: combiner to a nested list element by element(treated as flatten list) '''''' current_value=init for each_item in nlist: if isinstance(each_item,list): current_value =combine_nlist(each_item,current_value,combiner) else: current_value = combiner(current_value,each_item) return current_value

Entonces, después de definir la función combine_nlist, es fácil usar esta función para hacer planos. O puedes combinarlo en una función. Me gusta mi solución porque se puede aplicar a cualquier lista anidada.

def flatten_nlist(nlist): return combine_nlist(nlist,[],lambda x,y:x+[y])

resultado

In [379]: flatten_nlist([1,2,3,[4,5],[6],[[[7],8],9],10]) Out[379]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]


Versión del generador de la solución no recursiva de @ unutbu, tal como lo solicitó @Andrew en un comentario:

def genflat(l, ltypes=collections.Sequence): l = list(l) i = 0 while i < len(l): while isinstance(l[i], ltypes): if not l[i]: l.pop(i) i -= 1 break else: l[i:i + 1] = l[i] yield l[i] i += 1

Versión ligeramente simplificada de este generador:

def genflat(l, ltypes=collections.Sequence): l = list(l) while l: while l and isinstance(l[0], ltypes): l[0:1] = l[0] if l: yield l.pop(0)


totalmente intrincado, pero creo que funcionaría (dependiendo de tu tipo de datos)

flat_list = ast.literal_eval("[%s]"%re.sub("[/[/]]","",str(the_list)))


Sin utilizar ninguna biblioteca:

def flat(l): def _flat(l, r): if type(l) is not list: r.append(l) else: for i in l: r = r + flat(i) return r return _flat(l, []) # example test = [[1], [[2]], [3], [[''a'',''b'',''c''] , [[''z'',''x'',''y'']], [''d'',''f'',''g'']], 4] print flat(test) # prints [1, 2, 3, ''a'', ''b'', ''c'', ''z'', ''x'', ''y'', ''d'', ''f'', ''g'', 4]


Tomado descaradamente de mi propia respuesta a otra pregunta .

Esta función

  • No se usa isinstance, porque es malvado y rompe al escribir pato.
  • Utiliza reducerecursivamente. Tiene que haber una respuesta usando reduce.
  • Funciona con listas anidadas arbitrarias cuyos elementos son listas anidadas, o listas de átomos no anidadas o átomos (sujetos a un límite de recursión).
  • No LBYL.
  • Pero no con listas anidadas que contienen cadenas como átomos.

Código abajo:

def flattener(left, right): try: res = reduce(flattener, right, left) except TypeError: left.append(right) res = left return res def flatten(seq): return reduce(flattener, seq, []) >>> nested_list = [0, [1], [[[[2]]]], [3, [], [4, 5]], [6, [7, 8], 9, [[[]], 10, []]], 11, [], [], [12]] >>> flatten(nested_list) [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]


def flatten(xs): res = [] def loop(ys): for i in ys: if isinstance(i, list): loop(i) else: res.append(i) loop(xs) return res