6

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

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]

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

1
  • 2
    Большие временные затраты на длинных списках. 7 июл 2021 в 23:40

1 ответ 1

9

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

К примеру, 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 с примером

3
  • Так объясните этот факт, а то как-то непонятно получается :) 7 июл 2021 в 23:55
  • @Владислав Харламов, там же куча объектов будет создаваться. На каждой итерации будут складываться два списка, создавая новый. 7 июл 2021 в 23:58
  • @ВладиславХарламов К примеру, sum([[1, 2], [3, 4], ...], []) у нас раскладывается в ряд [] + [1, 2] + [3, 4] + .... На каждом "суммировании" создается новый список, стоящий O(n) и так n-раз. В итоге имеем сложность O(n^2). В случае же модификации списка. Мы имеем сложность, насколько понимаю, O(n). 8 июл 2021 в 0:18

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.