find_element.py

[labdmitriy]

Hi Sebastian,

Thanks a lot for your research!

For find_element.py I found that there is a built-in function (for Python 3.9+) to calculate the least common multiple:

import math

def lcm():
    return math.lcm(42, 43)

And since Python 3.5 you can calculate the least common multiple using the greatest common divisor:

def lcm_gcd():
    x = 42
    y = 43
    return abs(x * y) // math.gcd(x, y)

So the previous fastest result (generator) and these implementations have the following timings on my machine with Python 3.10.4:

python -m timeit -s "from find_element import generator" "generator()"
5000 loops, best of 5: 84.4 usec per loop

python -m timeit -s "from find_element import lcm_gcd" "lcm_gcd()"
1000000 loops, best of 5: 254 nsec per loop

python -m timeit -s "from find_element import lcm" "lcm()"
1000000 loops, best of 5: 205 nsec per loop

[switowski]

Hi Dmitry,

Thanks for the comment!
I didn't think about checking directly the equation for the lcm using the gcd (and I wasn't even aware that there is now lcm built-in in the math module), since I focused primarily on iterating over a list. The code executed inside each iteration was an afterthought.

But you are totally right. I don't want to give anyone the impression that using a for loop or a list comprehension is the right way to find the least common multiple. I've added a comment with your remark (https://switowski.com/blog/find-item-in-a-list/#least-common-multiple).

Thanks again for your useful feedback! A good algorithm will always beat the iteration :)

[labdmitriy]

Hi Sebastian,

Thanks a lot for your feedback, it was just a note, your research is incredibly useful anyway! :)