3. Porovnání (Kulečník)

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
end

record_rank!

Načtení dat a přidání "skórovacího" sloupce.

df = CSV.read("results03.csv", DataFrame)
df[!, "score"] .= 0
describe(df)

7×7 DataFrame

Row	variable	mean	min	median	max	nmissing	eltype
	Symbol	Union…	Any	Union…	Any	Int64	Type
1	nickname		Aheronin		Uwyss	0	String15
2	simulate_time	6.97308e8	3.87019e8	6.12738e8	1.81023e9	20	Union{Missing, Float64}
3	simulate_mem	6.06668e8	257926032	5.54537e8	1183489376	20	Union{Missing, Int64}
4	check_x	20.5632	-160.896	68.6408	68.6408	20	Union{Missing, Float64}
5	check_y	-217.579	-272.722	-272.722	176.898	20	Union{Missing, Float64}
6	error		(Not found)		ErrorException (simulation)	13	Union{Missing, String31}
7	score	0.0	0	0.0	0	0	Int64

Pozor! Tento benchmark nebyl úplně přímočarý na provedení. Řada implementací zdá se zvláštně selhává :-). Do sloupce error jsem zaznamenal důvod:

Not found: úkol nebyl odevzdán,
simulation: výjimka při pokusu o spuštění simulace (popis situace viz níže),
Table constructor: výjimka při pokusu o vytvoření kulečníku.

show(df[!,[:nickname, :error]], allrows=true)

33×2 DataFrame
 Row │ nickname   error                       
     │ String15   String31?                   
─────┼────────────────────────────────────────
   1 │ Kalvotom   missing                     
   2 │ Tiharis    missing                     
   3 │ Asuras     missing                     
   4 │ Khoviar    missing                     
   5 │ Offyn      (Not found)
   6 │ Avesior    (Not found)
   7 │ Elleas     missing                     
   8 │ Apan       missing                     
   9 │ Rhuqihr    missing                     
  10 │ Uwyss      ErrorException (simulation)
  11 │ Uhunyll    ErrorException (simulation)
  12 │ Kharnas    (Not found)
  13 │ Ahith      ErrorException (simulation)
  14 │ Korass     ErrorException (simulation)
  15 │ Isigoris   missing                     
  16 │ Gokelis    (Not found)
  17 │ Ozatosh    ErrorException (simulation)
  18 │ Emitrix    (Not found)
  19 │ Isim       (Not found)
  20 │ Ophuqiohn  ErrorException (simulation)
  21 │ Terias     (Not found)
  22 │ Izohr      (Not found)
  23 │ Uphanneas  (Not found)
  24 │ Awyn       missing                     
  25 │ Tomorith   missing                     
  26 │ Ossaem     ErrorException (simulation)
  27 │ Unnemal    missing                     
  28 │ Enyll      (Not found)
  29 │ Aheronin   ErrorException (simulation)
  30 │ Thodelis   missing                     
  31 │ Khukalis   missing                     
  32 │ Sumorith   (Not found)
  33 │ Eluhion    ErrorException (simulation)

Testovací kulečník

Testovací kulečník je složen ze čtyř segmentů a čtyř oblouků. K vykreslení použiji svoji verzi kódu.

include("kalvotom/src/billiard.jl")
using .Billiard

Definice kulečníku.

table = Table([
    Segment([-200., 100.], [-100., 200.]),
    Segment([100., 200.], [200., 100.]),
    Segment([200., -100.], [100., -200.]),
    Segment([-100., -200.], [-200., -100.]),
    Arc([200., 0.], 100., -pi/2, pi/2),
    Arc([0., -200.], 100., pi, 2pi),
    Arc([-200., 0.], 100., pi/2, 3pi/2),
    Arc([0., 200.], 100., 0., pi)
  ])

Billiard table with 8 obstacles.

Benchmark používá následující počáteční podmínky a výpočet 100 000 odrazů. Zde pro jednoduchost zobrazím jen 100.

path = zeros(4, 100)
path[:, 1] = [100, 100, 0.5, -0.33]
simulate!(table, path)

A konečně výsledný obrázek.

draw_path(table, path)

Rychlost

sort!(df, :simulate_time)
record_rank!(df, :simulate_time)
show(df[!,[:nickname, :simulate_time, :score]], allrows=true)

33×3 DataFrame
 Row │ nickname   simulate_time    score 
     │ String15   Float64?         Int64 
