Proton

[mytja]

Proton

[mytja]

Just a little update. Proton now seems to generate timetables successfully. It's still in very early development phase, as it doesn't currently obey all the instructions and rules. It will be finished (most likely) by the end of July. Just a screenshot on what's currently doing.

If there aren't any pushes to main branch, this means I'm working on Proton locally, as I won't push any code until it works and is stable.

Here is the status of the rules it currently obeys:

• Full days of teacher on the school - Polni dnevi učitelja
• Teacher's hours on the school - Ure učitelja na šoli
• Subject groups - Skupine predmetov
• Subjects with stacked hours - Predmeti z blok urami
• Subjects before or after class - Predmeti pred ali po pouku

Here is the status of what needs to be done besides rules:

• Fill the holes and optimize timetable to be without holes for students
• Normalize the timetable - students shouldn't have, for example, one day 4 hours and the other day 7 hours.

Be sure to comment here if you think I missed something or you think I should add something.

[mytja]

NEW UPDATE!!!

Proton zdaj upošteva tudi skupine predmetov. Sicer zaradi tega, ker še nisem naredil optimizacij, ne ustvarja "lepega" urnika, ampak tukaj lahko vidite trenutno demonstracijo. Proton je dejansko tudi hiter, glede na to, da uporabljamo "brute force" metode za generacijo. Vsi requesti so pod 100ms, čeprav nimam še ustvarjenih vseh predmetov za vseh 9 razredov OŠ (česar tudi verjetno ne bom naredil)...

PS
Oprostite mi, če bom kdaj govoril slovensko, kdaj pa angleško. Govorim v tistemu jeziku, v kateremu mi v trenutku bolj zapaše.

[mytja]

NEW AMAZING UPDATE!!!

Proton now even normalizes the timetable. Hole patching is WIP currently. I've also implemented many security features, that will make sure my algorithm isn't consuming too many system resources and is stuck in an infinite loop.

[mytja]

NEW UPDATE

Proton zdaj tudi polni luknje.

Imamo pa tudi lepo animacijo za čakanje med tem dolgotrajnim postopkom.

Vse, kar še moram narediti so blok ure in predure/poure, nato pa še veliko testiranja z dvema oz. večimi razredi. Bom kar še enkrat napisal tukaj:

• Predure in poure (za izbirne predmete)
• Polure (ena ura na dva tedna)
• Upoštevaj počitnice
• Testiranje z dvemi ali večimi razredi
• Izboljšaj UI za več razredov
• Dodaj možnost za uporabo tega ustvarjenega urnika
• Izbriši proton pravilo

[mytja]

No, pa smo vendarle tukaj. Proton upošteva čisto vsa pravila in ustvari ta lep urnik:

Ker temeljimo na naključnemu algoritmu, ki zagotovi popolno naključnost vsakič, ko pritisnete na "Ponovno generiraj urnik", je časovni razpon sestavljanja urnika vse od pol sekunde pa do desetih sekund (sicer bolj redko, a se vendarle dogaja) za en razred.

Sedaj bom začel testirati z dvema razredoma in pa dodal večtedenski pogled in posledično tudi polure.

[mytja]

No, to je bilo lažje kot sem mislil...

[mytja]

NEW INSANE UPDATE!!!

1. Na novo napisani algoritmi za post-procesiranje urnika

Stari algoritmi za post-procesiranje so bili zelo slabo narejeni in so tipično potrebovali več kot eno minuto, da rešijo vse luknje (za samo en razred), pa še teh včasih niso. Prav tako (kot lahko vidite iz prejšnjega komentarja), ni nevtralizacija urnika delovala dosti dobro (na petek so imeli samo dve šolski uri (ignorirajmo NI3 - izbirni predmet nemščina), medtem ko so imeli na torek SEDEM šolskih ur). Zdaj so te algoritmi veliko bolj učinkoviti, hitrejši (navadno potrebujejo manj kot 5 sekund (sicer na relativno novemu Ryzen 5 5500U) za tri razrede), kot tudi bolje zapolnijo urnik, kot lahko vidite iz spodnjih screenshotov.

