Python中多个列表的串联

Question

假设我有这样一个函数：

def getNeighbors(vertex)

给定一个顶点，返回其相邻的顶点列表。现在我想创建一个包含所有相邻顶点的相邻顶点的列表。我可以这样做：

listOfNeighborsNeighbors = []
for neighborVertex in getNeighbors(vertex):
    listOfNeighborsNeighbors.append(getNeighbors(neighborsVertex))

有没有更Pythonic的方法去做这件事？

- Björn Pollex

---

我认为这个重复的问题和这个问题都选择了错误的答案。在这里查看更Pythonic/高效的答案。 - Mateen Ulhaq

Answer 1

像往常一样，itertools模块中包含了一个解决方案：

>>> l1=[1, 2, 3]

>>> l2=[4, 5, 6]

>>> l3=[7, 8, 9]

>>> import itertools

>>> list(itertools.chain(l1, l2, l3))
[1, 2, 3, 4, 5, 6, 7, 8, 9]

- Jochen

---

因此，问题的解决方案是 list(itertools.chain.from_iterable(getNeighbors(n) for n in getNeighbors(vertex)))。 - OrangeDog

如果 ls = [l1,l2,l3]，则使用 list(itertools.chain(*ls))。 - Joel Sjögren

Answer 2

[x for n in getNeighbors(vertex) for x in getNeighbors(n)]

或者

sum(getNeighbors(n) for n in getNeighbors(vertex), [])

- Ignacio Vazquez-Abrams

---

+1 我本来想建议使用列表推导式。在我看来，这是最符合 Python 风格的方式。 - Evan Plaice

然而，查看emu回答下面的评论时，请注意时间比较：无论是"itertools.chain"还是"reduce(iadd"都比嵌套列表推导式快两倍以上，而且比sum()快得多，后者随着处理元素数量的增加而快速降级。 - ToolmakerSteve

真高兴我找到了这个。尝试过很多次，从未使用过这样的第二个参数[]来对列表求和。 - Guillaume Chevalier

第二个解决方案看起来非常酷，而且在实践中也有效。但是由于它对于大的N值并不适用，所以我花费了数小时进行分析和调试！请注意在第二个解决方案中有二次时间复杂度的问题。 - Maxim Imakaev

Answer 3

可以使用 + 和 sum() 来合并列表：

>>> c = [[1, 2], [3, 4]]
>>> sum(c, [])
[1, 2, 3, 4]

- Sjoerd

---

谢谢 - 我就知道一定有用sum函数的方法！顺便说一句，我不确定这个方法是否适用于超过2个子列表或长度可变的列表；因此，更清晰的示例可能是：c = [[1, 2], [3, 4, 5], [6, 7]] => [1, 2, 3, 4, 5, 6, 7]。 - ToolmakerSteve

但请查看我在emu的回答下面作为注释的时间。对于100个列表中的100个项目，请勿使用SUM - 非常慢！ - ToolmakerSteve

为什么 sum 函数需要第二个参数？我认为 sum([[1, 2], [3, 4]]) 很明显就是要计算 [1, 2] + [3, 4] 的和。 - KeithWM

@KeithWM 因为 sum([[1, 2], [3, 4]]) 不是指 [1, 2] + [3, 4]，而是 0 + [1, 2] + [3, 4]，这样是行不通的。你需要使用可选的第二个参数来将起始的 0 替换为 []，这样 sum([[1, 2], [3, 4]], []) 就变成了 [] + [1, 2] + [3, 4]。 - Stef

@Stef 非常感谢！这解释了我过去在使用sum时遇到的许多错误。 - KeithWM

Answer 4

从最快到最慢的顺序：

list_of_lists = [[x,1] for x in xrange(1000)]

%timeit list(itertools.chain.from_iterable(list_of_lists))
30 µs ± 320 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit list(itertools.chain(*list_of_lists))
33.4 µs ± 761 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

min(timeit.repeat("ll=[];\nfor l in list_of_lists:\n ll.extend(l)", "list_of_lists=[[x,1] for x in range(1000)]",repeat=3, number=100))/100.0
4.1411130223423245e-05

%timeit [y for z in list_of_lists for y in z]
53.9 µs ± 156 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit sum(list_of_lists, [])
1.5 ms ± 10.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

(Python 3.7.10)

Python2:

list_of_lists = [[x,1] for x in xrange(1000)]

%timeit list(itertools.chain(*list_of_lists))
100000 loops, best of 3: 14.6 µs per loop

%timeit list(itertools.chain.from_iterable(list_of_lists))
10000 loops, best of 3: 60.2 µs per loop

min(timeit.repeat("ll=[];\nfor l in list_of_lists:\n ll.extend(l)", "list_of_lists=[[x,1] for x in xrange(1000)]",repeat=3, number=100))/100.0
9.620904922485351e-05

