Iskanje naslednje ponovitve - najboljši algoritem

Posplošu? Na 0.2 sekunde sem spravil nekaj, kar tebi dela celo večnost.

Kaj točno sem posplošil?

xbite, ta program dela tocno in natancno to, kar si ti hotel. Ne vem, kaj ti manjka. Tebi je točno to 'preštevanje minutk' delalo težave. To, da si 'first-hit-occurence' računal predolgo.

Če pa meniš, da manjka to, da stvar iz (5-10/2) reče (od petih do desetih, vsaki 2 uri), je pa to ravno najbolj trivialen del programa, saj se sestoji le iz subdivizije problema na enakovredne podprobleme, nakar nad arrayem datumov rešitev izbereš najmanjšega.

Razen če si hotel nekaj drugega. Program pa dela tako kot mora.

Vedno sem mislil, da je v matematiki in posledično programiranju, problem posplošiti nekaj pozitivnega.

Samo da veš, da bova šla na pico enkrat v bližnji prihodnosti ;-)

Kaksn chat pa to. ;-)

/me se poboža po želodčku. ;-)

:>

anyhow... zadeva rešena... idejo sem si pa kar od Schedule::Cron::Events sposodil.

Jaz bi v tvojem primeru uporabil kopico in NE sklada, saj bi s tem izjemno pohitril findMin() [O(1)] in deleteMin() [O(log(n))]

[kar sta v bistvu najpogostejsi operaciji]

[ps, insertNode() naredis v O(log(n))]

Ja?

Hm, princip kopice najbrž poznaš. (Če ne, gugl jor frend :))

Ena najlepsih lastnosti je ta, da je minimalen element VEDNO na vrhu binarnega drevesa, in da operacije nad kopico to lastnost ohranjajo.

Dejstvo je tudi, da vedno rabis met dostopen samo najbolj zgoden dogodek. Ostali te, vsaj iz stalisca preferenc, ne zanimajo. Se.

Kaj potem naredis:

ko pride cas za izvedbo min elementa
deleteMin() in operacija, ki je s tem povezana

potem delas deleteMin() (do while min.time < currenttime) (za vsak slucaj ce je veliko operacij v kratkem casovnem obdobju, pac robni pogoj)

Potem si zapomnis cas, ko bos spet deleteMin()al

Sploh ne vidim komplikacije in potrebe po nadaljnjih optimizacijah (ker jih ni )

Hm... a veste katera resitev je najboljsa?

Tista, ki te najmanj kosta. Cesa? Tvojega casa, CPU casa in ostalih resourcev... Sendvici, ram, disk... ;)

Tisti ki najde pravo razmerje med temi komponentami zmaga.

Potem imas pa primere, ko se clovek trudi in matra na vse pretege in na koncu meseca ti pove, da je optimiziral neko akcijo, ki se izvede enkrat dnevno in bo sedaj namesto 10 sekund trajala 7.5 sekund ;)


"Tole bomo zmetal v eno razprseno tabelo!"
"Zakaj, ce je 150 elementov v seznamu, k se enkrat na dan preisce?"
"Ker bo hitrej!!!"


;) No, razen ce ti take stvari niso vsec in jih delas v prostem casu... ;)

Če se le da, je potrebno iskati najboljše rešitve. Sicer se bo ob vsakem problemu podobnega tipa uporabljalo slabo (počasno) rešitev. IMHO.

Praktično gledano, se najbolj splača vsak cron statement pretvoriti (sproti pretvarjati nanovo pridošle, ker taki venomer pritekajo) v pripadajoče evente do 2020.

Potem naj jih pa triga nek (obstoječ ali lasten) schedule programček.

OT, BW: Priden!