Iskanje naslednje ponovitve - najboljši algoritem

Lahko malo bolj podrobno opišeš ?

Tule je pa koda, ki preveri če se "dogodek zgodi sedaj", če koga zanima...

define('SCH_ORD_MIN',   0);
define('SCH_ORD_HOUR',  1);
define('SCH_ORD_MDAY',  2);
define('SCH_ORD_MON',   3);
define('SCH_ORD_WDAY',  4);

define('SCH_INFO_MIN', 0);
define('SCH_INFO_MAX', 1);
define('SCH_INFO_LTR', 2);

class Recurrence {
  var $info = array(
    SCH_ORD_MIN  => array(0, 59, 'i'),
    SCH_ORD_HOUR => array(0, 59, 'G'),
    SCH_ORD_MDAY => array(1, 31, 'j'),
    SCH_ORD_MON  => array(1, 12, 'n'),
    SCH_ORD_WDAY => array(0,  6, 'w'),
  );

  var $aliases = array(
    '@daily'   => '0 0 * * *', // Every midnight
    '@weekly'  => '0 0 * * 0', // Every sunday at midnight
    '@hourly'  => '0 * * * *', // Every full hour
    '@monthly' => '0 0 1 * *', // First day of every month at midnight
  );

  function Process($rec_rule) {
    if ( isset($this->aliases[$rec_rule]) ) {
      $rec_rule = $this->aliases[$rec_rule];
    }

    $ord = preg_split('/[\s]+/', $rec_rule);

    $time = time();
    for( $o = 0; $o < count($ord); $o++ ) {
      if ( !$this->_ProcessPart($time, $o, $ord[$o]) ) {
        return false;
      }
    }

    return true;
  }

  function _ProcessPart($time, $type, $input) {
    if ( '*' == $input ) {
      // Event se lahko izvrši kadarkoli (za ta tip)
      return true;
    }

    $ct = (int)date($this->info[$type][SCH_INFO_LTR], $time);

    if ( is_numeric($input) ) {
      // Event se zgodi samo ob določenem času,
      // če je podatek enak trenutnemu času vrnemo true
      return ($input == $ct);
    }

    if ( false !== strpos($input, '/') ) {
      list($range, $div) = explode('/', $input);

      if ( !is_numeric($div) && 0 < (int)$div ) {
        // Delitelj mora biti obvezno število večje od 0
        return false;
      }

      if ( '*' == $range || $this->_ProcessRange($time, $type, $range) ) {
        // Če je razpon enak '*' (whenever) ali pa trenutna vredno pade
        // znotraj razpona gremo gledat če je ostanek ok.
        return (0 == $ct % (int)$div);
      }
    }

    // Zadnja možnost, ki nam ostane: podatek ki je vpisan je razpon
    return $this->_ProcessRange($time, $type, $input);
  }

  function _ProcessRange($time, $type, $input) {
    $input_parts = ( false === strpos($input, ',') ? array($input) : explode(',', $input));

    $ct = (int)date($this->info[$type][SCH_INFO_LTR], $time);

    for ( $i = 0; $i < count($input_parts); $i++ ) {
      if ($ct == $input_parts[$i] ) {
        return true;
      }
      elseif ( false !== strpos($input_parts[$i], '-') ) {
        list($min, $max) = explode('-', $input_parts[$i]);
        if (RANGE_OK === Validation::InRange($ct, $min, $max)) {
          return true;
        }
      }
    }

    return false;
  }
}

hash tabelo česa?

hm ... mau pocak!

Računanje bi mogoče pohitrilo naslednje načelo:

Za dogodke, ki so v bližnji prihodnosti uporabiš natančnost do minute, za bolj oddaljene ure za še bolj oddaljene dneve ali celo mesece.

Saj je za dogodek ki se bo zgodil čez devet mesecev nepotrebno že sedaj računati ure in minute...

Sicer pa je to odvisno tudi od aplikacije ki ta podatek potrebuje.


-------------------------------

In še moje razmišljanje:

Zapis * * * * * bi lahko zapisal kot 0-59 0-23 0-31 1-12 0-6


Recimo da je trenutni čas 22. avgust 2004 23:45 In primer zapisa v cron:

