У меня есть три разных метода проверки уникальности записей в списке с теоретически разным масштабированием O (N), O (N log N) и O (N ** 2), тогда как N - это длина список.
Я понимаю, почему эти методы ДОЛЖНЫ масштабироваться как O (N), O (N log N) и O (N ** 2), но я не могу доказать это численно.
Идея заключалась в том, чтобы просто запустить каждый метод несколько раз со случайными записями списка и различной длины. Затем постройте график зависимости времени от длины списка (т.е. N). Я ожидал, что худший случай для каждого метода / N должен НЕКОТОРЫЕ масштабироваться, как теоретический прогноз, но это не так.
Код:
import time
import random
import matplotlib.pyplot as plt
#O(N**2) - each loop is O(N)
def is_unique1(alist):
for i in range(len(alist)):
for j in range(i+1,len(alist)):
if alist[i] == alist[j]:
return False
return True
#O(N log N) - as sort() is O(N log N)
def is_unique2(alist):
copy = list(alist)
copy.sort()
for i in range(len(alist)-1):
if copy[i] == copy[i+1]:
return False
return True
#O(N) - as set is O(N)
def is_unique3(alist):
aset = set(alist)
return len(aset) == len(alist)
times = []
lengths = []
scale = 1.5
for i in range(1,10):
print('range:',10**i,'to',10**(i+1),'values calc:',int(10**(i/scale)))
for j in range(1,10):
for i in range(1,int(10**(j/scale))):
random.seed(42)
a = str(random.randint(10**j,10**(j+1)))
start = time.time()
is_unique3(a)
end = time.time()
times.append(end-start)
lengths.append(len(a))
print(min(times),max(times))
plt.scatter(lengths,times,s=5)
plt.ylabel('process time (s)')
plt.xlabel('N (length of list)')
plt.title('is_unique3')
plt.grid()
plt.ylim(0.9*min(times),1.1*max(times))
#plt.yscale('log')
plt.show()
результаты:
К сожалению, могу Я вообще не вижу соответствия между теоретическим ожиданием и числовой оценкой.
Неужели иллюзорно думать, что можно достичь этого? Я так поступаю неправильно? Должен ли я проверять КАЖДУЮ возможную запись в списке, чтобы получить правильное масштабирование?
Я озадачен и был бы признателен за любую подсказку ...
###### EDIT
Спасибо за комментарии ! Я изменил способ сбора времени для каждого процесса и решил брать в среднем на (сейчас) 100 запусков на длину списка. Я попытался взять максимальное время на 100 запусков, но результаты все равно выглядели случайными. Адаптированный фрагмент кода:
import time
import random
import numpy as np
import matplotlib.pyplot as plt
#O(N**2) - each loop is O(N)
def is_unique1(alist):
for i in range(len(alist)):
for j in range(i+1,len(alist)):
if alist[i] == alist[j]:
return False
return True
#O(N log N) - as sort() is O(N log N)
def is_unique2(alist):
copy = list(alist)
copy.sort()
for i in range(len(alist)-1):
if copy[i] == copy[i+1]:
return False
return True
#O(N) - as set is O(N)
def is_unique3(alist):
aset = set(alist)
return len(aset) == len(alist)
times = []
lengths = []
times_mean = []
#times_max = []
for j in range(500,10000,1000):
lengths.append(j)
for i in range(1,100):
a = []
for i in range(1,j):
a.append(random.randint(0,9))
start = time.perf_counter()
is_unique2(a)
end = time.perf_counter()
times.append(end-start)
times_mean.append(np.mean(times))
#times_max.append(np.max(times))
#print(min(times),max(times))
#print(len(lengths),len(times_mean))
plt.scatter(lengths,times_mean,s=5, label='mean')
#plt.scatter(lengths,times_max,s=5, label='max')
plt.legend(loc='upper left')
plt.ylabel('process time (s)')
plt.xlabel('N (length of list)')
plt.title('is_unique2')
plt.grid()
plt.ylim(0.9*min(times_mean),1.1*max(times_mean))
#plt.yscale('log')
plt.show()
и результаты:
Хотя методы 2 и 3 выглядят так, как будто они будут масштабироваться как O (N) или O (N log N) в некоторой степени - надеюсь, не случайно - метод 1 по-прежнему выглядит rubbi sh и даже близко не к О (N ** 2). На самом деле я ожидал, что этот метод, как двойной l oop, будет худшим на милю.
Мне все еще не хватает чего-то более общего?