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

44

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]

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

Много лет назад у меня был это точная проблема и закончил тестировать несколько подходов. Francis Avila
Этот ответ из ранее заданный вопрос должен делать то, что вы хотите. (Голосование закрыть как дубликат). GreenMatt
@ GreenMatt, это только дубликат, есвопро то же самое, а не ответ. Понятно, что другой вопрос касается одного уровня вложенности, а более простые решения более уместны. Mark Ransom
@ Mark Ransom: Я думал, что видел это раньше, и это было то, что я нашел, когда искал. Думаю, я недостаточно внимательно прочитал вопрос. GreenMatt
Пожалуйста, прекратите удаление сгенерированного системой баннера «Возможный дубликат». Вторая ссылка содержит ответ на ваш вопрос. vaultah

Ваш Ответ

3   ответа
51

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

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

Это просто прекрасное приложение доходности. Отлично сработано .. fabee
В Python 3.3+ вы можете использоватьyield from flatten(i) вместо тогоfor j in flatten(i): yield j jfs
ты тоже можешь сделатьif isinstance(i, (list, tuple)): вместо. но отличное решение. acushner
А если это набор? Я использовалif hasattr(i, '__iter__'): Tgsmith61591
ипы @String вызывают бесконечную рекурсию сhastattr(i, '__iter__'). Я отфильтровал этиif hasattr(i, '__iter__') and not isinstance(i, str): random8
18

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

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

@ Отметьте этот код однократной записи :). Сделайте заметку, чтобы предупредить будущих редакторов и двигаться дальше по жизни. Triptych
@ Триптих, я не совсем понимаю твой комментарий. Mark Ransom
enumerate() очень прост и задокументирован как ленивый (т.е. возвращает итератор, который выдает последовательные значения индекса). Поведениеiter() в списке (с использованием возрастающего индекса с__getitem__() и сравнивая его сlen() на каждой итерации, которая работает даже при изменении длины) также задокументирована. Так что, хотя это выглядит как хак, на самом деле довольно безопасно, за исключением значительных изменений в языке. kindall
range вместо перечисления также поможет. NarayaN
Я удивлен, что у меня нет больше голосов. Я приписываю это тому факту, что вы должны внимательно прочитать, чтобы понять, что он делает. Mad Physicist
8

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

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

Похожие вопросы