Згладити нерегулярний список списків

Так, я знаю, що це питання було розглянуто раніше ( тут , тут , тут , тут ), але, наскільки я знаю, всі рішення, за винятком одного, виходять зі списку наступним чином:

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

Якщо бажаний результат

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

Або, може бути, навіть краще, итератор. Єдине рішення, яке я бачив, яке працює для довільної вкладеності, знайдено в цьому питанні :

 def flatten(x): result = [] for el in x: if hasattr(el, "__iter__") and not isinstance(el, basestring): result.extend(flatten(el)) else: result.append(el) return result flatten(L) 

Чи є це найкращою моделлю? Я щось пропустив? Будь-які проблеми?

368
29 янв. заданий telliott99 29 Січня. 2010-01-29 01:15 '10 о 1:15 2010-01-29 1:15
ответ 41 відповідь
  • 1
  • 2

Використання функцій генератора може зробити ваш приклад трохи легшим для читання і, ймовірно, підвищити продуктивність.

Python 2

 def flatten(l): for el in l: if isinstance(el, collections.Iterable) and not isinstance(el, basestring): for sub in flatten(el): yield sub else: yield el 

Я використовував Iterable ABC , доданий в 2.6.

Python 3

В Python 3 basestring більше немає, але ви можете використовувати кортеж str і bytes , щоб отримати там той же ефект.

Оператор yield from повертає елемент з генератора по одному за раз. Цей синтаксис для делегування подгенератору був доданий в 3.3

 def flatten(l): for el in l: if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)): yield from flatten(el) else: yield el 
324
29 янв. відповідь дан Cristian 29 Січня. 2010-01-29 01:35 '10 о 1:35 2010-01-29 1:35

Моє рішення:

 def flatten(x): if isinstance(x, collections.Iterable): return [a for i in x for a in flatten(i)] else: return [x] flatten def flatten(x): if isinstance(x, collections.Iterable): return [a for i in x for a in flatten(i)] else: return [x] 
border=0

Трохи більш коротким, але майже те ж саме.

47
29 янв. відповідь дан Josh Lee 29 Січня. 2010-01-29 01:34 '10 в 1:34 2010-01-29 1:34

Генераторна версія нерекурсівние рішення @unutbu, на прохання @Andrew в коментарі:

 def genflat(l, ltypes=collections.Sequence): l = list(l) i = 0 while i < len(l): while isinstance(l[i], ltypes): if not l[i]: l.pop(i) i -= 1 break else: l[i:i + 1] = l[i] yield l[i] i += 1 

Трохи спрощена версія цього генератора:

 def genflat(l, ltypes=collections.Sequence): l = list(l) while l: while l and isinstance(l[0], ltypes): l[0:1] = l[0] if l: yield l.pop(0) 
33
29 янв. відповідь дан Alex Martelli 29 Січня. 2010-01-29 03:27 '10 в 3:27 2010-01-29 3:27

Генератор з використанням рекурсії і качиної друку (оновлено для Python 3):

 def flatten(L): for item in L: try: yield from flatten(item) except TypeError: yield item list(flatten([[[1, 2, 3], [4, 5]], 6])) >>>[1, 2, 3, 4, 5, 6] 
32
24 янв. відповідь дан dansalmo 24 Січня. 2013-01-24 02:04 '13 в 2:04 2013-01-24 2:04

Ця версія flatten виключає межа рекурсії пітона (і, отже, працює з довільно глибокими вкладеними Ітера). Це генератор, який може обробляти рядки і довільні ітерації (навіть нескінченні).

 import itertools as IT import collections def flatten(iterable, ltypes=collections.Iterable): remainder = iter(iterable) while True: first = next(remainder) if isinstance(first, ltypes) and not isinstance(first, basestring): remainder = IT.chain(first, remainder) else: yield first 

Ось кілька прикладів, які демонструють його використання:

 print(list(IT.islice(flatten(IT.repeat(1)),10))) # [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] print(list(IT.islice(flatten(IT.chain(IT.repeat(2,3), {10,20,30}, 'foo bar'.split(), IT.repeat(1),)),10))) # [2, 2, 2, 10, 20, 30, 'foo', 'bar', 1, 1] print(list(flatten([[1,2,[3,4]]]))) # [1, 2, 3, 4] seq = ([[chr(i),chr(i-32)] for i in xrange(ord('a'), ord('z')+1)] + range(0,9)) print(list(flatten(seq))) # ['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 'g', 'G', 'h', 'H', # 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 'P', # 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X', # 'y', 'Y', 'z', 'Z', 0, 1, 2, 3, 4, 5, 6, 7, 8] 

