Каков самый быстрый способ сгладить произвольно вложенные списки в Python?

Ответ 1

Здесь рекурсивный подход, дружественный к строкам:

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

возвращает:

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

Обратите внимание: это не гарантирует каких-либо ограничений скорости или накладных расходов, но иллюстрирует рекурсивное решение, которое, надеюсь, будет полезно.

Ответ 2

Это не должно быть рекурсивным. Фактически, итеративное решение часто быстрее из-за накладных расходов, связанных с вызовами функций. Вот итеративная версия, которую я написал некоторое время назад:

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

Не тестировали производительность этой конкретной реализации, но это, вероятно, не так велико, потому что все назначения срезов, которые могут в конечном итоге перемещать много памяти. Тем не менее, не предполагайте, что он должен быть рекурсивным, или что его проще записать таким образом.

Эта реализация имеет то преимущество, что сглаживает список "на месте", а не возвращает копию, поскольку рекурсивные решения неизменно делают. Это может быть полезно, когда память плотная. Если вы хотите сплюснутую копию, просто перейдите в мелкую копию списка, который вы хотите сгладить:

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

Кроме того, этот алгоритм не ограничивается пределом рекурсии Python, поскольку он не рекурсивный. Я уверен, что это практически никогда не вступит в игру.

Ответ 3

Эта функция должна иметь возможность быстро сглаживать вложенные, итерируемые контейнеры без какой-либо рекурсии:

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)

Примерно через пять лет мое мнение по этому вопросу изменилось, и это может быть даже лучше использовать:

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