Jdi na navigaci předmětu

1. Domácí úkol: Porovnání

using DataFrames, CSV, PyPlot

Import naměřených dat.

data = CSV.read("files/measurements.csv", DataFrame);
data[!, :score] = zeros(Int64, nrow(data));

Význam jednotlivých sloupců je následující:

dense_time a dense_memory: čas a paměť potřebná k převodu husté Float64 $1000\times1000$ matice na rHST.
jacobi_time a jacobi_memory: čas a paměť potřebná k převodu tridiagonální Float64 $1000\times1000$ matice na rHST.
bigint_time a bigint_memory: čas a paměť potřebná k převodu husté BigInt $1000\times1000$ matice na rHST.
inverse_time a inverse_memory: čas a paměť potřebná výpočtu inverze husté Float64 $500\times500$ matice.
solve_time a solve_memory: čas a paměť potřebná k vyřešení soustavy s Float64 $500\times500$ maticí.
loc: čistý počet řádků kódu v souboru gauss.jl (tj. bez komentářů a prázdných řádků).

Čas v původních datech je měřen v nanosekundách, paměť v bytech. Každá hodnota je medián několika běhů benchmarku z balíčku BechmarkTools.jl. Všechny výpočty běží na stejných předem vygenerovaných maticích.

Poznámky

Vedle studentů je v tabulce i můj řádek (kalvotom) a řádek odpovídající rref metodě z RowEchelon.jl balíčku, která by měla obsahovat původní implementaci v Julia od Jeffa Bezansona (username bezanson; není ale použitelná mimo strojová čísla a v případě invertování a řešení soustavy).
U některých studentů v třetím a čtvrtém benchmarku (velká matice s BigInt a inverze větší husté metodě) došlo k chybě (missing hodnoty v tabulce). Detailně jsem chybu neprozkoumával.
Pro lepší porovnání časů provedem vždy relativní porovnání s nejrychlejším časem. Měníme proto hodnoty a význam časových sloupců!

Převod na rHST: hustá `Float64` matice $1000\times1000$

data[!, :dense_time] /= minimum(data.dense_time);
sort!(data, [:dense_time]);

for k in axes(data, 1)
    data[k, :score] += k
end

data[:, Cols(:username, :dense_time, :dense_memory, :score)]

17 rows × 4 columns

	username	dense_time	dense_memory	score
	String15	Float64	Int64	Int64
1	Sylean	1.0	0	1
2	kalvotom	4.67911	16784	2
3	bezanson	4.85189	16305744	3
4	Syleanlas	19.2848	16611328000	4
5	Luerailthus	21.214	24608	5
6	Amalian	25.2711	24041441904	6
7	Firtherdrim	33.8765	16264128000	7
8	Ansrael	38.502	24392144784	8
9	Aeraelael	43.7319	32541081648	9
10	Ahthievar	44.258	32511998848	10
11	Angemar	44.8692	32553995280	11
12	Aeremarlas	45.4071	32508024832	12
13	Sumaelran	48.4314	32718683520	13
14	Yadrimran	50.0766	32512000000	14
15	Dolkraeslera	50.5174	32524458496	15
16	Zaevar	51.5113	32500505312	16
17	Kanthidul	51.5616	33024271424	17

Relativní porovnání rychlosti běhu vzhledem k nejrychlejšímu řešení.

plt.grid()
bar(axes(data.dense_time, 1), data.dense_time, tick_label=data.username)
plt.xticks(rotation=80);

Odhad alokace paměti (v bytech).

plt.grid()
bar(axes(data.dense_memory, 1), data.dense_memory, tick_label=data.username)
plt.xticks(rotation=80);

Převod na rHST: tridiagonální `Float64` matice $1000\times1000$

data[!, :jacobi_time] /= minimum(data.jacobi_time);
sort!(data, [:jacobi_time]);

for k in axes(data, 1)
    data[k, :score] += k
end

data[:, Cols(:username, :jacobi_time, :jacobi_memory, :score)]

17 rows × 4 columns

	username	jacobi_time	jacobi_memory	score
	String15	Float64	Int64	Int64
1	Sylean	1.0	0	2
2	Angemar	257.787	3261732464	13
3	Sumaelran	288.706	3389130960	16
4	kalvotom	326.531	16784	6
5	Yadrimran	327.473	3257669888	19
6	Kanthidul	374.83	3394381952	23
7	bezanson	397.882	16305744	10
8	Syleanlas	1350.48	16611328000	12
9	Luerailthus	1461.55	24608	14
10	Amalian	1794.9	24041441904	16
11	Firtherdrim	2365.98	16264128000	18
12	Ansrael	2847.43	24392144784	20
13	Dolkraeslera	2939.91	32524458496	28
14	Aeraelael	3092.01	32541081648	23
15	Aeremarlas	3136.43	32508024832	27
16	Ahthievar	3167.73	32506439296	26
17	Zaevar	3853.9	32500505312	33

