Проверяю алгоритмическую сложность добавления в список | Блог python программиста
Изображение гика

Блог питониста

Проверяю алгоритмическую сложность добавления в список

30 сентября 2024 г.

В этом посте хотел бы проверить разницу в алгоритмической сложности между добавлением элемента в конец списка и добавлением в начало. Для этого буду использовать встроенный модуль timeit и библиотеку matplotlib.

Если посмотреть на официальную документацию, то мы видим, что операция добавления элемента в конец имеет сложность O(1), а вставки, например, в начало - O(n). Здесь стоит заметить, что не все так просто с добавлением элемента в список, потому что, могут быть ситуации, когда питону потребуется "переаллоцировать" список в памяти или выделить под него больше места, поэтому O(1) будет не всегда. Хотя, глубоко я не копал, не уверен.

Я хотел бы проверить, как растет время увеличение списка в двух случаях: при добавлении элемента в конец и при добавлении элемента в начало списка:

 1 import timeit
 2 
 3 
 4 def append_last(alist: list[int], elem: int) -> None:
 5     alist.append(elem)
 6 
 7 
 8 def insert_first(alist: list[int], elem: int) -> None:
 9     alist.insert(0, elem)
10 
11 
12 def compare_appends() -> None:
13     insert_first_time_log: list[float] = []
14     append_last_time_log: list[float] = []
15     elem = 42
16     factor = 1000
17     init_size = 100
18     last_size = init_size * factor
19     step = 10_000
20     x_axis = []
21     
22     for n in range(init_size, last_size, step):
23         x_axis.append(n)
24         alist = list(range(n))
25         insert_first_time_log.append(
26             timeit.timeit(lambda: insert_first(alist, elem), number=10000)
27         )
28         append_last_time_log.append(
29             timeit.timeit(lambda: append_last(alist, elem), number=10000)
30         )

Затем поставлю либу matplotlib и нарисуем 2 графика:

pip install matplotlib

Затем нарисуем 2 графика, один при добавлении в начало, другой в конец:

1 fig, ax = plt.subplots(figsize=(7, 2.7))             
2 ax.plot(x_axis, insert_first_time_log, label="insert_first_time")
3 ax.plot(x_axis, append_last_time_log, label="append_last_time")
4 ax.set_xlabel('размер списка, шт.')  # Add an x-label to the Axes.
5 ax.set_ylabel('время работы, сек.')  # Add a y-label to the Axes.
6 ax.set_title("Сравнение добавления в список")  # Add a title to the Axes.
7 ax.legend()
8 plt.show()

Получается такой график:

Сравнение операций со списком

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

Код целиком:

 1 import timeit
 2 import matplotlib.pyplot as plt
 3 
 4 
 5 def append_last(alist: list[int], elem: int) -> None:
 6     alist.append(elem)
 7 
 8 
 9 def insert_first(alist: list[int], elem: int) -> None:
10     alist.insert(0, elem)
11 
12 
13 def compare_appends() -> None:
14     insert_first_time_log: list[float] = []
15     append_last_time_log: list[float] = []
16     elem = 42
17     factor = 1000
18     init_size = 100
19     last_size = init_size * factor
20     step = 10_000
21     x_axis = []
22 
23     for n in range(init_size, last_size, step):
24         x_axis.append(n)
25         alist = list(range(n))
26         insert_first_time_log.append(
27             timeit.timeit(lambda: insert_first(alist, elem), number=10000)
28         )
29         append_last_time_log.append(
30             timeit.timeit(lambda: append_last(alist, elem), number=10000)
31         )
32 
33     fig, ax = plt.subplots(figsize=(7, 2.7))
34     ax.plot(x_axis, insert_first_time_log, label="insert_first_time")
35     ax.plot(x_axis, append_last_time_log, label="append_last_time")
36     ax.set_xlabel("размер списка, шт.")  # Add an x-label to the Axes.
37     ax.set_ylabel("время работы, сек.")  # Add a y-label to the Axes.
38     ax.set_title("Сравнение добавления в список")  # Add a title to the Axes.
39     ax.legend()
40     plt.show()
41 
42 
43 if __name__ == "__main__":
44     plt.rcParams.update({"font.size": 22})
45     compare_appends()

Метки

algorithms python
Если вам понравился пост, можете поделиться им в соцсетях: