Prijavi se z GoogleID

» »

Iskanje naslednje ponovitve - najboljši algoritem

Iskanje naslednje ponovitve - najboljši algoritem

strani: 1 2 »

Sergio ::

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

Kaj točno sem posplošil?
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

darh ::

ravno najpomembnejše, malo več logike je v vsem skupej kot pa samo prištevanje minutk :)

Celo večnost pa traja brute-force :)
Excuses are useless! Results are priceless!

Sergio ::

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.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

BigWhale ::

Je kdo pogledal, kako je to narejeno v kaki implementaciji cron taba?

OwcA ::

Vedno sem mislil, da je v matematiki in posledično programiranju, problem posplošiti nekaj pozitivnega.
Otroška radovednost - gonilo napredka.

darh ::

BigWhale, sem ravno našel eno perlovo stvar - Schedule::Cron::Events

Sergio... ne se tko hitro zjezat no... je bil tisto bol joke. (hint - smile - hint)
Excuses are useless! Results are priceless!

Zgodovina sprememb…

  • spremenil: darh ()

Sergio ::

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

Kaksn chat pa to. ;-)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

darh ::

How could I say no :)
Excuses are useless! Results are priceless!

Sergio ::

/me se poboža po želodčku. ;-)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

CCfly ::

"One needs that slightly twisted perspective that comes with sleep deprivation
to make sense of CSS and HTML implementations in different browsers"
--Alexander Limi

Monkey see, monkey do...

No pa imamo odgovor in to brez pomanjkanja spanca..

darh ::

:>

anyhow... zadeva rešena... idejo sem si pa kar od Schedule::Cron::Events sposodil.
Excuses are useless! Results are priceless!

Thomas ::

Ja ... jest bi naredu tkole:

Vsakemu novemu recordu se izračuna, kdaj naj se predvaja. Rezultat se da na sklad in se izračuna minimalni čas iz sklada. Tega se namreč playa najprej (takrat) in ob tem še nevtralizira zapis, ko se ga predvaja.

Isto kot ob novem, se naredi ob playanem recordu!
Man muss immer generalisieren - Carl Jacobi

Sergio ::

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?
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

Hja, jest bi filozofiral še naprej.

Včasih sploh ne bi iskal minimuma, saj bi mi ga nova vrednost ne spremenila. Ker bi bila pač večja (=kasnejša) od tega minimuma (=najzgodnejšega naslednjega dogodka). To bi bilo celo ponavadi, tako pri vpisu, kot pri predvajanju!
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

Sergio ::

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 >:D)
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

Dam algoritem ki mi je prišel na misel. Nisem čisto prepričan, ampak se mi zdi, da ga ni še noben omenil v tejle temi. Zagotovo pa zahteva daleč najmanj računanja od vseh drugih omenjenih.

Ja?

Potem pride Sergio in mi pove, da naj sklad zamenjam s kopico. Vzamem zadevo za potencialno zanimivo izboljšavo in hočem diskutirati dalje.

Postavi me na trdna tla. Da je tako pač najbolje, da boljš se ne da, da naj uporabim Google če imam težave z znanjem ...

Halo! Dobro jutro!

;)
Man muss immer generalisieren - Carl Jacobi

BigWhale ::

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... ;)

Thomas ::

Pridiganje o (ne)zapravljanju časa (z optimizacijami) z internetnih forumov dol, je dokaj zabavno. Pridigajoči očitno časa ne zapravlja s kakšno optimizacijo, pač pa optimizira ravnanje drugih.

V prostem času. ;)
Man muss immer generalisieren - Carl Jacobi

kopernik ::

Č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.

Sergio ::

Thomas, jaz sem VEDNO za nadaljnje diskusije. Tisto o "optimizacijah ki jih ni", kar sem napisal, je seveda neresnica in cista provokacija, ki sem jo mislil kot salo.

Z veseljem diskutiram naprej. Resno.
Tako grem jaz, tako gre vsak, kdor čuti cilj v daljavi:
če usoda ustavi mu korak,
on se ji zoperstavi.

Thomas ::

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.
Man muss immer generalisieren - Carl Jacobi

Zgodovina sprememb…

  • spremenil: Thomas ()

BigWhale ::

Hm, tole zadnje sem tudi jaz razmisljal, da bi bilo najbrz se najbolj primerno. Tako imas samo en izracun tabele ob popravljanju/dodajanju cron jobov.

OT:
Thomas, moja 'optimizacija' je bila, da sem tukajle v eno kodo uvedel se eno string listo, kjer so shranjena imena serverjev. Sem 'optimiziral' tako, da sedaj program dela to kar so zeleli da dela... ;)
Je pa optimizacija casa drugih tudi precej pomembno opravilo... Samo ne moje... ;>

Thomas ::

OT, BW: Priden!
Man muss immer generalisieren - Carl Jacobi
strani: 1 2 »


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

[java] datumi

Oddelek: Programiranje
151280 (1153) l0g1t3ch
»

crontab - zagon vsake 3 tedne

Oddelek: Operacijski sistemi
8812 (659) kronik
»

[NALOGA][C] iskanje petkov 13

Oddelek: Programiranje
14956 (754) seawolf
»

SQL vprašanje

Oddelek: Izdelava spletišč
301865 (1428) jerneju
»

Koledar in ponavljajoči se dogodki

Oddelek: Programiranje
5559 (469) darh

Več podobnih tem