Skip to main content
Code Review

Return to Answer

replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

Update: Claims of performance should be backed up with measurements. I liked Joe Wallis's answerJoe Wallis's answer using itertools.islice() and itertools.count() so much, I combined his approach with mine and timed them.

Update: Claims of performance should be backed up with measurements. I liked Joe Wallis's answer using itertools.islice() and itertools.count() so much, I combined his approach with mine and timed them.

Update: Claims of performance should be backed up with measurements. I liked Joe Wallis's answer using itertools.islice() and itertools.count() so much, I combined his approach with mine and timed them.

Typo in 2 function
Source Link
scottbb
scottbb
  • 872
  • 7
  • 13

Update: Claims of performance should be backed up with measurements. I liked Joe Wallis's answer using itertools.islice() and itertools.count() so much, I combined his approach with mine and timed them.

The functions:

from calendar import isleap
from itertools import count, islice

def leep_years_from(year, amount=20):
    return islice((y for y in count(year) if isleap(y)), amount)

def leap4_isleap(year, amount=20):
    return islice((y for y in count(year + abs(year % -4), 4)
                   if isleap(y)), amount)

def leap4(year, amount=20):
    return islice((y for y in count(year + abs(year % -4), 4)
                   if year % 100 != 0 or year % 400 == 0), amount)

All three functions, leep_years_from(), leap4_isleap(), and leap4() do the same thing. leep_years_from() iterates over every year; the other 2 iterate over every 4 years, but leap4() doesn't call calendar.isleap() to determine if the year is a leap year.

Here is one set of results on my machine running cProfile.run() for all three functions, finding the next 10 million leap years (I've eliminated a few unimportant and blank lines):

>>> cProfile.run('list(leep_years_from(2000,10000000))')
        51237117 function calls in 18.425 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <stdin>:1(leep_years_from)
 10000001    9.659    0.000   17.067    0.000 <stdin>:2(<genexpr>)
        1    1.358    1.358   18.425   18.425 <string>:1(<module>)
 41237113    7.408    0.000    7.408    0.000 calendar.py:97(isleap)

>>> cProfile.run('list(leap4b(2000,10000000))')
         20309284 function calls in 6.991 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <stdin>:1(leap4b)
 10000001    3.259    0.000    5.678    0.000 <stdin>:2(<genexpr>)
        1    1.312    1.312    6.991    6.991 <string>:1(<module>)
 10309279    2.419    0.000    2.419    0.000 calendar.py:97(isleap)

>>> cProfile.run('list(leap4(2000,10000000))')
         10000005 function calls in 3.422 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <stdin>:1(leap4)
 10000001    2.037    0.000    2.037    0.000 <stdin>:2(<genexpr>)
        1    1.385    1.385    3.422    3.422 <string>:1(<module>)

The change from checking if every year is a leap year to only checking if every 4 years is a leap year cut the execution time by a factor of 3. By eliminating the check if every 4th year is a leap year (the first check that occurs in calendar.isleap()) and the overhead of the isleap() function call, another factor 2 is gained.

Update: Claims of performance should be backed up with measurements. I liked Joe Wallis's answer using itertools.islice() and itertools.count() so much, I combined his approach with mine and timed them.

The functions:

from calendar import isleap
from itertools import count, islice

def leep_years_from(year, amount=20):
    return islice((y for y in count(year) if isleap(y)), amount)

def leap4_isleap(year, amount=20):
    return islice((y for y in count(year + abs(year % -4), 4)
                   if isleap(y)), amount)

def leap4(year, amount=20):
    return islice((y for y in count(year + abs(year % -4), 4)
                   if year % 100 != 0 or year % 400 == 0), amount)

All three functions, leep_years_from(), leap4_isleap(), and leap4() do the same thing. leep_years_from() iterates over every year; the other 2 iterate over every 4 years, but leap4() doesn't call calendar.isleap() to determine if the year is a leap year.

Here is one set of results on my machine running cProfile.run() for all three functions, finding the next 10 million leap years (I've eliminated a few unimportant and blank lines):

>>> cProfile.run('list(leep_years_from(2000,10000000))')
        51237117 function calls in 18.425 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <stdin>:1(leep_years_from)
 10000001    9.659    0.000   17.067    0.000 <stdin>:2(<genexpr>)
        1    1.358    1.358   18.425   18.425 <string>:1(<module>)
 41237113    7.408    0.000    7.408    0.000 calendar.py:97(isleap)

>>> cProfile.run('list(leap4b(2000,10000000))')
         20309284 function calls in 6.991 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <stdin>:1(leap4b)
 10000001    3.259    0.000    5.678    0.000 <stdin>:2(<genexpr>)
        1    1.312    1.312    6.991    6.991 <string>:1(<module>)
 10309279    2.419    0.000    2.419    0.000 calendar.py:97(isleap)

>>> cProfile.run('list(leap4(2000,10000000))')
         10000005 function calls in 3.422 seconds

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <stdin>:1(leap4)
 10000001    2.037    0.000    2.037    0.000 <stdin>:2(<genexpr>)
        1    1.385    1.385    3.422    3.422 <string>:1(<module>)

The change from checking if every year is a leap year to only checking if every 4 years is a leap year cut the execution time by a factor of 3. By eliminating the check if every 4th year is a leap year (the first check that occurs in calendar.isleap()) and the overhead of the isleap() function call, another factor 2 is gained.

Source Link
scottbb
scottbb
  • 872
  • 7
  • 13

You loop through every year, but you know a priori you only need to test every 4 years. You can reduce your loop overhead by a factor of 4.

To do so, first you need to "precondition" the input year so that it starts on the next (or current) leap year. You want to add 0, 3, 2, or 1, depending on whether year % 4 is 0, 1, 2, or 3. Either of the following methods will do that:

  • year += abs(year % -4)
  • year += (4 - (year % 4)) % 4

Then, in your loop, remove all instances of year+=1 as suggested by others. Instead, at the bottom of the loop, use year += 4. Because of this, you can remove checks for year % 4 != 0 in your loop. Your algorithm would be reduced the following

def loop_year(year, leapyear_count):
    year += abs(year % -4)
    while leapyear_count > 0:
        if year % 100 != 0 or year % 400 == 0:
            print("%s is a leap year") % (year)
            leapyear_count -= 1
        year += 4

Of course, as suggested by others, your conditional could just be if calendar.isleap(year): instead. However, calendar.isleap() will check first for year % 4 == 0, which will always be true. So from a pure performance issue (i.e., if you were generating huge list of the next N leap years), the way it is written above would be more performant.