Relativní porovnání rychlosti běhu vzhledem k nejrychlejšímu řešení.

plt.grid()
bar(axes(data.jacobi_time, 1), data.jacobi_time, tick_label=data.username)
plt.xticks(rotation=80);

Odhad alokace paměti (v bytech).

plt.grid()
bar(axes(data.jacobi_memory, 1), data.jacobi_memory, tick_label=data.username)
plt.xticks(rotation=80);

Převod na rHST: hustá `BigInt` matice $1000\times1000$

Počítáme pak v Rational{BigInt}.

mask = .!ismissing.(data.bigint_time);

data[mask, :bigint_time] /= minimum(data[mask, :bigint_time]);
sort!(data, [:bigint_time]);
mask = .!ismissing.(data.bigint_time);

for k in axes(data, 1)
    data[k, :score] += k
end

data[:, Cols(:username, :bigint_time, :bigint_memory, :score)]

17 rows × 4 columns

	username	bigint_time	bigint_memory	score
	String15	Float64?	Int64?	Int64
1	Syleanlas	1.0	346625720	13
2	Sylean	1.06316	303363424	4
3	kalvotom	1.07351	308854560	9
4	Amalian	1.30668	630412816	20
5	Ansrael	1.32124	636665456	25
6	Yadrimran	1.33959	654035360	25
7	Firtherdrim	1.35772	622371224	25
8	Dolkraeslera	1.40171	654275536	36
9	Angemar	1.40181	656201808	22
10	Zaevar	1.45042	654499600	43
11	Kanthidul	1.52535	656142664	34
12	Aeremarlas	1.54036	696835208	39
13	Ahthievar	5.1328	1177300376	39
14	Sumaelran	5.47222	1174261600	30
15	bezanson	missing	missing	25
16	Luerailthus	missing	missing	30
17	Aeraelael	missing	missing	40

Relativní porovnání ryuchlosti běhu vzhledem k nejrychlejšímu řešení.

plt.grid()
bar(axes(data[mask, :bigint_time], 1), data[mask, :bigint_time], tick_label=data[mask, :username])
plt.xticks(rotation=80);

Odhad alokace paměti (v bytech).

plt.grid()
bar(axes(data[mask, :bigint_memory], 1), data[mask, :bigint_memory], tick_label=data[mask, :username])
plt.xticks(rotation=80);

Invertování husté $500\times500$ matice

mask = .!ismissing.(data.inverse_time);

data[mask, :inverse_time] /= minimum(data[mask, :inverse_time]);
sort!(data, [:inverse_time]);
mask = .!ismissing.(data.inverse_time);

for k in axes(data, 1)
    data[k, :score] += k
end

data[:, Cols(:username, :inverse_time, :inverse_memory, :score)]

17 rows × 4 columns

	username	inverse_time	inverse_memory	score
	String15	Float64?	Int64?	Int64
1	Sylean	1.0	4250416	5
2	kalvotom	5.39649	8008768	11
3	Luerailthus	8.47118	12009040	33
4	Amalian	25.9143	6022746272	24
5	Syleanlas	29.6776	6166122432	18
6	Ansrael	36.5642	6106322960	31
7	Yadrimran	37.5335	8136000240	32
8	Aeraelael	37.6703	8153216192	48
9	Angemar	38.0189	8156805584	31
10	Ahthievar	38.1064	8135952064	49
11	Zaevar	38.1123	8127368336	54
12	Dolkraeslera	45.0412	8139549200	48
13	Kanthidul	55.8287	8246771120	47
14	Sumaelran	65.9994	8408934640	44
15	Aeremarlas	1023.89	28840066064	54
16	Firtherdrim	missing	missing	41
17	bezanson	missing	missing	42

plt.grid()
bar(axes(data[mask, :inverse_time], 1), data[mask, :inverse_time], tick_label=data[mask, :username])
plt.xticks(rotation=80);

plt.grid()
bar(axes(data[mask, :inverse_memory], 1), data[mask, :inverse_memory], tick_label=data[mask, :username])
plt.xticks(rotation=80);

Řešení soustavy s hustou $500\times500$ maticí

mask = .!ismissing.(data.solve_time);

