文章说明
文章作者:鴻塵
参考资料:
1.引言
闲来无事逛Stack Overflow,发现了一个挺有意思的问题:How to make a flat list out of a list of lists?。
1 | # 怎样快速优雅地将src转换成dst? |
乍一看,对于所给的二维数组,for
循环是最容易想到的思路,但是有没有some cool “one-liner”的办法呢?顺着这个问题往下看,还挺有意思。
说明:此处仅讨论各方法的正确性,至于性能和效率可自行测试。
2.解决方案
2.1.方法一:functools.reduce
该问题的提出者Emma提供了一个思路,利用标准库函数reduce
:1
2
3
4from 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
8src1 = [[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 Duminil和Davos。尽管John Mee的写法与for
循环相同,但顺序杂乱不易理解(直观仅限于leaf
、tree
和forest
),Davos更推荐使用leaf for leaf in tree for tree in forest
这种「递进式写法」。
2.3.方法三:itertools.chain
itertools.chain
先将二维数组解包为一维然后连接为迭代器,再转化为列表;itertools.chain.from_iterable
则无需先解包:1
2
3
4
5import 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
2src = [[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
24src = [[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
模块中提供了很多方法,例如concat
、add
等,需要配合functools.reduce
一起使用:1
2
3
4
5
6from 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
6def 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
13from typing import Iterable
def flatten(items):
for x in items:
if isinstance(x, Iterable) and not isinstance(x, (str, bytes)):
yield from flatten(x)
# *注:上句可展开为
# for sub_x in flatten(x):
# yield sub_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"])) # 复杂情况