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

Question

Возможный дубликат:
Сглаживание мелкого списка в Python
Свести (нерегулярный) список списков в Python

РЕДАКТИРОВАТЬ: Вопрос не в том, как это сделать - это обсуждалось в других вопросах - вопрос в том, какой метод самый быстрый?

Я уже нашел решения, но мне интересно, какое самое быстрое решение - сгладить списки, которые содержат другие списки произвольной длины.

Например:

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

Станет:

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

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

Answer 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']

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

Answer 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, потому что он не рекурсивен. Однако я уверен, что это практически никогда не вступит в игру.

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