[Algorithmie] Cron et Calendrier

[InstinctHack]

Salut,

Je suis face à un problème auquel je pense pas qu'il y ai de réponse, mais dans le doute, si quelque chose m'aurais échapper, je viens poser la question.

Considérons un ensemble d'évènements A et de longeur B, à chacun des termes est associé une règle similaire à ceux utilisé par cron.
Ainsi qu'un ensemble de jours de longueur C.

C = 365
B = [0,50000]

La problématique est la suivante : comment générer la totalité des match des évènements, et cela avec le moins de ressource CPU possible ?

Mon idée d'algo était de prendre un jour, et de parcourir les events et ainsi d'obtenir les évènements survenu ce jour là. Ca marche, mais c'est gourmand si on essaye de récuperer ceux de tout le mois par exemple...
Alors je pensais prendre le problème à l'envers, et parcourir les évènements pour obtenir les jours où la règle se vérifieras.
Problème résolu ? Pas sûr...
Si le nombre d'évènement est de l'ordre de la dizaine de milliers, cela prendrait énormement de ram pour toutes les possibilités existantes...

Dans le pire des cas, je passerais pas un système de cache, mais je trouvais la question intéressante.

Qu'en pensez-vous ?

[gruik]

j'ai rien compris, mais t'as l'air de maîtriser ton sujet
(donc la longueur B vaut [0,50000] c'est ca ?)

[Machin]

Je ne suis pas bien sûrs d'avoir bien compris. Si je résume tu as un ensemble de tâche, type cron, qui se déclenche à intervalle régulier et durent une certains temps. Et tu cherche à trouver de manière systématique quand plusieurs sont déclenchées en même temps, c'est ça ?

Si tu as N événements, a vu de nez, tu va avoir N*(N-1)/2 combinaisons de 2 événements à tester. Je considère que c'est suffisant. Si tu test E1 avec E2 tu dois être capable de sortir une info type "ils se croisent tous les M jours pendant J heures décallé de H heures". Avec ce genre d'infos + tous les autres croisements de E2 tu peux affiner le modèle pour détecter les croisements à 3, 4....

Bref ça te fais une sacré combinaison. De ce fait, ce serait cool que tu nous précise un peu dans quel cadre tu va l'utiliser. Quel info t'interesse ? Comment va tu l'utiliser ?

Car si le but est "juste" de trouver quand ou si il y a plus de K croisements, on peut se permettre des simplifications. Si ton but est de tracer le nombre d'événements chaques jours aussi, etc.

[InstinctHack]

@gruik ouep, c'est ça

@Machin, non, non c'est plus simple que ça quand même
L'application serais un agenda accesible via une api et je coderais une interface web par-dessus.
Je te passe les autres spécificités du truc (groups, block-life, etc...)

Voilà à quoi pourrais ressembler le fichier d'évènements public :

Code :

** 01 01 Jour de l'an
** 01 02 Basile
** 01 03 Geneviève
** 01 04 Odilon
** 01 05 Edouard
** 01 06 Mélaine
** 01 07 Raymond
** 01 08 Lucien
** 01 09 Alix
** 01 10 Guillaume
** 01 11 Pauline
** 01 12 Tatiana
** 01 13 Yvette
** 01 14 Nina
** 01 15 Rémi
.....

(Les étoiles ont la même signification que dans les règles cron.)
mais on peux imaginer des règles similaires à celles-ci :

Code :

** ** /7 dimanche

Et à partir de ça, je voudrais faire la listes des évènements de l'année toute entière, il peux donc y avoir plusieurs évènements par jour (jour == la plus petite unité de temps dans mon programme pour le moment)
Et c'est là que je suis pas sûr de la qualité de mon algo :

Mon idée d'algo était de prendre un jour, et de parcourir les events et ainsi d'obtenir les évènements survenu ce jour là. Ca marche, mais c'est gourmand si on essaye de récuperer ceux de tout le mois par exemple...
Alors je pensais prendre le problème à l'envers, et parcourir les évènements pour obtenir les jours où la règle se vérifieras.

[b0fh]

Yop,

Soit n le nombre de dates dans la plage que tu veux sortir, et m le nombre d'évènements.

Tes deux algorithmes sont en O(nm), ce qui n'est pas fantastique.

Je te propose d'utiliser un tas, une structure de données qui permet d'obtenir en O(1) le plus petit élément d'une collection, et en O(log n) d'insérer un élément dans la collection.

Dans le tas, nous allons stocker une structure qui contient deux choses: la date de la première occurrence de l'évènement (qui sert de clef pour le tas), et le descripteur de l'évènement.

Pour générer dans l'ordre les évènements, il suffit alors de:
- prendre l'élément minimum du tas, qui sera le prochain évènement (O(1))
- émettre l'évènement sur la sortie (O(1))
- calculer la date suivante à laquelle l'évènement arrive (O(1))
- et réinsérer la structure dans le tas (O(log m))

On arrive donc à une complexité en O(m log m), ce qui est très nettement mieux pour un grand nombre d'évènements, et encore plus quand la plage d'évènements (n) est large !