─────┼───────────────────────────────────
   1 │ Isigoris         3.87019e8      1
   2 │ Apan             4.54388e8      2
   3 │ Tomorith         4.63095e8      3
   4 │ Khukalis         5.38113e8      4
   5 │ Unnemal          5.84782e8      5
   6 │ Tiharis          5.96013e8      6
   7 │ Asuras           6.12738e8      7
   8 │ Awyn             6.30099e8      8
   9 │ Khoviar          6.85689e8      9
  10 │ Kalvotom         6.9666e8      10
  11 │ Elleas           7.26566e8     11
  12 │ Thodelis         8.79622e8     12
  13 │ Rhuqihr          1.81023e9     13
  14 │ Offyn      missing             13
  15 │ Avesior    missing             13
  16 │ Uwyss      missing             13
  17 │ Uhunyll    missing             13
  18 │ Kharnas    missing             13
  19 │ Ahith      missing             13
  20 │ Korass     missing             13
  21 │ Gokelis    missing             13
  22 │ Ozatosh    missing             13
  23 │ Emitrix    missing             13
  24 │ Isim       missing             13
  25 │ Ophuqiohn  missing             13
  26 │ Terias     missing             13
  27 │ Izohr      missing             13
  28 │ Uphanneas  missing             13
  29 │ Ossaem     missing             13
  30 │ Enyll      missing             13
  31 │ Aheronin   missing             13
  32 │ Sumorith   missing             13
  33 │ Eluhion    missing             13

Paměť

sort!(df, :simulate_mem)
record_rank!(df, :simulate_mem)
show(df[!,[:nickname, :simulate_mem, :score]], allrows=true)

33×3 DataFrame
 Row │ nickname   simulate_mem  score 
     │ String15   Int64?        Int64 
─────┼────────────────────────────────
   1 │ Isigoris      257926032      2
   2 │ Tomorith      462965568      5
   3 │ Apan          470394400      5
   4 │ Awyn          526488288     12
   5 │ Unnemal       530748336     10
   6 │ Asuras        546395616     13
   7 │ Tiharis       554537296     13
   8 │ Khoviar       586101504     17
   9 │ Khukalis      629331824     13
  10 │ Thodelis      664949104     22
  11 │ Kalvotom      734859552     21
  12 │ Elleas        738493744     23
  13 │ Rhuqihr      1183489376     26
  14 │ Offyn           missing     26
  15 │ Avesior         missing     26
  16 │ Uwyss           missing     26
  17 │ Uhunyll         missing     26
  18 │ Kharnas         missing     26
  19 │ Ahith           missing     26
  20 │ Korass          missing     26
  21 │ Gokelis         missing     26
  22 │ Ozatosh         missing     26
  23 │ Emitrix         missing     26
  24 │ Isim            missing     26
  25 │ Ophuqiohn       missing     26
  26 │ Terias          missing     26
  27 │ Izohr           missing     26
  28 │ Uphanneas       missing     26
  29 │ Ossaem          missing     26
  30 │ Enyll           missing     26
  31 │ Aheronin        missing     26
  32 │ Sumorith        missing     26
  33 │ Eluhion         missing     26

Poloha po 10 odrazech

Tento kulečník se také bude chovat chaoticky, takže po uvedených 100 000 odrazech bude u různých výpočtů vlivem i nepatrných zaokrouhlovacích chyb dosaženo velmi rozdílných výsledků.

Podíváme se proto pouze na 10 odrazů. I tak se výsledky přirozeně liší, ale je vidět, že hypotetická správná hodnota je někde kolem bodu $[68, -272]$ . Z hodnot, které jsou blízko této hodnotě napočteme průměr a budeme měřit pořadí podle vzdálenosti od tohoto bodu.

show(df[!,[:nickname, :check_x, :check_y, :score]], allrows=true)

33×4 DataFrame
 Row │ nickname   check_x       check_y      score 
     │ String15   Float64?      Float64?     Int64 