35 9 25 5 * - program se proži vsakega 25. maja ob 9:35 neglede na dan v tednu

sedaj izračunamo čez koliko časa bo to

1) minute
čez koliko minut = 60-45+35 = 50 minut modus 60 = 50 minut

2) ure
čez koliko ur = 24-23+9 = 10 ur modus 24 = 10 ur

3) dnevi
čez koliko dni = 31-22+25 = 34 modus 31 = 3 dni

4) meseci
čez koliko mesecev = 12-8+5=9 modus 12 = 9 mesecev


se pravi ta dogodek se bo zgodil: čez 9 mesecev, 3 dni, 10 ur in 50 minut toda kateri datum je to ?
Lahko bi poenostavil in rekel: 9*31*24*60+3*24*60+10*60+50= 406730 minut, toda ta razultat ima veliko napako 6 dni in 6 minut. (vsi meseci nimajo 31 dni)

Če ti ta natančnost ne zadošča uporabi časovne funkcije. Mysql ima že vgrajeno now() + interval x enot, pri čemer so lahko enote second, minute, hour, day, month, year

mysql funkcija izračuna, da se bo program naslednjihč sporožil 26.5.2005 ob 10.35. Torej je napaka 1 uro. Ne vem zakaj.

select (((('2004-08-22 23:45:00'+interval 9 month) + interval 2 day)+interval 10 hour ) + interval 50 minute) as datum;
vrne "2005-05-26 10:35:00"


Sicer bi pa moral rešiti tudi druge vrste dovoljenih zapisov v cron kot npr.
2,5,15-40 */3 2-28/2 * 0,1,2
vendar ne vem, kako bi to naredil.

@CCfly -- problem nima veze z dejanskim cronom, od tam sem si sposodil le format zapisa intervala. Vse kar želim ugotoviti je naslednja ponovitev...

@frke -- bolj preprosto je da rezultat pomnožiš še z 60 - dobiš sekunde in uporabiš funkcijo date ki ti vrne direktno datum, upoštevajoč dneve v mesecu, prestopna leta ipd

za enkrat delam to tako, da napolnim 5 arrayev z možnimi vrednostmi -- če ima enota (minute, ure, meseci...) predpisano eno številko ima array samo en element, če imamo vpisano * ima element vse možne vrednosti ki jih ta enota obsega (0-59, 1-31 ... )
Tako dobim sezname vseh možnih vrednosti.

Ugotovil sem tudi da bi bilo najbolj pametno računat po tem vrstnem redu:
- meseci
- dnevi v mesecu
- dnevi v tednu
- ure
- minute

zaplete se predvsem pri dnevih v tednu (mogoče se že predolgo ukvarjam z problemom pa ne vidim preproste rešitve??)

sej ni važno... nekej kar se pač zgodi na določen interval

CCfly... mislim da se ne razumeva...

Imam podatek o intervalu: 0 0 */2 * * (Nekaj kar se izvrši vsak drug dan ob polnoči)
Sedaj pa potrebujem točen datum in uro kdaj se bo to naslednjič zgodilo.

Je današnji mesec že taprav?

Če ni, ga toliko časa povečuješ za 1, dokler ne zadosti pogoju.



Je današnji dan v mesecu že taprav?

Če ni, ga toliko časa povečuješ za 1, dokler ne zadosti pogoju. Hkrati po potrebi updataš mesec in kontroliraš pogoj meseca. Če pogoj meseca ne klapa, nadaljuješ na vrhu, pri naraščanju meseca.

Če sta mesec in dan v mesecu OK, prekontroliraš dan v tednu. vrneš se na mesec ali dan v mesecu update. Na more significant (mesec je more dignificant) če sta oba narobe. Sicer na napačnega.

Je sedanja ura že taprava? (updataš more signifikant enote in kontroliraš, če se spremenijo, ter se vrneš na most significant časovno enoto.)

Če ni, jo toliko časa povečuješ za 1, dokler ne zadosti pogoju.



Je sedanja minuta že taprava? (updataš)

Če ni, jo toliko časa povečuješ za 1, dokler ne zadosti pogoju.



