Hlavní navigace

Nezávazné bádání nad časovou náročností programu - II

21. 2. 2021 0:00 Jiří Raška

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.

In [1]:
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:

In [2]:
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()
image01

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ů:

In [3]:
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:

In [4]:
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)}")
O(1)     ==> O(1)
O(log n) ==> O(log n)
O(n)     ==> O(n)
O(n^2)   ==> O(n^2)
O(n^4)   ==> O(n^4)
O(2^n)   ==> O(2^n)

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):

In [5]:
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()
image02

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:

In [6]:
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()
image03

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:

In [7]:
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()
image04

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.

Sdílet