data[mask, :solve_time] /= minimum(data[mask, :solve_time]);
sort!(data, [:solve_time]);
mask = .!ismissing.(data.solve_time);

for k in axes(data, 1)
    data[k, :score] += k
end

data[:, Cols(:username, :solve_time, :solve_memory, :score)]

17 rows × 4 columns

	username	solve_time	solve_memory	score
	String15	Float64?	Int64?	Int64
1	Sylean	1.0	2008272	6
2	kalvotom	3.4912	2020960	13
3	Luerailthus	7.68733	2016800	36
4	Firtherdrim	29.7404	2086172432	45
5	Amalian	30.0077	3018846448	29
6	Syleanlas	40.0174	2155928352	24
7	Ansrael	40.1764	3124108992	38
8	Yadrimran	46.7672	4162008272	40
9	Aeremarlas	47.0253	4161005328	63
10	Aeraelael	47.2196	4181183120	58
11	Angemar	47.5359	4173877040	42
12	Zaevar	48.8256	4159094176	66
13	Ahthievar	58.7506	4168176192	62
14	Kanthidul	59.2456	4272782848	61
15	Dolkraeslera	59.2739	4175276336	63
16	Sumaelran	62.2772	4228913456	60
17	bezanson	missing	missing	59

plt.grid()
bar(axes(data[mask, :solve_time], 1), data[mask, :solve_time], tick_label=data[mask, :username])
plt.xticks(rotation=80);

plt.grid()
bar(axes(data[mask, :solve_memory], 1), data[mask, :solve_memory], tick_label=data[mask, :username])
plt.xticks(rotation=80);

Čistý počet řádků kódu v `gauss.jl`

sort!(data, [:loc]);
mask = .!ismissing.(data.loc);

for k in axes(data, 1)
    data[k, :score] += k
end

data[:, Cols(:username, :loc, :score)]

17 rows × 3 columns

	username	loc	score
	String15	Int64?	Int64
1	Kanthidul	60	62
2	Amalian	61	31
3	Firtherdrim	69	48
4	Aeraelael	71	62
5	Angemar	75	47
6	kalvotom	82	19
7	Ansrael	84	45
8	Syleanlas	88	32
9	Zaevar	96	75
10	Dolkraeslera	100	73
11	Sumaelran	100	71
12	Aeremarlas	102	75
13	Yadrimran	114	53
14	Sylean	130	20
15	Luerailthus	134	51
16	Ahthievar	154	78
17	bezanson	missing	76

plt.grid()
bar(axes(data[mask, :loc], 1), data[mask, :loc], tick_label=data[mask, :username])
plt.xticks(rotation=80);

Skóre (čím menší hodnota, tím lépe)

sort!(data, :score)
data[:, :points] = zeros(Int64, nrow(data))

n = 0
for k in axes(data, 1)
    # kalvotom a bezanson se nepočítají, zbývá 15 studentů
    if data[k, :username] == "kalvotom" || data[k, :username] == "bezanson"
        continue
    end
    
    data[k, :points] = 5 - div(n, 5)
    n += 1
end

data[:, Cols(:username, :score, :points)]

17 rows × 3 columns

	username	score	points
	String15	Int64	Int64
1	kalvotom	19	0
2	Sylean	20	5
3	Amalian	31	5
4	Syleanlas	32	5
5	Ansrael	45	5
6	Angemar	47	5
7	Firtherdrim	48	4
8	Luerailthus	51	4
9	Yadrimran	53	4
10	Kanthidul	62	4
11	Aeraelael	62	4
12	Sumaelran	71	3
13	Dolkraeslera	73	3
14	Zaevar	75	3
15	Aeremarlas	75	3
16	bezanson	76	0
17	Ahthievar	78	3

1. Domácí úkol: Porovnání

Poznámky

Převod na rHST: hustá Float64 matice 1000×10001000\times10001000×1000

Převod na rHST: tridiagonální Float64 matice 1000×10001000\times10001000×1000

Převod na rHST: hustá BigInt matice 1000×10001000\times10001000×1000

Invertování husté 500×500500\times500500×500 matice

Řešení soustavy s hustou 500×500500\times500500×500 maticí

Čistý počet řádků kódu v gauss.jl

Skóre (čím menší hodnota, tím lépe)

Převod na rHST: hustá `Float64` matice $1000\times1000$

Převod na rHST: tridiagonální `Float64` matice $1000\times1000$

Převod na rHST: hustá `BigInt` matice $1000\times1000$

Invertování husté $500\times500$ matice

Řešení soustavy s hustou $500\times500$ maticí

Čistý počet řádků kódu v `gauss.jl`