Je sedanja sekunda že taprava? (updataš)

Če ni, jo toliko časa povečuješ za 1, dokler ne zadosti pogoju.

Če si prišel sem, si našel.

Ja. Najprej naštelaš most significant podatek ... potem pa vse manj.

Ampak moraš pa pri spremembi dneva kontrolirat spremembo meseca. Pri spremembi ure, spremebo vseh bolj signifikant.

Tako ti zadeva prileze sama na tisti dan in uro.

Bom jest dal tole v Critticall, kokr hitro sprovedem ene par drugih obdelav.

Zaenkrat mislim, da se ti dan v tednu splača vodit samo kod mod 7 absolutne številke dneva.

No, bom. Do jutri do 7:00 morm neki narest ... pod večer jutri.

Imam podatek o intervalu: 0 0 */2 * * (Nekaj kar se izvrši vsak drug dan ob polnoči)
Sedaj pa potrebujem točen datum in uro kdaj se bo to naslednjič zgodilo.

Aja zdaj štekam kaj si hotel narediti. Jaz sem mislil da iščeš po seznamu dogodkov.

bounce.

Thomas, si kaj stuhtal?

xbite, men se na prvi pogled zdi, da je problem zelo trivialen in bi se ga moralo dati resiti v 0-time.

Naj premislim, dobis reply.

> men se na prvi pogled zdi, da je problem zelo trivialen in bi se ga moralo dati resiti v 0-time.

Ne, ni tako trivialen, sploh ne!

Ja.. sej štima vse... če pogledaš prvi post - "minuta, ura, dan v mesecu, mesec in dan v tednu"

oziroma da zabetoniramo da ne bo dvoumno - [minute] [ure] [dnevi v mesecu] [meseci] [dnevi v tednu]

0 0 27 8 *

Torej.. včerajšnji dan...
čez 1 dan manj kot eno leto se bo zgodil...

Bisekcija je bistveno hitrejsa od Thomasovega predloga "obracanja kolesc", ampak v tvojem primeru (z malo predpriprave podatkov) je dejansko mozno naredit resitev O(log n) ali boljso.

Googlaj za "temporal distance" algorithm ali kaj podobnega, sicer pa ti lahko napisem resitev, ko bom imel kaj casa.

Ce pa poves, kaj dejansko pocnes, ti pa mogoce lahko svetujemo tudi kako drugo resitev, ki bolje resi tvoj originalni problem.

ps: predvidevam da je pri dnevih v tednu 0 nedelja, 1 ponedeljek, etc, do 6 sobota.

jype: Procedura je taka:

V funkcijo das datum in masko. Ven dobis najbolj zgodnji datum, ki je vecji od vhodnega datuma, ki ustreza maski.

O(0) je napačno razmišljanje, imho.

Če sem pravilno razumel problem potem je ena enostavna rešitev tole.
Pretvoriš vsak datum v minute (če imaš minutno natančnost) in potem iščeš najmanjši večji datum od določenega datuma.
Funkcija za pretvorbo datuma v minute je easy, edino relativno počasen algoritem je.
LP

cman, xbite je to ze naredil, stvar dela katastrofalno.

Kava, potem pa predstavim svojo grdo (a delujoco) kodo.

import java.util.Date;

public class CronComputation 
{
	private static final long oneMin = 60*1000;
	private static final long oneHr  = 60*60*1000;
	private static final long oneDay = 24*60*60*1000;
	private static final long oneWk  = 7*24*60*60*1000;
	
	/*
	 * Usage: java CronComputation minutes hours dayInMonth month dayInWeek 
	 */
 
	public static void main(String[] args) 
	{
		Date now = new Date();
		
		String min = args[0];
		String hrs = args[1];
		String dim = args[2];
		String mnt = args[3];
		String diw = args[4];
		
		//TODO implement problem division (complex argument passing)
		long l1 = System.currentTimeMillis();
		
		System.out.println("Maska: " + 
					min + " " + 
					hrs + " " + 
					dim + " " + 
					mnt + " " + 
					diw);
							
		System.out.println("Trenutni cas: " 
					       + now.toString());
		System.out.println("Izvedba ob: " + calcNumeric (min, 
								 hrs, 
								 dim, 
								 mnt,
								 diw, 
								 now).toString());		
		
		long l2 = System.currentTimeMillis();
		
		System.out.println("Izvajanje: " + 
				    String.valueOf(l2-l1) + 
			  	    " ms");
	}


