Forum Programmation.ruby Algorithmes calculs de date

Posté par (page perso) .
Tags : aucun
0
25
juil.
2010

Bonjour !



je cherche un algo efficace pour compter le nombre de jours ouvrés/ouvrables compris dans une plage de dates, la différence entre deux dates arbitraires est visiblement très rapide.



Ca me permet d'obtenir facilement le nombre de jours calendaires, par contre j'aimerais bien retrouver l'algo qui est derrière pour pouvoir faire la même chose en enlevant les dimanches, samedis, et éventuellement des jours féries/chômés/d'absence pour faire des calculs de paie.



Je me suis dit que je pourrais me baser éventuellement sur les numéros de semaine, mais ca commence à se corser quand je commence à faire des calculs sur plusieurs années.



pour l'instant j'en suis réduit à :


# Paramètre : les numéros de jours à exclure du décompte

def count_days_in_timespan(days=[])
# Méthode ultra-bourrin mais qui a le mérite de marcher à tous les coups
# TODO : A refactorer baby
count = 0
day = @starts_on

while day <= @ends_on do
count += 1 if days.include? day.cwday
day = day.advance :days => 1
end

count
end


honte à moi, donc voila, je me demande s'il y a pas un algo bien connu qui fasse ca et qui se serait caché de moi pendant mes recherches guggle...



Merci à vous !

  • # Date#upto

    Posté par . Évalué à 1.

    Si tu as vraiment besoin de perf sur cet algo et que tu compte l'utiliser sur des périodes longues ma méthode 'est certainement pas la bonne. Il est certainement possible d'écrire une "formule" pour calculer ça seulement avec les années bissextiles et compagnie ça risque d'être illisible, complexe à débugger et à améliorer si tu veux ajouter le support des jours fériés.

    Ma solution est donc dans le style de la tienne, mais en plus rubyique:


    def workday?(date)
    1 <= date.wday <= 5
    end

    workday_count_between(start_date, end_date)
    count = 0
    start_date.upto(end_date) do |date|
    count += 1 if workday?(date)
    end
    count
    end



    Si le mode de calcul change souvent tu peux aussi passer un block.
    NB: je l'ai écrite comme ça à l'arrache sans l'éxecuter, dsl pour les éventuelles erreurs
    • [^] # Re: Date#upto

      Posté par (page perso) . Évalué à 1.

      Merci pour ta réponse !
      Ce qui m'embête dans ces deux manières c'est la boucle...

      Si je me trompe pas les deux manières sont o(n) et ce que je recherche c'est la solution pour avoir un algo o(1)

      Je pense que la solution la plus performante ce serait d'utiliser cette méthode pour le début et la fin de l'intervalle et utiliser Date#- pour se baser sur le nombre de semaines entières contenues dans l'intervalle et multiplier par le nombre de numéros de jours qu'on souhaite supprimer.

      Pour ce qui est d'enlever les jours fériés il suffirait de passer un Array de dates de jours fériés et pour chacune d'elles vérifier si elle se trouve ou non dans l'intervalle ce qui est plutôt performant je pense puisque c'est basé sur Date#<=>
      • [^] # Re: Date#upto

        Posté par (page perso) . Évalué à 2.

        ce que je recherche c'est la solution pour avoir un algo o(1)
        Il n'est pas possible d'avoir un algorithme en o(1) ou o(xxx) sans table, puisqu'il n'y a pas de formule pour connaître les jours ouvrables. Certains jours fériés sont décidés plus ou moins arbitrairement d'une année sur l'autre, les règles changent, etc. Et puis ce n'est pas transposable à un autre pays, donc on constate que ce n'est pas la bonne solution.

        Une solution est d'avoir une table contenant uniquement les jours fériés (hors samedis-dimanches).
        Pour effectuer ton calcul, tu calcules d'abord la différence entre tes dates, puis tu supprimes les samedis-dimanches (deux par semaine, puis il faut gérer les extrémités), puis tu supprimes les jours fériés en regardant dans ta table.
        On est presque sur du o(1), mais pas tout à fait.

        Il reste que la méthode la plus rapide que je connaisse est d'avoir une table qui contient le nombre de jours pré-calculé depuis une date. Par exemple depuis le 1er janvier 2010 jusqu'au 31 décembre 2020. Chaque ligne de la table contient le cumul des jours ouvrés (ou non-ouvrés, comme on veut) depuis le début de la table.
        La première ligne contient 1, la seconde contient 2, la troisième aussi car c'est un samedi, idem pour la cinquième, etc. On arrive à la fin de la table avec une valeur du genre 2500.
        Ca fait 6 ko. Le nombre de jours ouvrés entre deux dates se calcule par la simple différence entre les deux lignes de la table. C'est du o(1). Ca prend de la place, et ça reporte les bugs ailleurs.
        • [^] # Re: Date#upto

          Posté par (page perso) . Évalué à 1.

          Yes.

          En fait quand je dis jours ouvrés/ouvrables c'est effectivement un abus de langage.

          Pour l'instant je simplifie le problème en posant les jours ouvrés du lundi au vendredi inclus et ouvrables du lundi au samedi inclus.

          Mais sinon, en effet, la solution qui se rapprocherait le plus du o(1) serait :
          - Comptage avec boucle pour les extrémités si elles ne tombent pas respectivement lundi et dimanche (14 tours de boucle max grosso modo)
          - Calcul du nombre de semaines entières (division ~ o(1))
          - Multiplication par le nombre de jours de la semaine à exclure, soustraction


          Bon, ben je pense que je vais commencer par coder un petit paquet de tests unitaires histoire de pas me retrouver avec une méthode performante mais inexacte :p
  • # En passant par les julian dates...

    Posté par (page perso) . Évalué à 3.

    C'est un peu différent, mais cela marchera bien pour ton cas: j'ai des implémentation d'algo standards pour le calcul de "julian date", c'est à dire de nombre de jours depuis une date de référence (en l'occurance, 1er janvier -4713). Donc tu calcul le julian date du premier dimanche suivant ta date de départ, puis le dernier dimanche avant ta date d'arrivée, tu divise cela par 7 et tu as le nombre de semaines (donc de jours ouvrés) plus les offsets du départ et de l'arrivée.

    L'algo:

    long Date::getJulianDayNumber(const int& _year, const int& _month, const int& _day) const
    622 { //given year, month, day, calculate the matching julian day
    623 //see Fliegel, H. F. and van Flandern, T. C. 1968. Letters to the editor: a machine algorithm for processing calendar dates. Commun. ACM 11, 10 (Oct. 1968), 657. DOI= http://doi.acm.org/10.1145/364096.364097
    624 const long lmonth = (long) _month, lday = (long) _day;
    625 long lyear = (long) _year;
    626
    627 // Correct for BC years -> astronomical year, that is from year -1 to year 0
    628 if ( lyear < 0 ) {
    629 lyear++;
    630 }
    631
    632 const long jdn = lday - 32075L +
    633 1461L * ( lyear + 4800L + ( lmonth - 14L ) / 12L ) / 4L +
    634 367L * ( lmonth - 2L - ( lmonth - 14L ) / 12L * 12L ) / 12L -
    635 3L * ( ( lyear + 4900L + ( lmonth - 14L ) / 12L ) / 100L ) / 4L;
    636
    637 return jdn;
    638 }


    Pour plus de détails, regarde dans mes sources:
    https://slfsmm.indefero.net/p/meteoio/source/tree/HEAD/trunk(...)
    (il y a aussi la méthode inverse, à partir d'une julian date trouver jours, mois, annés)

    Mathias

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.