Urnik za 9.b

Urnik za 9.a

Urnik za 9.c

2. Razne minimalne izboljšave v glavnem algoritmu za sestavljanje urnika

Kot verjetno že veste, je moj algoritem za sestavljanje urnika popolnoma naključen. Tako lahko garantiramo, da vsakič, ko kliknem "Ponovno generiraj urnik", se bo sestavil nov, drugačen in popolnoma naključen urnik. To omogoča, da imajo na šoli več izbire, a hkrati pride z negativnimi lastnostmi... urnik se zelo dolgo sestavlja. Izmeril sem že vse od 15 sekund, pa vse do 4 minut (kar naj bi bil maksimum) za tri razrede. Povprečje je okoli dveh minut. Vse je odvisno od seeda, ki ga dobi generator pseudo-naključnih števil (kriptografsko nenaključen generator, ki je veliko hitrejši od kriptografsko naključnega/varnega generatorja), kar pomeni, da je lahko trajanje sestavljanje urnika zelo naključno - lahko dobi pravi seed že v prvo, lahko ga pa dobi šele v desetem poskusu ipd.

Sestavil sem to tabelo s časi sestavljanja urnika

	Najmanjši/največji/povprečni izmerjen čas sestavljanja urnika pred optimizacijami	Najmanjši/največji/povprečni izmerjen čas sestavljanja urnika po optimizacijah
En razred	5s/20s/15s	3s/17s/10s
Dva razreda	20s/120s/60s	10s/95s/40s
Trije razredi	60s/600s/400s	15s/300s/120s

3. UI za več razredov

Kot lahko vidite na prejšnjih screenshotih, sem dodal UI za izbiro specifičnega razreda.

Kaj nam še ostane?

Izgleda, da bo Proton prej prišel na sceno, kot pričakovano. Proton bo ostal kar nekaj časa kot beta funkcija in bom z veseljem sprejemal kakršnekoli predloge in pripombe, za zdaj pa nam ostane samo še tole:

• Upoštevaj počitnice
• Dodaj možnost za uporabo tega ustvarjenega urnika
• Izbriši proton pravilo

PS. Skril sem vse prejšnje komentarje, zaradi boljše vidljivosti. Še vedno so vidni, a jih je treba ročno razširiti.

[mytja]

Bolj ali manj končano, samo še mali popravki in bom vse lahko pushal (ne še danes)

[mytja]

Vem, da sem to rekel že pred desetimi dnevi, ampak zdaj je Proton končan zares. Imel sem malo težav s post-procesirnim algoritmom, a sem to odpravil. To pomeni, da bo Proton objavljen do konca tega tedna (če se ne bo SPET kaj zalomilo) z vsemi drugimi novimi funkcijami.

V tem trenutku izvajam benchmarke in zadnje teste.

[mytja]

UPDATE: Takoj, ko izgleda vse dobro, gre vse po zlu... Upam, da bom to lahko čim prej odpravil in se čim prej premaknil iz Protona na sistem...

[mytja]

KONEC!

Po vsem trdem delu, se je vse vendarle izšlo. Proton bo izšel DANES.

Medtem ko čakate, pa si lahko ogledati naslednji benchmark za Proton layer

Pravila, uporabljena pri generaciji urnikov

Razredi, v benchmarku

• 9.b
• 9.a
• 9.c

Benchmark

Časi zahtevkov so pobrani iz razvijalskih orodij Firefox brskalnika.

Ranking je ocenjen ročno - urnikov ni ocenjeval program/stroj, temveč človek (razvijalec MeetPlan sistema) po svoji (subjektivni) lestvici. Ta lestvica ni pod nobenim pogojem standardizirana.

Vsi ranki pod (vključno z) 5 avtomatično pomenijo neuporabne urnike