Хоча flatten може обробляти нескінченні генератори, він не може обробляти нескінченне вкладення:

 def infinitely_nested(): while True: yield IT.chain(infinitely_nested(), IT.repeat(1)) print(list(IT.islice(flatten(infinitely_nested()), 10))) # hangs 
25
29 янв. відповідь дан unutbu 29 Січня. 2010-01-29 01:42 '10 в 1:42 2010-01-29 1:42

Ось моя функціональна версія рекурсивної згладжування, яка обробляє як кортежі, так і списки, і дозволяє вам використовувати будь-яку комбінацію позиційних аргументів. Повертає генератор, який виробляє всю послідовність в порядку, arg arg:

 flatten = lambda *n: (e for a in n for e in (flatten(*a) if isinstance(a, (tuple, list)) else (a,))) 

Використання:

 l1 = ['a', ['b', ('c', 'd')]] l2 = [0, 1, (2, 3), [[4, 5, (6, 7, (8,), [9]), 10]], (11,)] print list(flatten(l1, -2, -1, l2)) ['a', 'b', 'c', 'd', -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 
21
23 марта '11 в 20:42 2011-03-23 20:42 відповідь дан samplebias 23 березня '11 о 20:42 2011-03-23 20:42

Ось ще одна відповідь, який ще більш цікавий ...

 import re def Flatten(TheList): a = str(TheList) b,crap = re.subn(r'[\[,\]]', ' ', a) c = b.split() d = [int(x) for x in c] return(d) 

В основному, він перетворює вкладений список в рядок, використовує регулярний вираз для виділення вкладеного синтаксису, а потім перетворює результат назад в (сплющений) список.

13
14 янв. відповідь дан clay 14 Січня. 2011-01-14 21:31 '11 о 21:31 2011-01-14 21:31
 def flatten(xs): res = [] def loop(ys): for i in ys: if isinstance(i, list): loop(i) else: res.append(i) loop(xs) return res 
9
04 янв. відповідь дан kev 04 Січня. 2011-01-04 07:29 '11 в 7:29 2011-01-04 7:29

Ви можете використовувати deepflatten з стороннього пакета iteration_utilities :

 >>> from iteration_utilities import deepflatten >>> L = [[[1, 2, 3], [4, 5]], 6] >>> list(deepflatten(L)) [1, 2, 3, 4, 5, 6] >>> list(deepflatten(L, types=list)) # only flatten "inner" lists [1, 2, 3, 4, 5, 6] 

Це итератор, тому вам потрібно його ітератіровать (наприклад, шляхом його переповнення list або використання його в циклі). Всередині він використовує ітеративний підхід замість рекурсивного підходу, і він написаний як розширення C, тому він може бути швидше, ніж чисті підходи python:

 >>> %timeit list(deepflatten(L)) 12.6 µs ± 298 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) >>> %timeit list(deepflatten(L, types=list)) 8.7 µs ± 139 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each) >>> %timeit list(flatten(L)) # Cristian - Python 3.x approach from https://stackoverflow.com/a/2158532/5393381 86.4 µs ± 4.42 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) >>> %timeit list(flatten(L)) # Josh Lee - https://stackoverflow.com/a/2158522/5393381 107 µs ± 2.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each) >>> %timeit list(genflat(L, list)) # Alex Martelli - https://stackoverflow.com/a/2159079/5393381 23.1 µs ± 710 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each) 

Я є автором бібліотеки iteration_utilities .

7
29 июля '17 в 17:01 2017-07-29 17:01 відповідь дан MSeifert 29 липня '17 о 17:01 2017-07-29 17:01

Було весело намагатися створити функцію, яка могла б згладити нерегулярний список в Python, але, звичайно, це те, на що Python (для розваги програмування). Наступний генератор працює досить добре з деякими застереженнями:

 def flatten(iterable): try: for item in iterable: yield from flatten(item) except TypeError: yield iterable 

