如何将嵌套列表展开为一维

温馨提示:点击页面下方以展开或折叠目录

文章说明
文章作者:鴻塵
参考资料:

文章链接:https://hwame.top/20210610/flatten-a-nested-list.html

1.引言

闲来无事逛Stack Overflow,发现了一个挺有意思的问题:How to make a flat list out of a list of lists?

1
2
3
# 怎样快速优雅地将src转换成dst?
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
dst = [1, 2, 3, 4, 5, 6, 7, 8, 9]

乍一看,对于所给的二维数组,for循环是最容易想到的思路,但是有没有some cool “one-liner”的办法呢?顺着这个问题往下看,还挺有意思。

说明:此处仅讨论各方法的正确性,至于性能和效率可自行测试。

2.解决方案

2.1.方法一:functools.reduce

该问题的提出者Emma提供了一个思路,利用标准库函数reduce

1
2
3
4
from functools import reduce
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
#reduce(lambda x, y: x.extend(y), src)
reduce(lambda x, y: x + y, src)

这个方法是可行的,但为何不能用x.extend(y)呢?原因是列表的extend方法不返回值(返回None),故在下一轮次的reduce过程中会导致None.extend,从而raise AttributeError: 'NoneType' object has no attribute 'extend'。而列表加法则会返回「extended」列表。

如果非要用extend呢?既然返回None,我们是否可以人为给返回赋值?LBarret给出了一个方案:reduce(lambda x, y : x.extend(y) or x, src, []),或者省略initial参数:reduce(lambda x, y : x.extend(y) or x, src)。其中x.extend(y) or x实现了x + y并返回x,因为bool(x.extend(y)) = False

Greg Hewgill提到,extend()方法会修改列表x,而不是返回一个functools.reduce()所期望的「有用的」值,因此x + y优于x.extend(y)

需要指出的是,这种reduce方法只能解决二维数组,多层嵌套或非列表元素将抛错,例如:

1
2
3
4
5
6
7
8
src1 = [[1], [], [2, 3, 4], 5]           # 含有非列表元素5
src2 = [[1], [], [2, 3], [[4], [5, 6]]] # 多层嵌套
reduce(lambda x, y: x + y, src1)
# TypeError: can only concatenate list (not "int") to list

reduce(lambda x, y: x + y, src2)
# [1, 2, 3, [4], [5, 6]]
# 只能展开一层,若再reduce一次则含非列表元素

2.2.方法二:列表生成式

列表生成式也是很容易想到的办法,因为它本质上就是for循环:

1
2
3
4
5
6
7
8
9
10
11
12
# 列表生成式
dst = [item for sublist in src for item in sublist]

# for循环等价写法
dst = []
for sublist in src:
for item in sublist:
dst.append(item)

# lambda表达式
flatten = lambda t: [item for sublist in t for item in sublist]
dst = flatten(src)

两层for循环写成列表生成式不太直观,借用John Mee的例子会更容易理解和应用:[leaf for tree in forest for leaf in tree]。表达式中「叶 → 树 → 林」的关系很清晰地表现了内外循环的层级。

当然也有不同的观点,例如Eric DuminilDavos。尽管John Mee的写法与for循环相同,但顺序杂乱不易理解(直观仅限于leaftreeforest),Davos更推荐使用leaf for leaf in tree for tree in forest这种「递进式写法」。

2.3.方法三:itertools.chain

itertools.chain先将二维数组解包为一维然后连接为迭代器,再转化为列表;itertools.chain.from_iterable则无需先解包:

1
2
3
4
5
import itertools
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]

dst = list(itertools.chain(*src))
dst = list(itertools.chain.from_iterable(src))

借用该回答下Tim Dierks的评论,*将列表解包为多个参数传递给chain,导致将顶级列表(最外层)扩展为参数,再将这些可迭代对象连接在一起而不会进入更深层级。在这种情况下,列表生成式将比链式用法的可读性更好。

2.4.方法四:sum

这种方法既不直观也不高效,但是很有趣,计算机科学中的monoids定义如下:

