Почему плохо вызывать `sum` на списке списков?

Question

У меня есть длинный список состоящий из подсписков. Я хочу собрать все элементы подсписков в единый список. Например:

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]

Код короткий и понятный. Чем это может быть плохо?

Answer 1

В целом очень затратный способ по времени. На небольших списках незаметно, но на больших списках все становится плохо.

К примеру, 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 элементов имеем сопоставимый средний результат, но, начиная с 1к элементов, уже расходимся на порядок по среднему результату, а на 10к — уже два порядка:

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

gist с примером

БЛОГ НА HUSL

Почему плохо вызывать `sum` на списке списков?

Ответы (1 шт):