Непоследовательная временная сложность теста членства для диапазона Python - PullRequest
Новая
       22

Непоследовательная временная сложность теста членства для диапазона Python

0 голосов
/ 29 июня 2019

Согласно документации, тестирование членства для диапазона Python было постоянным, начиная с версии 3.2. Но когда я попытался измерить его (версия 3.7.3), я наблюдаю линейное время, когда я ищу максимальное или среднее целое число, но постоянное время, когда я рандомизирую целое число. Как это вообще имеет смысл ?? plot of the time complexity for range membership test Код: 

import scipy as sp
from matplotlib import pyplot as plt
import timeit
def in_range(maxlength = 1000, numlengths = 100, numSearch = 1000):
    lengths = sp.linspace(1, maxlength, num = numlengths, dtype = int)
    avgtimes = sp.zeros((3, lengths.size))

    for j, length in zip(range(numlengths), lengths):
        container = range(length)
        # test for last integer in range
        myInt = length-1
        avgtimes[0, j] = timeit.timeit('myInt in container',
                number = numSearch, globals = locals()) / numSearch

        # test for middle-ish integer
        myInt = length//2
        avgtimes[1, j] = timeit.timeit('myInt in container',
                number = numSearch, globals = locals()) / numSearch

        # test for random integer within range
        times = sp.zeros(numSearch)
        for i in range(numSearch):
            myInt = sp.random.randint(0, length)
            times[i] = timeit.timeit('myInt in container', number = 1,
                 globals = locals())
        avgtimes[2, j] = times.mean()

    for j in range(3):
        plt.plot(lengths, avgtimes[j])
    plt.legend(['maximum integer', 'middle-ish integer', 'random integer'])
    plt.xlabel('range size')
    plt.ylabel('average membership test time (seconds)')
...