	private static Date calcNumeric(String min, 
				    String hrs, 
				    String dim, 
				    String mnt, 
				    String diw, 
				    Date now) 
	{		
		Date following = new Date(new Date(now.getYear(), 
				           now.getMonth(), 
				           now.getDate(), 
				           now.getHours(), 
				           now.getMinutes())
				          .getTime() + 60*1000);		
		
		if (!min.equals("e"))
		{		
			following = new Date(following.getYear(), 
					     following.getMonth(), 
					     following.getDate(), 
					     following.getHours(), 
					     Integer.parseInt(min));
							     
			if (following.getTime() < now.getTime()) 
			    following = new Date(following.getTime() + oneHr); 		
		}
		
		if (!hrs.equals("e"))
		{
			following = new Date(following.getYear(), 
					 following.getMonth(), 
					 following.getDate(), 
					 Integer.parseInt(hrs), 
					 (min.equals("e")) ? 0 : following.getMinutes());
			if (following.getTime() < now.getTime()) 
			    following = new Date(following.getTime() + oneDay); 					
		}
		
		if (!dim.equals("e"))
		{
			following = new Date(following.getYear(), 
					 following.getMonth(), 
					 Integer.parseInt(dim), 
					 (hrs.equals("e")) ? 0 : following.getHours(),
					 (min.equals("e")) ? 0 : following.getMinutes());
			
			if (following.getTime() < now.getTime())
			{
				following = new Date(following.getTime() + oneDay);				
				while (following.getDate() != Integer.parseInt(dim)) 
				{
					following = new Date(following.getTime() + oneDay);
				} 		
			}						
		}
		
		if (!mnt.equals("e"))
		{
			following = new Date(following.getYear(), 
					 Integer.parseInt(mnt)-1,
					 (dim.equals("e")) ? 1 : following.getDate(), 
					 (hrs.equals("e")) ? 0 : following.getHours(),
					 (min.equals("e")) ? 0 : following.getMinutes());
								 
			if (following.getTime() < now.getTime())
			{
				int rightDate = following.getDate();
				int rightYear = following.getYear()+1;
						
				while ((following.getMonth() != Integer.parseInt(mnt)-1) ||
				       (following.getDate() != rightDate) ||
				       (following.getYear() != rightYear)) 
				{
					following = new Date(following.getTime() + oneDay);
				} 						
			}			
		}
		
		if (!diw.equals("e"))
		{
			if (following.getDay() != Integer.parseInt(diw))
			{
			  following = new Date(following.getYear(),
			  					   following.getMonth(),
			  					   following.getDate());
			  following = new Date (following.getTime() + oneDay);			  
			  following = calcNumeric(min, 
			                          hrs, 
			                          dim, 
			                          mnt, 
			                          diw, 
			                          following);
			}
		}
		
		return following;
	}
}

Ce kdo ne razume, kako dobimo pravi 'dan v tednu':

Dobimo rezultat. Pregledamo ce ima pravi dan v tednu. Ce ne, rekurzivno klicemo isto funkcijo z istimi parametri, le da kot 'trenuten datum' podamo datum, ki smo ga izracunali, plus en dan, opolnoci.

Zadeva se 'rekurzivira' dokler ne dobi resitev s pravim dnevom v tednu. Dela be-pe, vsaj kolikor sem preiskusal.

Sergio... pocak sek.. grem javin kompajler instalirat :)


Aja... dejanski problem...
Imam tabelo dogodkov. Ne smem se zanest na to da se stvar izvjaja dejansko vsako minuto (v tem primeru bi samo preveril vsak vnos če se izvrši ta trenutek ali ne). Zato je treba izračunat za vsak vnos kdaj se naslednjič ponovi. In ko grem čez tabelo, pogledam tiste vnose ki imajo exec time manjši od trenutnega in jih izvršim.

Sergio, ful si ti posplošu tole :)