Він буде згладжувати типи даних, які можуть знадобитися в поодинці (наприклад, об'єкти bytearray , bytes і str ). Крім того, код грунтується на тому, що запит ітератора з не-ітерабельного підвищує значення TypeError .

 >>> L = [[[1, 2, 3], [4, 5]], 6] >>> def flatten(iterable): try: for item in iterable: yield from flatten(item) except TypeError: yield iterable >>> list(flatten(L)) [1, 2, 3, 4, 5, 6] >>> 

Edit:

Я не згоден з попередньою реалізацією. Проблема в тому, що ви не повинні згладжувати то, що не є ітеріруемим. Це збиває з пантелику і дає неправильне уявлення про цей аргумент.

 >>> list(flatten(123)) [123] >>> 

Наступний генератор майже такий же, як перший, але не має проблеми зі спробою згладити незнищенний об'єкт. Він зазнає невдачі, як і слід було очікувати, коли йому присвоюється невідповідний аргумент.

 def flatten(iterable): for item in iterable: try: yield from flatten(item) except TypeError: yield item 

Тестування генератора відмінно працює з наданим списком. Однак новий код буде підняти TypeError , коли йому присвоюється незнищенний об'єкт. Нижче наведені приклади нового поведінки.

 >>> L = [[[1, 2, 3], [4, 5]], 6] >>> list(flatten(L)) [1, 2, 3, 4, 5, 6] >>> list(flatten(123)) Traceback (most recent call last): File "<pyshell#32>", line 1, in <module> list(flatten(123)) File "<pyshell#27>", line 2, in flatten for item in iterable: TypeError: 'int' object is not iterable >>> 
6
25 июля '13 в 23:46 2013-07-25 23:46 відповідь дан Noctis Skytower 25 липня '13 о 23:46 2013-07-25 23:46

Тут проста функція, яка вирівнює списки довільної глибини. Немає рекурсії, щоб уникнути.

 from copy import deepcopy def flatten_list(nested_list): """Flatten an arbitrarily nested list, without recursion (to avoid stack overflows). Returns a new list, the original list is unchanged. >> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]])) [1, 2, 3, 4, 5] >> list(flatten_list([[1, 2], 3])) [1, 2, 3] """ nested_list = deepcopy(nested_list) while nested_list: sublist = nested_list.pop(0) if isinstance(sublist, list): nested_list = sublist + nested_list else: yield sublist 
4
10 дек. відповідь дан Wilfred Hughes 10 дек. 2013-12-10 15:56 '13 о 15:56 2013-12-10 15:56

Хоча був обраний елегантний і дуже піфоніческій відповідь, я б представив своє рішення тільки для огляду:

 def flat(l): ret = [] for i in l: if isinstance(i, list) or isinstance(i, tuple): ret.extend(flat(i)) else: ret.append(i) return ret 

Розкажіть, наскільки хороший чи поганий цей код?

4
08 марта '11 в 1:32 2011-03-08 01:32 відповідь дан Xolve 08 березня '11 в 1:32 2011-03-08 1:32

Я віддаю перевагу прості відповіді. Немає генераторів. Обмежень рекурсії або рекурсії. Просто ітерація:

 def flatten(TheList): listIsNested = True while listIsNested: #outer loop keepChecking = False Temp = [] for element in TheList: #inner loop if isinstance(element,list): Temp.extend(element) keepChecking = True else: Temp.append(element) listIsNested = keepChecking #determine if outer loop exits TheList = Temp[:] return TheList 

Це працює з двома списками: внутрішнім циклом і зовнішнім циклом while.

Внутрішній цикл циклу повторюється через список. Якщо він знаходить елемент списку, він (1) використовує list.extend (), щоб згладити той рівень, на якому один рівень вкладеності, і (2) перемикає keepChecking на True. keepchecking використовується для управління зовнішнім циклом while. Якщо зовнішній цикл отримує значення true, він запускає внутрішній цикл для іншого проходу.

Ці проходи тривають до тих пір, поки не будуть знайдені більше вкладених списків. Коли пропуск, нарешті, відбувається там, де жоден з них не знайдений, keepChecking ніколи не спрацює до істини, що означає, що listIsNested залишається помилковим, а зовнішній while цикл виходить.

Потім повертається сплющений список.

тестування

 flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]]) 