Monoids in computer science【来自维基百科】

在计算机科学中,许多抽象数据类型(Abstract Data Types,ADT)都具有monoid结构。在一个常见的模式中,monoid的一系列元素被「折叠)」或「累积」以产生最终值。例如,许多迭代算法需要在每次迭代时更新某种「运行总数」;这种模式可以通过monoid运算优雅地表达。或者,monoid运算的关联性确保可以通过使用前缀和或类似算法来并行化运算,以便有效地利用多个内核或处理器。
给定一系列「$M$类型」且具有「标识元素$\varepsilon$」和「关联操作$\bullet$」的值,折叠操作定义如下:

此外,如果给定其元素的序列化,任何数据结构都可以以类似的方式「折叠」。例如,「折叠」二叉树的结果可能会因遍历方式(前序遍历pre-order与后序遍历post-order)的不同而不同。

代码如下:

1
2
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
dst = sum(src, [])

这只是对第一个参数中传递的iterable元素进行求和,而将第二个元素视为总和的初始值。sum函数的声明为sum(iterable, start=0, /),在上例中如果不传仅限位置参数start,将取默认值0,在这种情况下将抛出TypeError:不能将整数和列表相加。

毫无疑问,这种方法是所有答案中最「简洁」、最「聪明」的,答案评论区争论的焦点之一就是低效,原因是列表连接时产生了大量不必要的复制,时间复杂度高达$O(n^2)$。当然,这并非本文重点,有兴趣可移步Mathieu Larose的文章:How Not to Flatten a List of Lists in Python

同时,该方法仅用于二维嵌套列表,对于更深层级的嵌套,则需寻求其他方法。

2.5.方法五:现有的轮子

有这么句话,Do not reinvent the wheel!,即不要重复造轮子Max Malysh可谓是贯彻了这一理念,很多第三方库甚至是python自带的库或函数,都提供了相应的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
# Django
from django.contrib.admin.utils import flatten
dst = flatten(src)

# Pandas
from pandas.core.common import flatten
dst = list(flatten(src))

# Numpy
from numpy import concatenate
dst = list(concatenate(src))

# Matplotlib
from matplotlib.cbook import flatten
dst = list(flatten(src))

# Unipath
from unipath.path import flatten
dst = list(flatten(src))

# Setuptools
from setuptools.namespaces import flatten
dst = list(flatten(src))

pandas提供的flatten函数不仅能解决多层嵌套,还能连接整数和列表,这或许是终极答案了。

关于造轮子的说法,使用别人造好了的轮子固然可以提高效率,但是自己造轮子难道不是一种更好的学习方式吗?正如Nathan Chappell所言:

All these great libraries reinvented the wheel, why shouldn’t I?

2.6.方法六:operator

operator模块中提供了很多方法,例如concatadd等,需要配合functools.reduce一起使用:

1
2
3
4
5
6
from functools import reduce
import operator
src = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]

reduce(operator.concat, src)
reduce(operator.add, src)

2.6.方法七:map

Daniel Braun给出的map方法,个人认为不是很好(可能这也是vote数比较少的原因吧):

1
2
3
4
5
6
def flatten(src):
dst = []
tmp = list(map(dst.extend, src))
return dst

flatten([[1, 2, 3], [4, 5, 6], [7], [8, 9]])

3.其他问题

上述各种方法都有一定的局限性,最大的问题就是对于数据类型的制约以及嵌套深度的限制,pylang给出了一种适用于数字、字符串、嵌套列表及其复合体的通用方法,该方法参考了Cristian在Flatten an irregular list of lists的回答

1
2
3
4
5
6
7
8
9
10
11
12
from typing import Iterable 
def flatten(items):
for x in items:
if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
for sub_x in flatten(x): #*注
yield sub_x #*注
# *注:上述两句可写为yield from flatten(x)
else:
yield x

list(flatten([[1, 2, 3], [4, 5, 6], [7], [8, 9]])) # 简单情况
list(flatten([[1, [2]], (3, 4, {5, 6}, 7), 8, "9"])) # 复杂情况