1. Porovnání (Catalanova čísla)
Porovnání jednotlivých řešení.
using CSV, DataFrames"""
Pomocná hodnotící funkce přidělující body ve sloupci `score` pod pořadí ve sloupci `column` (seřazeném).
"""
function record_rank!(data_frame::DataFrame, column::Symbol)
rank = 1
value = first(data_frame[!, column])
for row in eachrow(data_frame)
if !ismissing(row[column]) && row[column] != value
value = row[column]
rank += 1
end
row[:score] += rank
end
endrecord_rank!
Načtení dat a přidání "skórovacího" sloupce.
df = CSV.read("results01.csv", DataFrame)
df[!, "score"] .= 0
describe(df)10×7 DataFrame
| Row | variable | mean | min | median | max | nmissing | eltype |
|---|---|---|---|---|---|---|---|
| Symbol | Union… | Any | Union… | Any | Int64 | Type | |
| 1 | nickname | Aheronin | Uwyss | 0 | String15 | ||
| 2 | int64_count_correct | 30.6364 | 0 | 34.0 | 35 | 0 | Int64 |
| 3 | int64_time_median | 587.711 | 1.307 | 196.006 | 7440.62 | 3 | Union{Missing, Float64} |
| 4 | int64_mem_median | 221.067 | 0 | 0.0 | 5320 | 3 | Union{Missing, Int64} |
| 5 | uint64_time_median | 879.645 | 1.307 | 272.724 | 9298.83 | 10 | Union{Missing, Float64} |
| 6 | uint64_mem_median | 321.043 | 0 | 0.0 | 6032 | 10 | Union{Missing, Int64} |
| 7 | bigint_100 | 1.0 | true | 1.0 | true | 3 | Union{Missing, Bool} |
| 8 | bigint_time_median | 36962.5 | 1898.8 | 36475.2 | 1.13206e5 | 3 | Union{Missing, Float64} |
| 9 | bigint_mem_median | 29167.2 | 624 | 26084.0 | 99688 | 3 | Union{Missing, Int64} |
| 10 | score | 0.0 | 0 | 0.0 | 0 | 0 | Int64 |
Int64 pokusy
Pro jak velké hodnoty Int64 vstupu dostáváme správný výsledek (poslední Catalanovo číslo reprezentovatelné v Int64 je pro n=35).
sort!(df, :int64_count_correct, rev=true)
record_rank!(df, :int64_count_correct)
show(df[!,[:nickname, :int64_count_correct, :score]], allrows=true)33×3 DataFrame Row │ nickname int64_count_correct score │ String15 Int64 Int64 ─────┼─────────────────────────────────────── 1 │ Asuras 35 1 2 │ Elleas 35 1 3 │ Korass 35 1 4 │ Uphanneas 35 1 5 │ Awyn 35 1 6 │ Tomorith 35 1 7 │ Ossaem 35 1 8 │ Aheronin 35 1 9 │ Thodelis 35 1 10 │ Kalvotom 34 2 11 │ Offyn 34 2 12 │ Rhuqihr 34 2 13 │ Uwyss 34 2 14 │ Ahith 34 2 15 │ Isigoris 34 2 16 │ Ozatosh 34 2 17 │ Emitrix 34 2 18 │ Ophuqiohn 34 2 19 │ Terias 34 2 20 │ Izohr 34 2 21 │ Unnemal 34 2 22 │ Enyll 34 2 23 │ Khukalis 34 2 24 │ Eluhion 34 2 25 │ Tiharis 31 3 26 │ Khoviar 31 3 27 │ Apan 31 3 28 │ Uhunyll 31 3 29 │ Gokelis 31 3 30 │ Isim 31 3 31 │ Avesior 0 4 32 │ Kharnas 0 4 33 │ Sumorith 0 4
Rychlost výpočtu catalan(30), měřeno pomocí BenchmarTools.jl, hodnota mediánu je v ns.
sort!(df, :int64_time_median)
record_rank!(df, :int64_time_median)
show(df[!,[:nickname, :int64_time_median, :score]], allrows=true)33×3 DataFrame Row │ nickname int64_time_median score │ String15 Float64? Int64 ─────┼───────────────────────────────────── 1 │ Isigoris 1.307 3 2 │ Kalvotom 1.308 4 3 │ Rhuqihr 1.308 4 4 │ Ophuqiohn 1.308 4 5 │ Terias 1.308 4 6 │ Izohr 1.308 4 7 │ Unnemal 1.308 4 8 │ Gokelis 1.308 5 9 │ Korass 1.31 4 10 │ Enyll 1.31 5 11 │ Apan 1.314 7 12 │ Isim 30.5221 8 13 │ Tiharis 31.3028 9 14 │ Tomorith 114.37 8 15 │ Khoviar 131.062 11 16 │ Uwyss 260.95 11 17 │ Emitrix 267.456 12 18 │ Ahith 267.475 13 19 │ Eluhion 267.488 14 20 │ Ozatosh 267.539 15 21 │ Uhunyll 309.298 17 22 │ Khukalis 374.083 17 23 │ Offyn 382.549 18 24 │ Uphanneas 746.422 18 25 │ Thodelis 878.224 19 26 │ Awyn 886.78 20 27 │ Ossaem 1505.8 21 28 │ Elleas 1530.7 22 29 │ Aheronin 1924.3 23 30 │ Asuras 7440.62 24 31 │ Avesior missing 27 32 │ Kharnas missing 27 33 │ Sumorith missing 27
Paměťová náročnost (hodnota v bytech).
sort!(df, :int64_mem_median)
record_rank!(df, :int64_mem_median)
show(df[!,[:nickname, :int64_mem_median, :score]], allrows=true)33×3 DataFrame Row │ nickname int64_mem_median score │ String15 Int64? Int64 ─────┼──────────────────────────────────── 1 │ Isigoris 0 4 2 │ Kalvotom 0 5 3 │ Rhuqihr 0 5 4 │ Ophuqiohn 0 5 5 │ Terias 0 5 6 │ Izohr 0 5 7 │ Unnemal 0 5 8 │ Gokelis 0 6 9 │ Korass 0 5 10 │ Enyll 0 6 11 │ Apan 0 8 12 │ Isim 0 9 13 │ Tiharis 0 10 14 │ Tomorith 0 9 15 │ Khoviar 0 12 16 │ Uwyss 0 12 17 │ Emitrix 0 13 18 │ Ahith 0 14 19 │ Eluhion 0 15 20 │ Ozatosh 0 16 21 │ Uhunyll 0 18 22 │ Khukalis 0 18 23 │ Offyn 0 19 24 │ Ossaem 0 22 25 │ Aheronin 0 24 26 │ Uphanneas 248 20 27 │ Thodelis 304 22 28 │ Awyn 304 23 29 │ Elleas 456 26 30 │ Asuras 5320 29 31 │ Avesior missing 32 32 │ Kharnas missing 32 33 │ Sumorith missing 32
UInt64 pokusy
Stejné experimenty jako výše pouze s hodnotou UInt64(34).
sort!(df, :uint64_time_median)
record_rank!(df, :uint64_time_median)
show(df[!,[:nickname, :uint64_time_median, :score]], allrows=true)33×3 DataFrame Row │ nickname uint64_time_median score │ String15 Float64? Int64 ─────┼────────────────────────────────────── 1 │ Korass 1.307 6 2 │ Kalvotom 1.308 7 3 │ Rhuqihr 1.308 7 4 │ Enyll 1.308 8 5 │ Tiharis 33.857 13 6 │ Isim 33.9547 13 7 │ Tomorith 121.773 14 8 │ Khoviar 144.884 18 9 │ Uwyss 264.896 19 10 │ Emitrix 272.712 21 11 │ Eluhion 272.718 24 12 │ Ahith 272.724 24 13 │ Ozatosh 272.958 27 14 │ Uhunyll 333.314 30 15 │ Offyn 365.411 32 16 │ Khukalis 369.227 32 17 │ Uphanneas 827.436 35 18 │ Awyn 963.783 39 19 │ Thodelis 975.444 39 20 │ Elleas 1618.1 44 21 │ Ossaem 1651.7 41 22 │ Aheronin 2132.89 44 23 │ Asuras 9298.83 50 24 │ Isigoris missing 25 25 │ Ophuqiohn missing 26 26 │ Terias missing 26 27 │ Izohr missing 26 28 │ Unnemal missing 26 29 │ Gokelis missing 27 30 │ Apan missing 29 31 │ Avesior missing 53 32 │ Kharnas missing 53 33 │ Sumorith missing 53
sort!(df, :uint64_mem_median)
record_rank!(df, :uint64_mem_median)
show(df[!,[:nickname, :uint64_mem_median, :score]], allrows=true)33×3 DataFrame Row │ nickname uint64_mem_median score │ String15 Int64? Int64 ─────┼───────────────────────────────────── 1 │ Korass 0 7 2 │ Kalvotom 0 8 3 │ Rhuqihr 0 8 4 │ Enyll 0 9 5 │ Tiharis 0 14 6 │ Isim 0 14 7 │ Tomorith 0 15 8 │ Khoviar 0 19 9 │ Uwyss 0 20 10 │ Emitrix 0 22 11 │ Eluhion 0 25 12 │ Ahith 0 25 13 │ Ozatosh 0 28 14 │ Uhunyll 0 31 15 │ Offyn 0 33 16 │ Khukalis 0 33 17 │ Ossaem 0 42 18 │ Aheronin 0 45 19 │ Uphanneas 256 37 20 │ Awyn 312 42 21 │ Thodelis 312 42 22 │ Elleas 472 48 23 │ Asuras 6032 55 24 │ Isigoris missing 30 25 │ Ophuqiohn missing 31 26 │ Terias missing 31 27 │ Izohr missing 31 28 │ Unnemal missing 31 29 │ Gokelis missing 32 30 │ Apan missing 34 31 │ Avesior missing 58 32 │ Kharnas missing 58 33 │ Sumorith missing 58
BigInt pokusy
Správnost výsledku pro vstup big"100".
sort!(df, :bigint_100, rev=true)
df.score += coalesce.(df.bigint_100 .== true, false) # zde pouze přičteme bod těm s true hodnotou
show(df[!,[:nickname, :bigint_100, :score]], allrows=true)33×3 DataFrame Row │ nickname bigint_100 score │ String15 Bool? Int64 ─────┼────────────────────────────── 1 │ Avesior missing 58 2 │ Kharnas missing 58 3 │ Sumorith missing 58 4 │ Korass true 8 5 │ Kalvotom true 9 6 │ Rhuqihr true 9 7 │ Enyll true 10 8 │ Tiharis true 15 9 │ Isim true 15 10 │ Tomorith true 16 11 │ Khoviar true 20 12 │ Uwyss true 21 13 │ Emitrix true 23 14 │ Eluhion true 26 15 │ Ahith true 26 16 │ Ozatosh true 29 17 │ Uhunyll true 32 18 │ Offyn true 34 19 │ Khukalis true 34 20 │ Ossaem true 43 21 │ Aheronin true 46 22 │ Uphanneas true 38 23 │ Awyn true 43 24 │ Thodelis true 43 25 │ Elleas true 49 26 │ Asuras true 56 27 │ Isigoris true 31 28 │ Ophuqiohn true 32 29 │ Terias true 32 30 │ Izohr true 32 31 │ Unnemal true 32 32 │ Gokelis true 33 33 │ Apan true 35
A poté opět čas a paměť.
sort!(df, :bigint_time_median)
record_rank!(df, :bigint_time_median)
show(df[!,[:nickname, :bigint_time_median, :score]], allrows=true)33×3 DataFrame Row │ nickname bigint_time_median score │ String15 Float64? Int64 ─────┼────────────────────────────────────── 1 │ Uphanneas 1898.8 39 2 │ Thodelis 1922.9 45 3 │ Unnemal 1929.4 35 4 │ Izohr 1929.5 36 5 │ Terias 1938.1 37 6 │ Awyn 1947.65 49 7 │ Ophuqiohn 2010.0 39 8 │ Isigoris 2031.1 39 9 │ Rhuqihr 2167.89 18 10 │ Apan 2464.89 45 11 │ Gokelis 2491.67 44 12 │ Elleas 3482.69 61 13 │ Enyll 4039.0 23 14 │ Eluhion 23578.0 40 15 │ Kalvotom 34782.0 24 16 │ Korass 38168.5 24 17 │ Tomorith 49116.0 33 18 │ Offyn 52872.0 52 19 │ Khukalis 53092.0 53 20 │ Khoviar 55053.0 40 21 │ Ozatosh 56713.0 50 22 │ Emitrix 57047.0 45 23 │ Ahith 64156.0 49 24 │ Asuras 66209.0 80 25 │ Uwyss 68153.0 46 26 │ Tiharis 78421.0 41 27 │ Isim 82499.0 42 28 │ Ossaem 82836.5 71 29 │ Uhunyll 102720.0 61 30 │ Aheronin 1.13206e5 76 31 │ Avesior missing 88 32 │ Kharnas missing 88 33 │ Sumorith missing 88
sort!(df, :bigint_mem_median)
record_rank!(df, :bigint_mem_median)
show(df[!,[:nickname, :bigint_mem_median, :score]], allrows=true)33×3 DataFrame Row │ nickname bigint_mem_median score │ String15 Int64? Int64 ─────┼───────────────────────────────────── 1 │ Uphanneas 624 40 2 │ Thodelis 624 46 3 │ Unnemal 624 36 4 │ Terias 624 38 5 │ Awyn 624 50 6 │ Izohr 664 38 7 │ Ophuqiohn 672 42 8 │ Isigoris 704 43 9 │ Rhuqihr 784 23 10 │ Apan 968 51 11 │ Gokelis 968 50 12 │ Elleas 1088 68 13 │ Enyll 1520 31 14 │ Eluhion 14416 49 15 │ Kalvotom 24184 34 16 │ Korass 27984 35 17 │ Khukalis 34088 65 18 │ Offyn 34416 65 19 │ Tomorith 38816 47 20 │ Ozatosh 42280 65 21 │ Emitrix 42280 60 22 │ Ahith 47080 65 23 │ Asuras 47840 97 24 │ Khoviar 52912 58 25 │ Uwyss 53928 65 26 │ Tiharis 72824 61 27 │ Uhunyll 75328 82 28 │ Isim 77576 64 29 │ Ossaem 78888 94 30 │ Aheronin 99688 100 31 │ Avesior missing 112 32 │ Kharnas missing 112 33 │ Sumorith missing 112
Závěrečná tabulka
Zaznamenávali jsme v každé kategorii (sdílené) pořadí. Čím nižší hodnota, tím lepší výsledek.
sort!(df, :score)
show(df[!,[:nickname, :score]], allrows=true)33×2 DataFrame Row │ nickname score │ String15 Int64 ─────┼────────────────── 1 │ Rhuqihr 23 2 │ Enyll 31 3 │ Kalvotom 34 4 │ Korass 35 5 │ Unnemal 36 6 │ Terias 38 7 │ Izohr 38 8 │ Uphanneas 40 9 │ Ophuqiohn 42 10 │ Isigoris 43 11 │ Thodelis 46 12 │ Tomorith 47 13 │ Eluhion 49 14 │ Awyn 50 15 │ Gokelis 50 16 │ Apan 51 17 │ Khoviar 58 18 │ Emitrix 60 19 │ Tiharis 61 20 │ Isim 64 21 │ Khukalis 65 22 │ Offyn 65 23 │ Ozatosh 65 24 │ Ahith 65 25 │ Uwyss 65 26 │ Elleas 68 27 │ Uhunyll 82 28 │ Ossaem 94 29 │ Asuras 97 30 │ Aheronin 100 31 │ Avesior 112 32 │ Kharnas 112 33 │ Sumorith 112
Poznámky k prvnímu úkolu
- Využívejte typové anotace a typové proměnné!
function f(x::T) where {T <: Real}
return x + one(T) # T(1)
endf (generic function with 1 method)
f(1)2
f(3.3)4.3
- Snažte se vyhnout přetypovávání.
- Jako velmi rychlá se ukazuje implementace pomocí
binomial, která navíc využívá makra.
@which binomial(3, 2)binomial(n::T, k::T) where T<:Integer in Base at intfuncs.jl:1063
Je zajímavé porovnat Julia zdrojový kód s analogickou implementací v "Pythonu":