[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]

4
13 янв. відповідь дан clay 13 Січня. 2011-01-13 06:19 '11 в 6:19 2011-01-13 6:19

Я здивований, що ніхто не подумав про це. Проклята рекурсія. Я не отримую рекурсивних відповідей, які пропонували тут просунуті люди. У будь-якому випадку, ось моя спроба. обмовка це дуже специфічна для випадку використання OP

 import re L = [[[1, 2, 3], [4, 5]], 6] flattened_list = re.sub("[\[\]]", "", str(L)).replace(" ", "").split(",") new_list = list(map(int, flattened_list)) print(new_list) 

вихід:

 [1, 2, 3, 4, 5, 6] 
2
14 нояб. відповідь дан Zion 14 нояб. 2015-11-14 08:59 '15 в 8:59 2015-11-14 8:59

Я не розглянув всі вже наявні відповіді тут, але ось один лайнер, який я придумав, запозичуючи з lisp спосіб першої та обробки списку відпочинку

 def flatten(l): return flatten(l[0]) + (flatten(l[1:]) if len(l) > 1 else []) if type(l) is list else [l] 

ось один простий і один не дуже простий випадок -

 >>> flatten([1,[2,3],4]) [1, 2, 3, 4] >>> flatten([1, [2, 3], 4, [5, [6, {'name': 'some_name', 'age':30}, 7]], [8, 9, [10, [11, [12, [13, {'some', 'set'}, 14, [15, 'some_string'], 16], 17, 18], 19], 20], 21, 22, [23, 24], 25], 26, 27, 28, 29, 30]) [1, 2, 3, 4, 5, 6, {'age': 30, 'name': 'some_name'}, 7, 8, 9, 10, 11, 12, 13, set(['set', 'some']), 14, 15, 'some_string', 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] >>> 
2
08 апр. відповідь дан Shreyas 08 Квітня. 2016-04-08 16:24 '16 о 16:24 2016-04-08 16:24

Тут реалізація compiler.ast.flatten в 2.7.5:

 def flatten(seq): l = [] for elt in seq: t = type(elt) if t is tuple or t is list: for elt2 in flatten(elt): l.append(elt2) else: l.append(elt) return l 

Є кращі, швидші методи (якщо ви вже тут, ви вже бачили їх)

Також зверніть увагу:

Застарілий з версії 2.6: пакет компілятора був видалений в Python 3.

2
27 авг. відповідь дан pradyunsg 27 Серпня. 2013-08-27 16:05 '13 о 16:05 2013-08-27 16:05

повністю зламаний, але я думаю, що він буде працювати (в залежності від вашого data_type)

 flat_list = ast.literal_eval("[%s]"%re.sub("[\[\]]","",str(the_list))) 
1
28 мая '14 в 20:54 2014-05-28 20:54 відповідь дан Joran Beasley 28 травня '14 о 20:54 2014-05-28 20:54

Використання itertools.chain :

 import itertools from collections import Iterable def list_flatten(lst): flat_lst = [] for item in itertools.chain(lst): if isinstance(item, Iterable): item = list_flatten(item) flat_lst.extend(item) else: flat_lst.append(item) return flat_lst 

Або без прив'язки:

 def flatten(q, final): if not q: return if isinstance(q, list): if not isinstance(q[0], list): final.append(q[0]) else: flatten(q[0], final) flatten(q[1:], final) else: final.append(q) 
1
27 февр. відповідь дан Saksham Varma 27 февр. 2015-02-27 05:38 '15 в 5:38 2015-02-27 5:38

Я використовував рекурсивний для вирішення вкладений список з будь-якою глибиною

 def combine_nlist(nlist,init=0,combiner=lambda x,y: x+y): ''' apply function: combiner to a nested list element by element(treated as flatten list) ''' current_value=init for each_item in nlist: if isinstance(each_item,list): current_value =combine_nlist(each_item,current_value,combiner) else: current_value = combiner(current_value,each_item) return current_value 

