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 Jean B . Évalué à 1.
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 David FRANCOIS (site web personnel) . Évalué à 1.
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 Kerro . Évalué à 2.
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 David FRANCOIS (site web personnel) . Évalué à 1.
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 Mathias Bavay (site web personnel) . Évalué à 3.
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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.