1. 46.54s - ranking 10/10 - ročnih post procesiranj: 0
   Komentar: Odličen urnik
2. 2.22min - ranking 3/10 (NEUPORABEN) - ročnih post procesiranj: 2
   Komentar: naštetih 5 nepopravljivih lukenj, od tega ena nepopravljiva, katero bi se dalo popraviti s premikanjem na druge dneve - ostale nepopravljive ure so enostavno nepopravljive, razen če zmešamo na novo celoten urnik. Urnik bi sicer lahko bil slabši, verjamem da bi ga z ročnim post procesiranjem spravili na še višjo oceno, ampak nikoli do uporabnega stanja
3. 25.86s - ranking 8.5/10 - ročnih post procesiranj: 0
   Komentar: Urnik je dober, lahko bi bile sicer ure malo bolj razpršene, ampak popolnoma uporaben urnik
4. 28.73s - začeten ranking 8/10 (po ročnih post procesiranjih 9/10) - ročnih post procesiranj: 2
   Komentar: Urnik je dober, nenormalne ure bi bile sicer lahko malo bolj razpršene, drugače pa uporaben. Po ročnemu post procesiranju je urnik zelo dober, le še malo bi se ga dalo "zgladiti" in urediti blok ure (pri predmetih v skupinah predmetov, npr. matematiki)
5. 6.72min - ranking 5/10 - ročnih post procesiranj: 2
   Komentar: našteti dve nepopravljivi luknji - eno bi se dalo popraviti s premikanjem na druge dneve (kar je dokaj enostavno popraviti), drugo pa se bi dalo popraviti z menjavanjem normalnih ur
6. 2.21min - ranking 9/10 - ročnih post procesiranj: 0
   Komentar: Kot že večkrat omenjeno, bi lahko bile ure malo bolj razpršene. To nameravam odpraviti kasneje z ročno določitvijo maksimalnega števila ur. Urnik je drugače zelo dobro sestavljen.
7. 15.40s (ne hecam se...) - ranking 9.5/10 (po post procesiranjih 10/10) - ročnih post procesiranj: 2
   Komentar: Ure so dokaj enakomerno razpršene, le blok ure bi bilo (kot že večkrat omenjeno) treba malo razpršiti čez vse dni.
8. 2.26min - ranking 8/10 (po ročnemu post procesiranju 7/10, a najverjetneje neuporaben) - ročnih post procesiranj: 0
   Komentar: Izbirni predmeti so neenakomerno prerazporejeni, do te točke, ko imajo učenci 8 šolskih ur, zaradi dveh zaporednih izbirnih predmetov. Da ne omenjam, da učenci, ki nimajo 1. izbirnega predmeta (NRA) imajo luknjo, če čakajo na 2. izbirni predmet, nemščino (NI3). Po ročnemu post procesiranju se ustvari nepopravljiva luknja.
9. 1.26min - ranking 10/10 - ročnih post procesiranj: 0
   Komentar: Ničesar nimam za dodati - zelo lep urnik, brez lukenj in z dokaj enakomerno porazdelitvijo učnih ur
10. 1.50min - ranking 9/10, najverjetneje neuporaben (po ročnih post procesiranjih 10/10) - ročnih post procesiranj: 4
    Komentar: Urnik je bil dokaj slab na začetku, z eno luknjo, katero pa smo lahko odpravili z ročnim post procesiranjem. Sestava urnika je odlična, z dokaj lepo razporejenimi urami.

Strnjeni rezultati

Povprečna ocena (štejejo se boljše ocene): 8.1
Povprečna ocena (štejejo se slabše ocene): 7.9
Povprečna ocena: 8.0

Povprečen čas, potreben za sestavo urnika (ni upoštevan čas za ročno post procesiranje):
46.54+133.2+25.86+28.73+403.2+132.6+15.4+135.6+75.6+90 = 1086.73
1086.73/10 = 108.673
108.673/60 = 1.8 minute

10. sestava urnika