optimize - ¿Cuál es la forma más rápida de aplanar listas anidadas arbitrariamente en Python?

scipy optimize bisect

Question

Posible duplicado:
Aplanando una lista superficial en Python
Aplanar (una lista irregular) de listas en Python

EDITAR: La pregunta no es cómo hacerlo - esto se ha discutido en otras questions - la pregunta es, ¿cuál es el método más rápido ?

He encontrado soluciones antes, pero me pregunto cuál es la solución más rápida para aplanar listas que contienen otras listas de longitud arbitraria.

Por ejemplo:

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

Se convertiría:

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

Puede haber infinitos niveles Algunos de los objetos de la lista pueden ser cadenas, que no deben aplanarse en sus caracteres secuenciales en la lista de salida.

Answer 1

Aquí hay un enfoque recursivo que es amigable con las cuerdas:

nests = [1, 2, [3, 4, [5],[''hi'']], [6, [[[7, ''hello'']]]]]

def flatten(container):
    for i in container:
        if isinstance(i, (list,tuple)):
            for j in flatten(i):
                yield j
        else:
            yield i

print list(flatten(nests))

devoluciones:

[1, 2, 3, 4, 5, ''hi'', 6, 7, ''hello'']

Tenga en cuenta que esto no garantiza la velocidad o el uso general, pero ilustra una solución recursiva que, con suerte, será útil.

Answer 2

Esta función debería poder aplanar rápidamente los contenedores anidados e iterables sin usar ninguna recursión:

import collections

def flatten(iterable):
    iterator = iter(iterable)
    array, stack = collections.deque(), collections.deque()
    while True:
        try:
            value = next(iterator)
        except StopIteration:
            if not stack:
                return tuple(array)
            iterator = stack.pop()
        else:
            if not isinstance(value, str) /
               and isinstance(value, collections.Iterable):
                stack.append(iterator)
                iterator = iter(value)
            else:
                array.append(value)

Después de unos cinco años, mi opinión sobre el tema ha cambiado, y esto puede ser aún mejor de usar:

def main():
    data = [1, 2, [3, 4, [5], []], [6]]
    print(list(flatten(data)))


def flatten(iterable):
    iterator, sentinel, stack = iter(iterable), object(), []
    while True:
        value = next(iterator, sentinel)
        if value is sentinel:
            if not stack:
                break
            iterator = stack.pop()
        elif isinstance(value, str):
            yield value
        else:
            try:
                new_iterator = iter(value)
            except TypeError:
                yield value
            else:
                stack.append(iterator)
                iterator = new_iterator


if __name__ == ''__main__'':
    main()

Answer 3

No tiene que ser recursivo. De hecho, una solución iterativa es a menudo más rápida debido a la sobrecarga involucrada en las llamadas a funciones. Aquí hay una versión iterativa que escribí hace un tiempo:

def flatten(items, seqtypes=(list, tuple)):
    for i, x in enumerate(items):
        while i < len(items) and isinstance(items[i], seqtypes):
            items[i:i+1] = items[i]
    return items

No he probado el rendimiento de esta implementación específica, pero probablemente no sea tan bueno debido a todas las asignaciones de sectores, lo que podría terminar moviendo mucha memoria. Aún así, no asuma que tiene que ser recursivo, o que es más simple escribirlo de esa manera.

Esta implementación tiene la ventaja de aplanar la lista "en su lugar" en lugar de devolver una copia, como invariablemente hacen las soluciones recursivas. Esto podría ser útil cuando la memoria es escasa. Si quiere una copia aplanada, simplemente pase una copia superficial de la lista que desea aplanar:

flatten(mylist)                # flattens existing list
newlist = flatten(mylist[:])   # makes a flattened copy

Además, este algoritmo no está limitado por el límite de recursión de Python porque no es recursivo. Sin embargo, estoy seguro de que esto nunca entrará en juego.