Проверяю алгоритмическую сложность добавления в список
В этом посте хотел бы проверить разницу в алгоритмической сложности между добавлением элемента в конец списка и добавлением в начало. Для этого буду использовать встроенный модуль 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()