Отже, після того, як я визначаю функцію comb_nlist, легко використовувати цю функцію для вирівнювання. Або ви можете об'єднати його в одну функцію. Мені подобається моє рішення, тому що воно може бути застосоване до будь-якого вкладеному списку.

 def flatten_nlist(nlist): return combine_nlist(nlist,[],lambda x,y:x+[y]) 

результат

 In [379]: flatten_nlist([1,2,3,[4,5],[6],[[[7],8],9],10]) Out[379]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 
1
01 окт. відповідь дан freeyoung 01 Жовтня. 2014-10-01 01:02 '14 в 1:02 2014-10-01 1:02

Я не впевнений, що це обов'язково швидше або ефективніше, але це те, що я роблю:

 def flatten(lst): return eval('[' + str(lst).replace('[', '').replace(']', '') + ']') L = [[[1, 2, 3], [4, 5]], 6] print(flatten(L)) 

Функція flatten перетворює список в рядок, витягує квадратні дужки all, прив'язує квадратні дужки до кінців і повертає їх назад до списку.

Хоча, якби ви знали, що у вас будуть квадратні дужки в вашому списку в рядках, наприклад [[1, 2], "[3, 4] and [5]"] , вам потрібно буде зробити щось ще.

1
13 мая '17 в 5:32 2017-05-13 05:32 відповідь дан diligar 13 травня '17 о 5:32 2017-05-13 5:32

Я знаю, що вже є багато чудових відповідей, але я хотів додати відповідь, який використовує метод функціонального програмування для вирішення питання. У цій відповіді я використовую подвійну рекурсию:

 def flatten_list(seq): if not seq: return [] elif isinstance(seq[0],list): return (flatten_list(seq[0])+flatten_list(seq[1:])) else: return [seq[0]]+flatten_list(seq[1:]) print(flatten_list([1,2,[3,[4],5],[6,7]])) 

вихід:

 [1, 2, 3, 4, 5, 6, 7] 
1
03 окт. відповідь дан Leo wahyd 03 Жовтня. 2016-10-03 18:46 '16 о 18:46 2016-10-03 18:46

Найпростіший спосіб - використовувати бібліотеку morph , використовуючи pip install morph .

код:

 import morph list = [[[1, 2, 3], [4, 5]], 6] flattened_list = morph.flatten(list) # returns [1, 2, 3, 4, 5, 6] 
1
15 дек. відповідь дан YPCrumble 15 дек. 2015-12-15 23:03 '15 о 23:03 2015-12-15 23:03

Ось ще один підхід py2, я не впевнений, що його найшвидший або найелегантніший і безпечний ...

 from collections import Iterable from itertools import imap, repeat, chain def flat(seqs, ignore=(int, long, float, basestring)): return repeat(seqs, 1) if any(imap(isinstance, repeat(seqs), ignore)) or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs)) 

Він може ігнорувати будь-який конкретний (або похідний) тип, який вам потрібен, він повертає ітератор, тому ви можете перетворити його в будь-який конкретний контейнер, такий як list, tuple, dict або просто знищити його, щоб зменшити обсяг пам'яті, для краще або гірше , він може обробляти початкові незламні об'єкти, такі як int ...

Зверніть увагу, що велика частина важкого підйому виконується на C, оскільки, наскільки я знаю, це те, як реалізовані itertools, тому, будучи рекурсивним, AFAIK не обмежується глибиною рекурсії python, оскільки виклики функцій відбуваються в C, хоча це не означає, що ви обмежені пам'яттю, особливо в OS X, де розмір його стека має жорсткий ліміт на сьогоднішній день (OS X Mavericks) ...

існує кілька більш швидкий підхід, але менш стерпний метод, використовуйте його, тільки якщо ви можете припустити, що базові елементи введення можуть бути явно визначені інакше, ви отримаєте нескінченну рекурсію, а OS X з її обмеженим стеком розмір, швидко відкине помилку сегментації .. .

 def flat(seqs, ignore={int, long, float, str, unicode}): return repeat(seqs, 1) if type(seqs) in ignore or not isinstance(seqs, Iterable) else chain.from_iterable(imap(flat, seqs)) 

