Şu kodu çalıştırıp çıktısını inceleyebilirsiniz, time complexity’nin etkisini listelerin uzunluğu artınca daha iyi anlıyoruz:
from timeit import default_timer as timer
class Sublist():
def __init__(self, l):
self.list = l
self.start = 0
self.finish = len(l)
def upto(self, finish):
self.finish = self.start + finish
return self
def startfrom(self, start):
self.start += start
return self
def __getitem__(self, index: int):
i = self.start + index
if not i < self.finish: # bu kodda gerek yok ama genel olarak böyle bir durumda hata verilmesi lazım
raise IndexError()
return self.list[i]
def __len__(self):
return self.finish - self.start
def ölç(f, n=100000):
"Bir işlemi aldığı ortalama zaman."
t = timer()
f(n)
return (timer() - t) / n
def logn(n):
f = lambda m, k, l, i: (f(m.startfrom(l), k.startfrom(l), (len(m)-l)//2, l + i) if m[l-1] == k[l-1] else f(m.upto(l), k.upto(l), l//2, i)) if len(m) > 1 else i+l
dev_index = lambda l, k: f(Sublist(l), Sublist(k), len(l)//2, 0)
for _ in range(n):
dev_index(list_a, list_b)
def lineer(n):
f = lambda m, k, l, i: (f(m[l:], k[l:], (len(m)-l)//2, l + i) if m[l-1] == k[l-1] else f(m[:l], k[:l], l//2, i)) if len(m) > 1 else i+l
dev_index = lambda l, k: f(l, k, len(l)//2, 0)
for _ in range(n):
dev_index(list_a, list_b)
repeat = 100
import random
list_a = sorted(random.sample(range(1000000), 1000))
list_b = list_a.copy()
list_a.pop(random.randrange(0, len(list_a)))
list_a.append(list_a[-1] + random.randint(1, 100))
a=ölç(lineer, repeat)
print("lineer:", a)
b=ölç(logn, repeat)
print("logn:", b)
list_a = sorted(random.sample(range(1000000), 100000))
list_b = list_a.copy()
list_a.pop(random.randrange(0, len(list_a)))
list_a.append(list_a[-1] + random.randint(1, 100))
c=ölç(lineer, repeat)
print("lineer:", c)
d=ölç(logn, repeat)
print("logn:", d)
print("lineerdeki artış:", c/a)
print("logndeki artış:", d/b)