При попытке ответить на такой вопрос вам действительно нужно указать ограничения кода, который вы предлагаете в качестве решения. Если бы речь шла только о производительности, я бы не возражал, но большинство кодов, предложенных в качестве решения (включая принятый ответ), не могут сгладить ни один список, глубина которого превышает 1000.
Когда я говорю большинство кодов , я имею в виду все коды, которые используют любую форму рекурсии (или вызывают стандартную библиотечную функцию, которая является рекурсивной). Все эти коды не выполняются, потому что для каждого сделанного рекурсивного вызова стек (вызова) увеличивается на одну единицу, а стек вызовов (по умолчанию) python имеет размер 1000.
Если вы не слишком знакомы со стеком вызовов, возможно, вам поможет следующее (в противном случае вы можете просто прокрутить до Реализация ).
Размер стека вызовов и рекурсивное программирование (аналогия подземелий)
Найти клад и выйти
Представьте, что вы входите в огромное подземелье с пронумерованными комнатами в поисках сокровищ. Вы не знаете место, но у вас есть указания о том, как найти сокровище. Каждое указание является загадкой (сложность варьируется, но вы не можете предсказать, насколько сложными они будут). Вы решаете немного подумать о стратегии экономии времени, вы делаете два замечания:
- Трудно (долго) найти сокровище, так как вам придется разгадывать (потенциально сложные) загадки, чтобы добраться туда.
- Как только сокровище найдено, возвращение ко входу может быть легким, вам просто нужно использовать тот же путь в другом направлении (хотя это требует немного памяти, чтобы вспомнить ваш путь).
При входе в подземелье вы замечаете небольшой блокнот здесь. Вы решаете использовать его, чтобы записать каждую комнату, в которую вы выходите после решения загадки (при входе в новую комнату), таким образом вы сможете вернуться обратно к входу. Это гениальная идея, вы даже не потратите ни цента на реализацию своей стратегии.
Вы входите в темницу, с большим успехом решая первые 1001 загадку, но тут появляется то, что вы не планировали, у вас нет места в заимствованной вами записной книжке. Вы решаете отказаться от вашего квеста, так как вы предпочитаете не иметь сокровища, чем быть потерянным навсегда в подземелье (это действительно выглядит умно).
Выполнение рекурсивной программы
По сути, это то же самое, что найти клад. Подземелье - это память компьютера , теперь ваша цель - не найти клад, а вычислить некоторую функцию (найти f (x) для заданного х ). Признаки просто подпрограммы, которые помогут вам решить f (x) . Ваша стратегия аналогична стратегии стек вызовов , ноутбук - это стек, комнаты - адреса возврата функций:
x = ["over here", "am", "I"]
y = sorted(x) # You're about to enter a room named `sorted`, note down the current room address here so you can return back: 0x4004f4 (that room address looks weird)
# Seems like you went back from your quest using the return address 0x4004f4
# Let's see what you've collected
print(' '.join(y))
Проблема, с которой вы столкнулись в подземелье, будет такой же: стек вызовов имеет конечный размер (здесь 1000), и поэтому, если вы введете слишком много функций без возврата назад, вы заполните стек вызовов и получите ошибка, которая выглядит как «Дорогой искатель приключений, мне очень жаль, но ваш ноутбук заполнен» : RecursionError: maximum recursion depth exceeded. Обратите внимание, что вам не нужна рекурсия для заполнения стека вызовов, но очень маловероятно, чтобы нерекурсивная программа вызывала 1000 функций без какого-либо возврата. Также важно понимать, что после того, как вы вернулись из функции, стек вызовов освобождается от используемого адреса (следовательно, имя «стек», адрес возврата вставляется перед входом в функцию и извлекается при возврате). В особом случае простой рекурсии (функция f, которая вызывает себя один раз, снова и снова), вы будете вводить f снова и снова, пока вычисление не будет завершено (пока не найден клад), и вернетесь из f пока вы не вернетесь к тому месту, где вы вначале позвонили f. Стек вызовов никогда не будет освобожден ни от чего до конца, где он будет освобожден от всех адресов возврата один за другим.
Как избежать этой проблемы?
Это на самом деле довольно просто: «не используйте рекурсию, если вы не знаете, как глубоко она может зайти». Это не всегда так, поскольку в некоторых случаях рекурсия Tail Call может быть оптимизирована (TCO) . Но в python это не так, и даже «хорошо написанная» рекурсивная функция не оптимизирует использование стека. Есть интересный пост от Гвидо по этому вопросу: Устранение хвостовой рекурсии .
Существует методика, которую вы можете использовать, чтобы сделать любую рекурсивную функцию итеративной, эту методику мы могли бы назвать , чтобы принести свой блокнот . Например, в нашем конкретном случае мы просто изучаем список, вход в комнату эквивалентен вводу подсписка, вопрос, который вы должны задать себе: как мне вернуться из списка в его родительский список? Ответ не так сложен, повторяйте следующее до тех пор, пока stack не станет пустым:
- нажмите текущий список
address и index в stack при вводе нового подсписка (обратите внимание, что адрес списка + индекс также является адресом, поэтому мы просто используем точно такой же метод, который используется стеком вызовов );
- каждый раз, когда предмет найден,
yield его (или добавить их в список);
- как только список полностью изучен, вернитесь к родительскому списку, используя
stack return address (и index) .
Также обратите внимание, что это эквивалентно DFS в дереве, где некоторые узлы являются подсписками A = [1, 2], а некоторые являются простыми элементами: 0, 1, 2, 3, 4 (для L = [0, [1,2], 3, 4]). Дерево выглядит так:
L
|
-------------------
| | | |
0 --A-- 3 4
| |
1 2
Предварительный порядок обхода DFS: L, 0, A, 1, 2, 3, 4. Помните, что для реализации итеративной DFS вам также «нужен» стек. Реализация, которую я предложил ранее, приводит к следующим состояниям (для stack и flat_list):
init.: stack=[(L, 0)]
**0**: stack=[(L, 0)], flat_list=[0]
**A**: stack=[(L, 1), (A, 0)], flat_list=[0]
**1**: stack=[(L, 1), (A, 0)], flat_list=[0, 1]
**2**: stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2]
**3**: stack=[(L, 2)], flat_list=[0, 1, 2, 3]
**3**: stack=[(L, 3)], flat_list=[0, 1, 2, 3, 4]
return: stack=[], flat_list=[0, 1, 2, 3, 4]
В этом примере максимальный размер стека равен 2, поскольку входной список (и, следовательно, дерево) имеют глубину 2.
Осуществление
Для реализации в python вы можете немного упростить использование итераторов вместо простых списков. Ссылки на (под) итераторы будут использоваться для хранения возвращаемых адресов подсписков (вместо того, чтобы иметь и адрес списка, и индекс). Это не большая разница, но я чувствую, что это более читабельно (а также немного быстрее):
def flatten(iterable):
return list(items_from(iterable))
def items_from(iterable):
cursor_stack = [iter(iterable)]
while cursor_stack:
sub_iterable = cursor_stack[-1]
try:
item = next(sub_iterable)
except StopIteration: # post-order
cursor_stack.pop()
continue
if is_list_like(item): # pre-order
cursor_stack.append(iter(item))
elif item is not None:
yield item # in-order
def is_list_like(item):
return isinstance(item, list)
Также обратите внимание, что в is_list_like у меня есть isinstance(item, list), который можно изменить для обработки большего количества типов ввода, здесь я просто хотел иметь простейшую версию, где (итерируемая) - это просто список. Но вы также можете сделать это:
def is_list_like(item):
try:
iter(item)
return not isinstance(item, str) # strings are not lists (hmm...)
except TypeError:
return False
Это рассматривает строки как "простые элементы", и поэтому flatten_iter([["test", "a"], "b]) вернет ["test", "a", "b"], а не ["t", "e", "s", "t", "a", "b"]. Обратите внимание, что в этом случае iter(item) вызывается дважды для каждого элемента, давайте представим, что это упражнение для читателя, чтобы сделать это чище.
Тестирование и замечания по другим реализациям
В конце помните, что вы не можете напечатать бесконечно вложенный список L, используя print(L), потому что внутри он будет использовать рекурсивные вызовы __repr__ (RecursionError: maximum recursion depth exceeded while getting the repr of an object). По той же причине решения для flatten, включающие str, завершатся с тем же сообщением об ошибке.
Если вам нужно протестировать ваше решение, вы можете использовать эту функцию для генерации простого вложенного списка:
def build_deep_list(depth):
"""Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$
with $depth > 1$ and $l_0 = [0]$.
"""
sub_list = [0]
for d in range(1, depth):
sub_list = [d, sub_list]
return sub_list
Что дает: build_deep_list(5) >>> [4, [3, [2, [1, [0]]]]].