тут ми використовуємо безлічі для перевірки типу, тому для перевірки того, чи слід ігнорувати елемент, необхідно, щоб O (1) vs O (кількість типів) ігнорувалося, хоча, звичайно, будь-яке значення з похідним типом зазначеного ігнорується типи будуть терпіти невдачу, тому використання str , unicode використовує його з обережністю ...

тести:

 import random def test_flat(test_size=2000): def increase_depth(value, depth=1): for func in xrange(depth): value = repeat(value, 1) return value def random_sub_chaining(nested_values): for values in nested_values: yield chain((values,), chain.from_iterable(imap(next, repeat(nested_values, random.randint(1, 10))))) expected_values = zip(xrange(test_size), imap(str, xrange(test_size))) nested_values = random_sub_chaining((increase_depth(value, depth) for depth, value in enumerate(expected_values))) assert not any(imap(cmp, chain.from_iterable(expected_values), flat(chain(((),), nested_values, ((),))))) >>> test_flat() >>> list(flat([[[1, 2, 3], [4, 5]], 6])) [1, 2, 3, 4, 5, 6] >>> $ uname -a Darwin Samys-MacBook-Pro.local 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun 3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64 $ python --version Python 2.7.5 
1
17 авг. відповідь дан Samy Vilar 17 Серпня. 2014-08-17 22:52 '14 о 22:52 2014-08-17 22:52

Python-3

 from collections import Iterable L = [[[1, 2, 3], [4, 5]], 6,[7,[8,9,[10]]]] def flatten(thing): result = [] if isinstance(thing, Iterable): for item in thing: result.extend(flatten(item)) else: result.append(thing) return result flat = flatten(L) print(flat) 
0
27 февр. відповідь дан Fuji Clado 27 февр. 2017-02-27 19:01 '17 о 19:01 2017-02-27 19:01

Без використання бібліотеки:

 def flat(l): def _flat(l, r): if type(l) is not list: r.append(l) else: for i in l: r = r + flat(i) return r return _flat(l, []) # example test = [[1], [[2]], [3], [['a','b','c'] , [['z','x','y']], ['d','f','g']], 4] print flat(test) # prints [1, 2, 3, 'a', 'b', 'c', 'z', 'x', 'y', 'd', 'f', 'g', 4] 
0
07 дек. відповідь дан alfasin 07 дек. 2014-12-07 09:06 '14 в 9:06 2014-12-07 9:06

Немає рекурсії або вкладених циклів. Кілька рядків. Добре відформатований і легко читається:

 def flatten_deep(arr: list): """ Flattens arbitrarily-nested list 'arr' into single-dimensional. """ while arr: if isinstance(arr[0], list): # Checks whether first element is a list arr = arr[0] + arr[1:] # If so, flattens that first element one level else: yield arr.pop(0) # Otherwise yield as part of the flat array flatten_deep(L) 

З мого власного коду на https://github.com/jorgeorpinel/flatten_nested_lists/blob/master/flatten.py

0
22 янв. відповідь дан Jorge Orpinel 22 Січня. 2019-01-22 13:22 '19 о 13:22 2019-01-22 13:22

При спробі відповісти на таке питання вам дійсно потрібно вказати обмеження коду, який ви пропонуєте в якості рішення. Якби мова йшла тільки про виступи, я б не проти занадто багато, але більшість кодів, запропонованих як рішення (включаючи прийнятий відповідь), що не згладжують список, який має глибину більше 1000.

Коли я говорю більшість кодів, я маю на увазі всі коди, які використовують будь-яку форму рекурсії (або називають стандартну бібліотечну функцію, яка є рекурсивної). Всі ці коди зазнають невдачі, тому що для кожного рекурсивного виклику стек (виклику) зростає на одиницю, а стек викликів за замовчуванням (за замовчуванням) python має розмір 1000.

Якщо ви не дуже добре знайомі з стеком викликів, можливо, наступне допоможе (інакше ви можете просто перейти до Реалізації).

Розмір стека викликів і рекурсивне програмування (аналогія підземель)

Пошук скарбів і вихід

