Simplify datetime calculation

Ideas
1

I’m surprised to see constructs such as return _DAYS_BEFORE_MONTH[month] + (month > 2 and _is_leap(year)) in python’s datetime routines.
But the calculation year-month-day ↔ days past a certain reference date can be done by simple integer arithmetic without any “if” conditional or whatever conditional in the calculation.
The only thing to do is a time shift to March 1st:

                       |   |   |   |   |
                       v   v   v   v   v
Mar,Apr,May,Jun,Jul:  31, 30, 31, 30, 31   ∑: 153 days
Aug,Sep,Oct,Nov,Dec:  31, 30, 31, 30, 31   ∑: 153 days
Jan,Feb:              31, rest             leap year day just added at end

So you see the logic behind the Gregorian calendar.

Then calculation can go this way: see gregorian/__init__.py at master · galuschka/gregorian · GitHub
year-month-day → days past March 1st 0 (don’t worry about non existence of year “0”)

    m3     = (month + 9) % 12   # 1,2 -> 10,11 / 3,4,..,12 -> 0..9
    y_corr = year - (m3 // 10)  # jan/feb: 1 year before y
    mar1st = y_corr * 365 + (y_corr//4) - (y_corr//100) + (y_corr//400)

    d153 = m3 // 5  # 153 days every 5 months
    m5   = m3 %  5
    d61  = m5 // 2  # 61 days every 2 months
    d31  = m5 %  2  # mar,may,jul etc.: 31 days
    days_past_mar1 = (d153 * 153) + (d61 * 61) + (d31 * 31) + day - 1

    return mar1st + days_past_mar1  # Mar 1st plus just arithmetic calculation

and inverse function: days → year-month-day:

    y400  =     days // self._DAYS400Y
    days -=     y400 *  self._DAYS400Y
    y100  = min(days // self._DAYS100Y,3)  # 0..3: 146096/36524==4! - every 4th century has 1 more day
    days -=     y100 *  self._DAYS100Y
    y4    =     days // self._DAYS4Y       # 0..24: (every century has one day less - 24 is max. anyway)
    days -=     y4   *  self._DAYS4Y
    y1    = min(days // self._DAYS1Y, 3)   # 0..3: 1460/365==4! - every 4th year has 1 more day
    days -=     y1   *  self._DAYS1Y       # days here: days past Mar 1st (0..365)

    y_corr = (y400 * 400) + (y100 * 100) + (y4 * 4) + y1

    # print( f"{y_corr=} = {y400=}*400 + {y100=}*100 + {y4=}*4 + {y1=}" )

    m153  = days // 153  # 0..2: number of 5 months blocks 31,30,31,30,31
    days -= m153 *  153
    m61   = days //  61  # 0..2: number of 2 months blocks 31,30
    days -= m61  *   61
    m31   = days //  31  # 0..1: number of 31 days months
    days -= m31  *   31  # remaining days: days past 1st of month - also when February
    day   = days + 1                    # day of month 1..31
    m3 = (m153 * 5) + (m61 * 2) + m31   # 0=mar, .. 11=feb

    # print( f"{m3=} = {m153=}*5 + {m61=}*2 + {m31=} / remaining {days=}" )

    year = y_corr + (m3 // 10)          # revert y_corr for jan/feb

    month = ((m3 + 2) % 12) + 1  # 0->3, 1->4, ..., 9->12, 10->1, 11->2

    return year, month, day
2

Hi, are you suggesting a change to the code in the standard library? You showed one line of existing code, then showed dozens of lines of your code, and described it as simplifying.

I don’t understand what you are proposing, or why. Is there a problem with the existing code?

4 Likes
3

The referred line is just a hint to other many lines. (“… to see constructs such as…”!)

  • _DAYS_BEFORE_MONTH[month] → other calculation behind
  • month > 2 → unnecessary conditional
  • _is_leap(year) → another hint about not knowing about the schematic behind Gregorian calendar.

When we roll out all the calls and nested calls behind datetime.datetime and the invert routine, you will see, that it is unnecessarily complex implementation.
Comparison of code with nested calls to code without a nested call is quite unfair. :wink:

4

To make a change to standard library code, you’ll need to make a strong case. Incorrect answers are the strongest justification. Inefficiency might be a reason. So far, it seems like your justification is, “there’s another way to do it.”

You mentioned conditionals: what’s wrong with a conditional? Or nested calls? Why is that a problem? Nested calls are often the best way to modularize code to express common operations once instead of sprinkling them throughout the module.

2 Likes
5

Also note datetime has both a C implementation that is used whenever possible, and a Python one that is used as a fallback.

For example, if CPython is explicitly built without the C version, or something like PyPy is using the pure Python one. But in most cases the much faster C one is used, and the Python one is mostly for historical/prototyping reasons, so there’s a higher bar to modify it.

7

I recall this algorithm from Calendrical Calculations by Dershowitz and Reingold, I had to look it up, equation 2.29;-) The book also notes it is not particularly efficient. I predict any performance gain would be negligible, as our algorithm is quite fast already. Unless you have benchmarks that show otherwise?

Also note datetime has both a C implementation that is used whenever possible, and a Python one that is used as a fallback.

We have the same algorithm in both implementations IIRC.

2 Likes
8

First of all: An AI bot silenced me. Therefore I could not answer up to now.

About C implementation: The fact that also the C code uses “…days + (month > 2 && ((year % 4 == 0) && ((… || …)))” is not for interest to the topic. But also the C code could benefit.

About performance: I never wanted to talk about performance. It is just more about robustness of the code. When the code is just integer arithmetic and it works once, then it will work for any edge case.

Just compare:

toordinal():

    y = year - 1;
    return y*365 + y//4 - y//100 + y//400 + _DAYS_BEFORE_MONTH[month] + (month > 2 and (year % 4 == 0 and (year % 100 != 0 or year % 400 == 0))) + day

suggested replacement:

    y = year - (((month + 9) % 12) // 10)
    return y*365 + y//4 - y//100 + y//400 + _DAYS_BEFORE_MONTH_ALT[month] + day

fromordinal():

    n -= 1
    n400, n = divmod(n, _DI400Y)
    year = n400 * 400 + 1   # ..., -399, 1, 401, ...
    n100, n = divmod(n, _DI100Y)
    n4, n = divmod(n, _DI4Y)
    n1, n = divmod(n, 365)
    year += n100 * 100 + n4 * 4 + n1
    if n1 == 4 or n100 == 4:
        return year-1, 12, 31
    leapyear = n1 == 3 and (n4 != 24 or n100 == 3)

    month = (n + 50) >> 5
    preceding = _DAYS_BEFORE_MONTH[month] + (month > 2 and leapyear)
    if preceding > n:  # estimate is too large
        month -= 1
        preceding -= _DAYS_IN_MONTH[month] + (month == 2 and leapyear)
    n -= preceding
    return year, month, n+1

suggested replacement:

   def divmodmax( n, div, max ):
        i = min( n // div, max )  # integer division with given maximum
        return i, n - (i*div)     # rest (>=div, when n//div > max)

    n += 305                      # shift: jan 1st 1 = 1 --> mar 1st 0 = 0
    c4, n = divmod(    n, 146097 )
    c1, n = divmodmax( n,  36524, 3 )
    y4, n = divmod(    n,   1461 )
    y1, n = divmodmax( n,    365, 3 )
    m5, n = divmod(    n,    153 )
    m2, n = divmod(    n,     61 )
    m1, n = divmod(    n,     31 )

    m     = m5*5 + m2*2 + m1                        # 0=mar ... 11=feb
    year  = c4*400 + c1*100 + y4*4 + y1 + (m // 10) # ...+1 when jan or feb
    month = ((m + 2) % 12) + 1                      # jan=1 ... dec=12
    return year, month, n+1

To me these if n1 == 4 or n100 == 4 , month = (n + 50) >> 5 and if preceding > n: # estimate is too large don’t look very trustworthy.

And please don’t expect further answers from my side. Maybe the AI bot will silence me again… :wink:

I also don’t expect any further answers from your side. Your point of view is clear. I just posted to make the difference visible and in case other developers are interested.

1 Like
9

Hi! I wrote that code (both Python and C versions) long ago. “Simplicity” is in the eye of the beholder, and our views just differ. I was aware of the “pretend Jan and Feb are actually at the end of the previous year” transformation, but that’s not how most people think of it.

_DAYS_BEFORE_MONTH[month] + (month > 2 and _is_leap(year))
[/quote]

is how they think of it. “Conceptual obviousness” was just more important to me than “code golf” :wink: At least in this context, where peak speed isn’t really a goal.

Nothing wrong with your code, and if it had been in from the start, I’d be just as averse to replacing it with my code. “Ain’t broke, don’t fx.”

Trust isn’t required. The test suite exhaustively verifies ordinal<->date conversions for the first and last days of every year in datetime’s range, and for every day in a leap and non-leap year.

4 Likes
10

and

is also how most people think of it?

However: my curiosity has been satisfied: “Ain’t broke, don’t fx.” That is a valid answer to my question.

2 Likes
11

Sure doubt it :wink: What they will think is “this is messy- irregular. Maybe a binary search across two tables, one for leap years and another for regular years?”. The Python code could do that succinctly using the bisect module, but not so much the C code. The Python implementation was a prototype for the C implementation during development, so favored things easily expressed in C.

So how about a cheap approximation + a possible correction? That’s not so much “science” as pragmatic hackery.

It’s then a matter of exhaustive testing to show that the approximation used here is always exact or 1 too large. I picked the constants via iterative poke-and-hope, until “it worked”. I think it “obvious enough” to programmers that shifting right by 5 is a cheap way to divide by 32, “close to” the number of days in a month.

Your

    m61   = days //  61  # 0..2: number of 2 months blocks 31,30
    days -= m61  *   61
    m31   = days //  31  # 0..1: number of 31 days months
    days -= m31  *   31  # remaining days: days past 1st of month - also when February
    day   = days + 1                    # day of month 1..31
    m3 = (m153 * 5) + (m61 * 2) + m31   # 0=mar, .. 11=feb
    ...
    month = ((m3 + 2) % 12) + 1  # 0->3, 1->4, ..., 9->12, 10->1, 11->2

is, to my eyes, even further from “obvious”.

But so it goes: there’s often no truly obvious way to get an exact result from an irregular function. Pick your poison :wink:

Good!

1 Like
12

When you saw the regularity, while you guess “they” don’t see but think “this is messy- irregular”, then it is all the more reason to educate “them” about the regularity of the calendar.

But I never even thought about to align implementation according “most people’s thoughts”.
It is mathematics and “most people” don’t know anyway and even don’t want to know… :wink:
We don’t have to align as messy as most people’s poor knowledge.

The code of mine which you quoted is also an early version. Please check the comparison.
(… “fromordinal(): …” compared to “suggested replacement: …”)
Nothing must be estimated and later being checked, whether estimation was right.
(-> “# estimate is too large”)

13

But I did :wink: De gustibus non est disputandum. I’m not saying you’re “wrong” - I’m saying we think differently.

It’s programming, and Python code also serves pedagogical purposes. We have a step function, which is closely approximated by a straight line. As a programming problem, “cheaply estimate and correct if needed” is a very useful approach in general to such things. Illustrating that was more important to me than diving into domain-specific details, which don’t generalize.

They’re much the same to me. Both versions have 9 instances of int division and mod, compared to just 4 in Python’s code, and those are the most expensive operations. While this code isn’t speed-critical, needless expense isn’t welcome either.

Not quite true. The divmodmax() you introduced later (adding the additional “needless expense” of two Python-level function calls) takes an informed guess at the quotient it really wants, and reduces it if it turns out to be “too large”. The test-and-branch is hiding inside Python’s implementation of min(), but it’s there nevertheless.

Addressing a different kind of irregularity in the function as a whole than the “number of days in a month” irregularity. Perhaps another pile of divs and mods could “hide” that too, but “ain’t broke, don’t fix” still rules for me :wink:

1 Like