Как работает исходный фрагмент
def flatten(x):
return sum([flatten(y) if isinstance(y, list) else [y] for y in x], [])
- Для каждого элемента y в x создаётся либо одноэлементный список $[y]$ (если y не список), либо результат рекурсивного вызова flatten(y) (если y — список).
- Получив список списков, sum(..., []) последовательно складывает (конкатенирует) эти списки, начиная с пустого списка, давая общий плоский список.
Недостатки по производительности и памяти
- Операция конкатенации списков создаёт новый список и копирует элементы. При последовательном сложении списков получаем квадратичную копию элементов в худшем случае. При n элементов и m «частичных» списков это даёт в худшем случае время порядка $O(N^2)$. Для примера, если складывать списки длины 1 последовательно, суммарная работа ~$1+2+\cdots +N=\frac{N(N+1)}{2}=O(N^2)$.
- Создаются множество промежуточных списков — высокий пиковый расход памяти и лишние копирования.
- Рекурсия может привести к переполнению стека при глубокой вложенности.
- isinstance(y, list) фильтрует только list; кортежи/другие итерируемые объекты, строки и т.п. обрабатываются неунифицированно.
Эффективные варианты
1) Рекурсивный с extend (линейное время и память, но рекурсивная глубина остаётся)
def flatten(x):
res = []
for y in x:
if isinstance(y, list):
res.extend(flatten(y))
else:
res.append(y)
return res
Временная сложность: $O(N)$. Память: $O(N)$ (без множества промежуточных копий).
2) Генератор (ленивая генерация, меньше пиковой памяти; рекурсия остаётся)
def iter_flatten(x):
for y in x:
if isinstance(y, list):
yield from iter_flatten(y)
else:
yield y
# получить список: list(iter_flatten(x))
3) Итеративный стекный вариант (избегает глубокой рекурсии)
def flatten_iter(x):
res = []
stack = list(reversed(x))
while stack:
item = stack.pop()
if isinstance(item, list):
stack.extend(reversed(item))
else:
res.append(item)
return res
Этот вариант даёт порядок обхода тот же, что и рекурсивный, с временной сложностью $O(N)$ и без рекурсивного стека Python.
4) Универсальность типов
Если нужно обрабатывать любые итерируемые, а не строки и байты, проверку можно делать через collections.abc.Iterable и исключать (str, bytes):
from collections.abc import Iterable
def iter_flatten_any(x):
for y in x:
if isinstance(y, Iterable) and not isinstance(y, (str, bytes)):
yield from iter_flatten_any(y)
else:
yield y
Короткое резюме
- Исходный код прост, но неэффективен: время и копирования до $O(N^2)$, много промежуточной памяти и риск переполнения стека.
- Лучше использовать extend/генератор/итеративный стек — они дают линейное время $O(N)$, линейную память $O(N)$ (без лишних промежуточных копий) и при итеративном варианте — отсутствие рекурсивной глубины.