Nezávazné bádání nad časovou náročností programu - II
Tímto článkem bych rád navázal na své předchozí nezávazné bádání nad komplexností programů.
V něm jsem se nejříve pokusil odhadnout, jaké funkci by mohla časová závislost programu odpovídat. Následně pak pro tuto funkci spočítat její parametry. No a ty pak můžu použít pro odhad toho, jak by se můj program mohl chovat v produkčním prostředí.
To vše ovšem probíhalo na testovacích datech získaných z hry BENDER – Episode 3, takže se jednalo o dopředu připravená data. Bude mně ale ten postup fungovat, když data nebudou dopředu dobře připravená?
Na to se pokusím najít nějakou odpověď v tomto článku:
Ani teď nemám data vzniklá měřením běhu nějakého reálného programu či algoritmu. Pokusím se o vygenerování náhodných vzorků dat na základě funkcí, které používám pro určení časové náročnosti programu.
Stanovil jsem si sám pro sebe následující omezení vygenerovaných dat:
- nezávislá proměnná X, tedy počet testovacích vzorků dat, bude maximálně 100. To proto, že pokud budu data získávat měřením nějakého programu, pak asi nebudu mít čas a chuť těch vzorků dělat příliš mnoho
- závislá proměnná Y, tedy doba běhu programu pro jeden vzorek dat, bude maximálně 1000 sekund. Omezení opět vychází z představy, že kdybych dobu měřil na běhu programu, asi by se mně nechtělo čekat příliš dlouho
Dále jsem si omězil i počet funkcí, se kterými budu experimentovat.
import os
import numpy as np
import matplotlib.pyplot as plt
%matplotlib inline
Funkce pro popis časové náročnosti
Takto tedy vypadají funkce, se kterými budu dále pracovat:
X = 100
MAX_A, MAX_Y = 10, 1000
SAMPLE_FUNCTIONS = {
'O(1)': (lambda x, a, b: a + b * np.ones(x.shape), MAX_Y / 2),
'O(log n)': (lambda x, a, b: a + b * np.log2(x), MAX_Y / np.log2(X)),
'O(n)': (lambda x, a, b: a + b * x, MAX_Y / X),
'O(n^2)': (lambda x, a, b: a + b * np.power(x, 2, dtype=float), MAX_Y / np.power(X, 2, dtype=float)),
'O(n^4)': (lambda x, a, b: a + b * np.power(x, 4, dtype=float), MAX_Y / np.power(X, 4, dtype=float)),
'O(2^n)': (lambda x, a, b: a + b * np.power(2, x, dtype=float), MAX_Y / np.power(2, X, dtype=float)),
}
x = np.array(range(1, X + 1))
for name, (func, coef) in SAMPLE_FUNCTIONS.items():
a, b = MAX_A, coef
y = func(x, a, b)
plt.plot(x, y, label=name)
plt.legend(bbox_to_anchor=(1.04,1), loc="upper left")
plt.show()
Odhad funkce na základě naměřených dat
Toto je mírně upravené řešení z předchozího článku pro hledání vhodné funkce pro popis časové náročnosti programů:
def complexity_phase(x_values, y_values, samples):
x = np.array(x_values)
y = np.array(y_values)
xx = np.linspace(np.min(x), np.max(x), samples, dtype=int)
yy = np.interp(xx, x, y)
min_y = np.min(yy)
max_y = np.max(yy)
norm_x = np.arange(1, samples + 1)
if max_y > min_y:
norm_y = (yy - min(y)) / (max_y - min_y)
else:
return 'O(1)'
complexity = {
'O(1)': (lambda v: np.ones(v.shape), 2.0),
'O(log n)': (lambda v: np.log2(v), np.log2(samples)),
'O(n)': (lambda v: v, samples),
'O(n^2)': (lambda v: np.power(v, 2), np.power(samples, 2)),
'O(n^4)': (lambda v: np.power(v, 4), np.power(samples, 4)),
'O(2^n)': (lambda v: np.exp2(v), np.exp2(samples)),
}
res = []
for comp, (func, coef) in complexity.items():
z = np.sum(np.power(norm_y - func(norm_x) / coef, 2))
res.append((comp, z))
return min(res, key=lambda a: a[1])[0]
A tímto si pouze vyzkouším, že jsem schopen detekovat neupravená data:
x = np.array(range(1, X + 1))
for name, (func, coef) in SAMPLE_FUNCTIONS.items():
a, b = 10, coef
y = func(x, a, b)
print(f"{name:8} ==> {complexity_phase(x, y, X)}")
Vliv šumu na detekci funkce
Pokud získávám data měřením nějakého existujícího pragramu, pak vždy je moje měření zatížené nějakou chybou. Tuto chybu se pokusím nasimulovat tak, že závisle proměnnou zatížím nějakým náhodným „šumem“. Tím budou náhodně vygenerované chyby s normálním rozdělením.
Tak například takto vypadají průběhy sledovaných funkcí, pokud k nim přidám šum s normálním rozdělením (střední hodnota je 0.0, odchylka 0.1):
np.random.seed(0)
x = np.array(range(1, X + 1))
for name, (func, coef) in SAMPLE_FUNCTIONS.items():
a, b = MAX_A, coef
y = func(x, a, b) * (1 + np.random.normal(0.0, 0.1, size=x.shape))
plt.plot(x, y, label=name)
plt.legend(bbox_to_anchor=(1.04,1), loc="upper left")
plt.show()
Dále jsem se pokusil zjisit, jaký vliv má přidaný šum na moji chopnost správně detekovat proběh funkce.
Proto jsem pro každý průběh funkce udělal testovací běh, ve kterém:
- zkoumám chyby s odchylkou v rozmezí <0.0, 0.2>
- pro každou odchylku udělám 100 testovacích běhů
- počítám pravděpodobnost správného určení průběhu funkce
A zde je výsledek:
np.random.seed(0)
X = 100
MAX_A, MAX_Y = 10, 1000
x = np.array(range(1, X + 1))
deviations = np.arange(0.0, 0.21, 0.02)
sample_per_deviation = 100
for name, (func, coef) in SAMPLE_FUNCTIONS.items():
a, b = MAX_A, coef
success = np.zeros(deviations.shape)
for i, deviation in enumerate(deviations):
for j in range(sample_per_deviation):
y = func(x, a, b) * (1 + np.random.normal(0.0, deviation, size=x.shape))
comp = complexity_phase(x, y, X)
success[i] += int(comp == name)
val = success / sample_per_deviation
plt.plot(deviations, val, label=name)
plt.legend(bbox_to_anchor=(1.04,1), loc="upper left")
plt.xlabel("noise - deviation")
plt.ylabel("probability of determination")
plt.show()
S odchylkou 0.1 a výše se moje schopnost rozpoznat průběh funkce znatelně zhoršuje. Daří se to stále dobře pro krajní průběhy, jako je 0(1) a O(2n).
Vliv počtu vzorků na detekci funkce
Dále jsem se zkusil podívat, jak mně bude ovlivňovat počet vzorků mou schopnost detekovat proběh funkce.
Proto jsem pro každý průběh funkce udělal testovací běh, ve kterém:
- zkoumám počty vzorků dat v rozmezí <2, 100>
- pro každý počet vzorků udělám 100 testovacích běhů
- počítám pravděpodobnost správného určení průběhu funkce
Navíc jsem nechal zařazenu i jistou úrověň šumu s odchylkou 0.1
A zde je výsledek:
np.random.seed(0)
X = 100
MAX_A, MAX_Y = 10, 1000
deviation = 0.1
sample_per_size = 100
x = np.array(range(1, X + 1))
data_size = np.arange(2, X + 1, 2)
for name, (func, coef) in SAMPLE_FUNCTIONS.items():
a, b = MAX_A, coef
success = np.zeros(data_size.shape)
for i, size in enumerate(data_size):
for j in range(sample_per_size):
y = func(x, a, b) * (1 + np.random.normal(0.0, deviation, size=x.shape))
comp = complexity_phase(x, y, size)
success[i] += int(comp == name)
val = success / sample_per_deviation
plt.plot(data_size, val, label=name)
plt.legend(bbox_to_anchor=(1.04,1), loc="upper left")
plt.xlabel("data size")
plt.ylabel("probability of determination")
plt.show()
Pro malý počet vzorků je spíše otázka náhody, zda se mně podaří správně určit průbeh funkce. Od počtu 20 vzroků a více je to ale docela slušné. Z toho alespoň pro mne plyne závěr, že není potřeba to příliš přehánět s počtem testovacích vzorků dat.
A to je pro dnešek vše, ale pokračování ještě bude.
-
Výborně. Jak říkali v Pelíškách, takový práce a přitom taková blbost :).
Většinou lidé začnou tím, že to zkusí, a pak mudrují. Vy jste si ovšem pečlivě připravil analýzu chyb. Je to analýza experimentální, ne teoretická, ale o to je to zajímavější.
"počítám pravděpodobnost správného určení průběhu funkce" si překládám jako "vydělím zašuměné nezašuměným.
jedno typo: vzroků
U jména se Vám nezobrazuje profesní background, asi by to bylo zajímavé.
-
Přeji pěkný den,
Je mně líto, že ten text považujete za blbost. Nic lepšího mne v daný moment nenapadlo.
Zajímal vás můj profesní background: https://www.linkedin.com/in/jiri-raska-6762703b/
ČLÁNKY DO MAILU