Когда я анализирую скорость из своих алгоритмов-разделителей, почему я получаю эти выбросы в заданных c точках?

Question

Я изучаю алгоритмы, сложность и науку о данных. Я написал две функции, которые разбивают список из 1000 чисел на список каждого числа в своем собственном списке.

Например,

[1,2,3,4,5] станет [[1], [2], [3], [4], [5]]

Это не практично, но дело в том, чтобы увидеть, как масштабируются функции. 'divsep' разделяет список с помощью рекурсия и 'ifsep' разделяет список с помощью итерация. Сценарий, который я написал, генерирует списки длины от 1 до 1000 и проверяет количество времени, необходимое для сортировки этих размеров списков с каждой отдельной функцией.

Однако, я получаю последовательные выбросы в указанных c точках данных, особенно в списках размеров 400 и 800, и я не уверен, почему. Код ниже.

import time

def divsep(prime_list,fresh_list = []):
    '''takes an input list of size x and breaks it down into x lists of size 1 
    using recursion'''
    if len(prime_list) == 0:
        return fresh_list
    else:
        new = prime_list.pop()
        list_entry = [new]
        fresh_list.append(list_entry)
        return divsep(prime_list, fresh_list)


def ifsep(list_input):
    '''takes an input list of size x and breaks it down into x lists of size 1 
    using iteration'''
    new_list = []
    for item in list_input:
        ind = [item]
        new_list.append(ind)
    return new_list


with open('divsep.csv', 'w') as f:
    f.write('"Algorithm","Range","Time"\n')
    for number in range(1,1000):
        list1 = [x for x in range(1,number)]
        sum1 = 0
        for numnum in range(100):
            t1 = time.perf_counter()
            divsep(list1)
            t2 = time.perf_counter()
            sum1 += t2-t1
        f.write(f'"divsep","{number}","{sum1/100}"\n')


with open('ifsep.csv', 'w') as f:
    f.write('"Algorithm","Range","Time"\n')
    for number in range(1,1000):
        list1 = [x for x in range(1,number)]
        sum1 = 0
        for number in range(100):
            t3 = time.perf_counter()
            ifsep(list1)
            t4 = time.perf_counter()
            sum1 += t4-t3

        f.write(f'"ifsep","{number}","{sum1/100}"\n')


print('End program')

Я использую этот код в блокноте Jupyter для отображения результатов на линейных графиках.

import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

recursion_separators = pd.io.parsers.read_csv('divsep.csv')
iteration_separators = pd.io.parsers.read_csv('ifsep.csv')


recursive_values = list(recursion_separators[['Time'][0]])
plt.plot(range(1,1000), recursive_values, 'm')
plt.show()

iteration_values = list(iteration_separators[['Time'][0]])
plt.plot(range(1,1000), iteration_values, 'b')
plt.show()

Для обоих графиков ось x - это размер списка, а ось y - время, необходимое для запуска алгоритма. Фиолетовый (верхний график) - это результаты для разделителя рекурсии, а синий (нижний график) отображает результаты для итеративного разделителя.

Я предполагаю, что эти значения должны масштабироваться согласованно, поэтому, когда я первоначально увидел эти выбросы, я подумал, что, возможно, это добавило дополнительное время, потому что мой компьютер работает под управлением другого программного обеспечения, что делает тестирование медленнее, чем должно быть. Чтобы это исправить, я добавил в программу и сделал так, чтобы он 100 раз запускал каждый список размером n, а затем получал среднее значение. Я полагал, что это компенсирует любые выбросы, но я этого не делаю. Кроме того, отметки всегда появляются в одинаковых отметках, особенно 400 и 800 для верхнего графика.

Я не уверен, что это проблема с моим кодом, компьютером или пониманием статистики, поэтому я надеюсь, что кто-то сможет пролить свет на топи c.

Спасибо!

Мои версии: python: 3.7, spyder: 3.3.6, ядро ​​jupyter: 4.5 .0, jupyter-notebook: 6.0.1,