%timeit [y for z in list_of_lists for y in z]
10000 loops, best of 3: 108 µs per loop

%timeit sum(list_of_lists, [])
100 loops, best of 3: 3.7 ms per loop

- Yariv

---

itertools.chain(list_of_lists) 是错误的（它不会连接任何东西，因为它只有一个参数）。你需要在那里加上一个 *，或者使用 chain.from_iterable。 - interjay

这些时间结果可能已经过时。 在使用Python3.6.6和2018年的硬件进行测试时，我没有发现itertools.chain、itertools.chain.from_iterable和functools.reduce/iadd解决方案之间有任何可重复的速度差异。但是，你的情况可能不同。 不过，iadd解决方案会改变输入。 - Amnon Harel

没有人提到列表的列表是动态的，因此我认为 from_iterable 解决方案不相关。 - Benjamin Atkin

Answer 5

如果速度很重要，最好使用以下代码：

from operator import iadd
reduce(iadd, (getNeighbors(n) for n in getNeighbors(vertex)))

这段代码的重点在于使用list.extend来连接整个列表，而不是像列表推导式一样逐个添加元素，就好像调用list.append一样。这样可以减少一些开销，使前者（根据我的测量）快三倍左右。（通常将iadd运算符写成+=，并且与list.extend执行相同的操作。）

使用列表推导式（Ignacio提供的第一个解决方案）通常仍然是正确的方式，因为其更易于阅读。

但是绝对要避免使用sum(..., [])，因为它的运行时间是平方级别的。这对于包含许多列表（超过一百个左右）的情况非常不实用。

- emu

---

感谢评论有关sum的性能 - 我喜欢这段代码的紧凑性，所以知道不要在大规模上使用它是很好的。 在我看来，Jochen的itertools'chain解决方案比reduce更合适：它更直接/简单地完成了所要求的工作。 - ToolmakerSteve

警告：iadd修改了传入的第一个列表。在示例中无所谓，因为这些列表是函数的结果。但我进行了一个测试，将预先计算的列表列表传递给它。修改了我的原始列表，这样做不好。修复方法：不要使用reduce(iadd, LL)或者reduce(iadd, (L for L in LL))，而是必须将每个返回的L包装在list()中：reduce(iadd, (list(L) for L in LL))。这会强制复制每个L。（这很快，因为大小是已知的。） - ToolmakerSteve

列表推导式的性能下降得更快（2.4 => 9.1）。求和则更糟糕（13.8 => 130.2）！为了更容易比较，将这些数字放在一起：（reduce，chain，comprehension，sum）@ 100x100 =（1.1，1.1，2.6，13.8）; @ 200x200 =（2.6，4.0，9.1，130.2）。 - ToolmakerSteve

测试代码（Python 2.7）：print timeit('all = reduce(operator.iadd, (list(list_) for list_ in LL))', number=1000, setup='n = 100; import operator; L1 = list(range(n)); LL = [[10 * x + v for v in L1] for x in range(n)]') print timeit('all = list(itertools.chain(*LL))', number=1000, setup='n = 100; L1 = list(range(n)); LL = [[10 * x + v for v in L1] for x in range(n)]') print timeit('all = [x for list_ in LL for x in list_]', number=... print timeit('all = sum(LL, [])', number=... 然后将这4个代码，将 n = 100; 替换为 n = 200;。 （然后我将结果时间乘以10） - ToolmakerSteve

@drevicko 因为它在每次添加时都不得不构建一个新列表，这是一种线性时间操作。 - emu

Answer 6

我喜欢使用itertools.chain方法，因为它在线性时间内运行（而sum(...)则在二次时间内运行），但是@Jochen没有展示如何处理动态长度的列表。以下是OP问题的解决方案。

import itertools
list(itertools.chain(*[getNeighbors(n) for n in getNeighbors(vertex)]))

如果您只需要可迭代对象，可以省去list(...)调用。

- renadeen

---

你可以使用chain.from_iterable来代替*[getNeighbors...]，实现方法如下：list(itertools.chain.from_iterable(getNeighbors(n) for n in getNeighbors(vertex)))。该操作不改变原意，且使句子更通俗易懂。 - emu

或者您可以保留解包，但不生成列表，方法是执行 list(itertools.chain(*(getNeighbors(n) for n in getNeighbors(vertex))))。 - Benjamin Atkin

Answer 7

使用.extend()（原地更新）与reduce结合，而不是使用sum()（每次都创建新对象）应该更高效，但我太懒了不想测试 :)

mylist = [[1,2], [3,4], [5,6]] 
reduce(lambda acc_l, sl: acc_l.extend(sl) or acc_l, mylist)

- realmaniek

---

确实更快，但正如Yariv的回答所示，这并不是最快的方法。 - Björn Pollex