主页 / 问题 / 1303092
Accepted
Stanislav Volodarskiy
Asked:2022-07-08 07:02:12 +0800 CST2022-07-08 07:02:12 +0800 CST

为什么在列表列表上调用“sum”是不好的？

  • 772

我有一长串子列表。我想将子列表的所有元素收集到一个列表中。例如：

lst = [[i, i + 1] for i in range(10)]
print(lst)

[[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [ 8, 9], [9, 10]]

flat = sum(lst, [])
print(flat)

[0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10]

代码简短明了。这怎么可能不好？

python

1 个回答

  1. Best Answer

    一般来说，这是一个非常耗时的方法。在小列表上它是难以察觉的，但在大列表上事情变得很糟糕。

    例如，sum([[1, 2], [3, 4], ...], [])我们将它排成一行[] + [1, 2] + [3, 4] + ...。在每个连接上，都会创建一个新列表，O(n)并以此类推 n 次。因此，我们有复杂性O(n^2)。在修改列表的情况下。据我了解，我们有复杂性，O(n). 如果我错了，希望能得到纠正。）

    相比：

    lst_1 = [[i, i + 1] for i in range(100)]
lst_2 = [[i, i + 1] for i in range(1000)]
lst_3 = [[i, i + 1] for i in range(10000)]

def flat(lst: list):
    return [item for row in lst for item in row]

def sum_lst(lst: list):
    return sum(lst, [])

    在 100 个元素的列表中，我们有一个可比较的平均结果，但是，从 1k 个元素开始，我们的平均结果已经相差一个数量级，并且相差 10k - 已经是两个数量级：

    Case: sum_1
---
Function: sum_lst
Total time = 0.00900042 sec
Best loop time = 2.9509e-05 sec
Average loop time = 9.00042e-05 sec
Repeats = 100

Case: flat_1
---
Function: flat
Total time = 0.00363718 sec
Best loop time = 3.2562e-05 sec
Average loop time = 3.63718e-05 sec
Repeats = 100

Case: sum_2
---
Function: sum_lst
Total time = 0.271297 sec
Best loop time = 0.00207202 sec
Average loop time = 0.00271297 sec
Repeats = 100

Case: flat_2
---
Function: flat
Total time = 0.0326995 sec
Best loop time = 0.000306655 sec
Average loop time = 0.000326995 sec
Repeats = 100

Case: sum_3
---
Function: sum_lst
Total time = 36.4801 sec
Best loop time = 0.336264 sec
Average loop time = 0.364801 sec
Repeats = 100

Case: flat_3
---
Function: flat
Total time = 0.384994 sec
Best loop time = 0.00275655 sec
Average loop time = 0.00384994 sec
Repeats = 100

    举例说明

    • 9

相关问题