─────┼─────────────────────────────────────────────
   1 │ Isigoris        68.6408     -272.722      2
   2 │ Tomorith        68.6408     -272.722      5
   3 │ Apan            68.6408     -272.722      5
   4 │ Awyn          -160.896      -139.104     12
   5 │ Unnemal         68.6408     -272.722     10
   6 │ Asuras          68.6408     -272.722     13
   7 │ Tiharis        -97.295       176.898     13
   8 │ Khoviar         68.6408     -272.722     17
   9 │ Khukalis        68.6408     -272.722     13
  10 │ Thodelis      -160.896      -139.104     22
  11 │ Kalvotom        68.6408     -272.722     21
  12 │ Elleas          68.6408     -272.722     23
  13 │ Rhuqihr         68.6408     -272.722     26
  14 │ Offyn      missing       missing         26
  15 │ Avesior    missing       missing         26
  16 │ Uwyss      missing       missing         26
  17 │ Uhunyll    missing       missing         26
  18 │ Kharnas    missing       missing         26
  19 │ Ahith      missing       missing         26
  20 │ Korass     missing       missing         26
  21 │ Gokelis    missing       missing         26
  22 │ Ozatosh    missing       missing         26
  23 │ Emitrix    missing       missing         26
  24 │ Isim       missing       missing         26
  25 │ Ophuqiohn  missing       missing         26
  26 │ Terias     missing       missing         26
  27 │ Izohr      missing       missing         26
  28 │ Uphanneas  missing       missing         26
  29 │ Ossaem     missing       missing         26
  30 │ Enyll      missing       missing         26
  31 │ Aheronin   missing       missing         26
  32 │ Sumorith   missing       missing         26
  33 │ Eluhion    missing       missing         26

using Statistics

mean_x = mean(filter(x -> floor(Int64, x) == 68, collect(skipmissing(df.check_x))))
mean_y = mean(filter(y -> ceil(Int64, y) == -272, collect(skipmissing(df.check_y))))
(mean_x, mean_y)

(68.64077846426251, -272.7216854302761)

df[!, :distance] .= Inf
for idx in 1:nrow(df)
    if ismissing(df[idx, :check_x])
        continue
    end
    df[idx, :distance] = sqrt((df[idx, :check_x] - mean_x)^2 + (df[idx, :check_y] - mean_y)^2)
end

sort!(df, :distance)
record_rank!(df, :distance)
show(df[!,[:nickname, :distance, :score]], allrows=true)

33×3 DataFrame
 Row │ nickname   distance       score 
     │ String15   Float64        Int64 
─────┼─────────────────────────────────
   1 │ Tomorith     5.74354e-10      6
   2 │ Khoviar      1.31451e-9      19
   3 │ Kalvotom     1.58204e-9      24
   4 │ Apan         1.61874e-9       9
   5 │ Rhuqihr      1.61997e-9      31
   6 │ Isigoris     1.86925e-9       8
   7 │ Unnemal      1.86925e-9      16
   8 │ Asuras       1.98222e-9      20
   9 │ Elleas       2.12754e-9      31
  10 │ Khukalis     1.19288e-8      22
  11 │ Thodelis   265.595           32
  12 │ Awyn       265.595           23
  13 │ Tiharis    479.263           25
  14 │ Offyn      Inf               39
  15 │ Avesior    Inf               39
  16 │ Uwyss      Inf               39
  17 │ Uhunyll    Inf               39
  18 │ Kharnas    Inf               39
  19 │ Ahith      Inf               39
  20 │ Korass     Inf               39
  21 │ Gokelis    Inf               39
  22 │ Ozatosh    Inf               39
  23 │ Emitrix    Inf               39
  24 │ Isim       Inf               39
  25 │ Ophuqiohn  Inf               39
  26 │ Terias     Inf               39
  27 │ Izohr      Inf               39
  28 │ Uphanneas  Inf               39
  29 │ Ossaem     Inf               39
  30 │ Enyll      Inf               39
  31 │ Aheronin   Inf               39
  32 │ Sumorith   Inf               39
  33 │ Eluhion    Inf               39

Závěrečná tabulka

sort!(df, :score)
show(df[!, [:nickname, :score]], allrows=true)

33×2 DataFrame
 Row │ nickname   score 
     │ String15   Int64 
─────┼──────────────────
   1 │ Tomorith       6
   2 │ Isigoris       8
   3 │ Apan           9
   4 │ Unnemal       16
   5 │ Khoviar       19
   6 │ Asuras        20
   7 │ Khukalis      22
   8 │ Awyn          23
   9 │ Kalvotom      24
  10 │ Tiharis       25
  11 │ Rhuqihr       31
  12 │ Elleas        31
  13 │ Thodelis      32
  14 │ Offyn         39
  15 │ Avesior       39
  16 │ Uwyss         39
  17 │ Uhunyll       39
  18 │ Kharnas       39
  19 │ Ahith         39
  20 │ Korass        39
  21 │ Gokelis       39
  22 │ Ozatosh       39
  23 │ Emitrix       39
  24 │ Isim          39
  25 │ Ophuqiohn     39
  26 │ Terias        39
  27 │ Izohr         39
  28 │ Uphanneas     39
  29 │ Ossaem        39
  30 │ Enyll         39
  31 │ Aheronin      39
  32 │ Sumorith      39
  33 │ Eluhion       39