Уявіть, що ви входите в величезну підземелля з пронумерованими кімнатами, шукаючи скарб. Ви не знаєте місця, але у вас є деякі вказівки про те, як знайти скарб. Кожне вказівку - загадка (труднощі розрізняються, але ви не можете передбачити, наскільки вони будуть важкими). Ви вирішили трохи подумати про стратегію економії часу, ви робите два спостереження:

  1. Це важко (довго) знайти скарб, як вам доведеться вирішувати (потенційно важко) загадки, щоб дістатися туди.
  2. Як тільки знайдений скарб, повернення до входу може бути легким, вам просто потрібно використовувати той же шлях в іншому напрямку (хоча для цього потрібно небагато пам'яті, щоб згадати ваш шлях).

Коли ви входите в підземеллі, ви помічаєте тут маленький ноутбук. Ви вирішили використовувати його для запису кожної кімнати, яку ви виходите, після рішення загадки (при вході в нову кімнату), таким чином ви зможете повернутися назад до входу. Це геніальна ідея, ви навіть не витратите цент, реалізуючи свою стратегію.

Ви потрапляєте в темницю, з великим успіхом вирішуєте перші 1001 загадки, але тут приходить то, що ви не планували, у вас немає місця в записнику, яку ви запозичили. Ви вирішуєте відмовитися від свого квесту, так як ви вважаєте за краще не мати скарби, ніж бути втраченим назавжди всередині підземелля (це виглядає дійсно розумним).

Виконання рекурсивної програми

В принципі, це те ж саме, що знайти скарб. Підземелля - це комп'ютерна пам'ять, тепер ваша мета - не знайти скарб, а обчислити деяку функцію (знайти f (x) для даного 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 see what you've collected print(' '.join(y)) you can return back 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 see what you've collected print(' '.join(y)) using the return address 0x4004f4 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 see what you've collected print(' '.join(y)) 

Проблема, з якою ви зіткнулися в підземеллі, буде тут же, стек викликів має кінцевий розмір (тут 1000), і тому, якщо ви вводите занадто багато функцій, які не повертаючись назад, ви заповнюєте стек викликів і отримуєте помилку, яка виглядає "Дорогий шукач пригод, мені дуже шкода, але ваш ноутбук сповнений ": RecursionError: maximum recursion depth exceeded . Зверніть увагу, що вам не потрібна рекурсія для заповнення стека викликів, але дуже малоймовірно, що нерекурсівние програма викличе тисяча функцій, які не повертаючись. Важливо також розуміти, що після того, як ви повернулися з функції, стек викликів звільняється від використовуваного адреси (звідси ім'я "стек", адреса повернення вставляються перед входом в функцію і витягуються при поверненні). В частном случае простой рекурсии (функция f которая вызывает себя один раз - снова и снова) вы будете вводить f снова и снова, пока вычисление не закончится (пока сокровище не будет найдено) и не вернется с f до тех пор, пока вы не пойдете назад к месту, где вы назвали f в первую очередь. Стек вызовов никогда не будет освобожден от чего-либо до конца, где он будет освобожден от всех обратных адресов один за другим.

Как избежать этой проблемы?

Это на самом деле довольно просто: "не используйте рекурсию, если вы не знаете, как глубоко она может идти". Это не всегда так, как в некоторых случаях, рекурсия хвостового звонка может быть оптимизирована (TCO) . Но в python это не так, и даже "хорошо написанная" рекурсивная функция не будет оптимизировать использование стека. Есть интересный пост от Гвидо об этом вопросе: " Устранение хвостовой рекурсии" .

Существует методика, позволяющая сделать любую рекурсивную функцию итеративной, эта техника, которую мы могли бы назвать, приносит ваш собственный ноутбук . Например, в нашем конкретном случае мы просто изучаем список, входя в комнату, эквивалентно вводу подсписок, вопрос, который вы должны задать себе, - как я могу вернуться из списка в его родительский список? Ответ не такой сложный, повторите следующее, пока stack будет пустым:

  1. нажимайте текущий address и index в stack при вводе нового подсписок (обратите внимание, что адрес + индекс также является адресом, поэтому мы используем только тот же метод, который используется стеком вызовов);
  2. каждый раз, когда элемент найден, yield его (или добавьте в список);
  3. как только список будет полностью изучен, вернитесь к родительскому списку, используя address возврата stackindex ).

Также обратите внимание, что это эквивалентно 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 вам также понадобится стек. Реализация, которую я предложил, flat_list к flat_list , что следующие состояния (для 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]