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

Possible Duplicate:
Flattening a shallow list in Python
Flatten (an irregular) list of lists in Python

EDIT: Вопрос неhow сделать это - это былообсуждается в другихвопросы - вопрос, который являетсяfastest метод?

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

Например:

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

Станет:

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

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

 GreenMatt30 мая 2012 г., 23:15
@ Mark Ransom: Я думал, что видел это раньше, и это было то, что я нашел, когда искал. Думаю, я недостаточно внимательно прочитал вопрос.
 Mark Ransom30 мая 2012 г., 22:52
@ GreenMatt, это только дубликат, есвопро то же самое, а не ответ. Понятно, что другой вопрос касается одного уровня вложенности, а более простые решения более уместны.
 vaultah24 апр. 2016 г., 22:29
Пожалуйста, прекратите удаление сгенерированного системой баннера «Возможный дубликат». Вторая ссылка содержит ответ на ваш вопрос.
 Francis Avila30 мая 2012 г., 22:38
Много лет назад у меня был это точная проблема и закончил тестировать несколько подходов.
 GreenMatt30 мая 2012 г., 22:43
Этот ответ из ранее заданный вопрос должен делать то, что вы хотите. (Голосование закрыть как дубликат).

Ответы на вопрос(3)

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

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

 Mark Ransom30 мая 2012 г., 23:30
@ Триптих, я не совсем понимаю твой комментарий.
 Triptych30 мая 2012 г., 23:20
@ Отметьте этот код однократной записи :). Сделайте заметку, чтобы предупредить будущих редакторов и двигаться дальше по жизни.
 NarayaN17 июл. 2013 г., 06:29
range вместо перечисления также поможет.
 Mad Physicist17 мар. 2016 г., 17:36
Я удивлен, что у меня нет больше голосов. Я приписываю это тому факту, что вы должны внимательно прочитать, чтобы понять, что он делает.
 kindall31 мая 2012 г., 00:45
enumerate() очень прост и задокументирован как ленивый (т.е. возвращает итератор, который выдает последовательные значения индекса). Поведениеiter() в списке (с использованием возрастающего индекса с__getitem__() и сравнивая его сlen() на каждой итерации, которая работает даже при изменении длины) также задокументирована. Так что, хотя это выглядит как хак, на самом деле довольно безопасно, за исключением значительных изменений в языке.
Решение Вопроса

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

returns:

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

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

 fabee13 сент. 2013 г., 17:29
Это просто прекрасное приложение доходности. Отлично сработано ..
 jfs24 февр. 2015 г., 11:38
В Python 3.3+ вы можете использоватьyield from flatten(i) вместо тогоfor j in flatten(i): yield j
 acushner16 мар. 2016 г., 23:39
ты тоже можешь сделатьif isinstance(i, (list, tuple)): вместо. но отличное решение.
 Tgsmith6159126 мая 2016 г., 16:07
А если это набор? Я использовалif hasattr(i, '__iter__'):
 random801 мар. 2017 г., 19:03
ипы @String вызывают бесконечную рекурсию сhastattr(i, '__iter__'). Я отфильтровал этиif hasattr(i, '__iter__') and not isinstance(i, str):

ативные контейнеры без использования рекурсии:

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

Ваш ответ на вопрос