Why is one function of divisor >3000% faster than the other?-CodePudding

I was doing some simple Python exercises on https://www.practicepython.org/ when I did this task https://www.practicepython.org/exercise/2014/02/26/04-divisors.html.

I wanted to test different ways to code the answer, and I saw solutions in the comment field that piqued my interest; two codes looked similar, but one is almost 4000% faster than the other!

Code:

import time

start = time.time()

print("Fast code:")

#the slow code
def divisor(x):
    divisors = []
    for i in range(1, int(x)):
        if x % i == 0:
            divisors.append(i)
            divisors.sort()
    print(divisors)


divisor(50000000)
end = time.time()
print("Time elapsed: ")
print(end - start)

print("Fast code:")

start = time.time()

#the fast code!
def divisor2(x):
    divisors = []
    for i in range(1, int(x**.5)):
        if x % i == 0:
            divisors.append(i)
            divisors.append(x//i)
            divisors.sort()
    print(divisors)
divisor2(50000000)
end = time.time()
print("Time elapsed: ")
print(end - start)

Time elapsed (slow code):

3.1739981174468994

Time elapsed (fast code):

0.0010004043579101562

Can anyone please tell me how this is possible so perhaps anyone can take home some valuable faster coding skills for their toolbelt?

CodePudding user response：

x**.5 is x to the power of a half, it's a square root.

Both using x = 50,000,000, the first does:

for i in range(1, int(x)):

fifty million loops.

The second does:

for i in range(1, int(x**.5)):

seven thousand loops.

The reason you can do this when calculating divisors is because they form two sides of a rectangle:

 __
|  |
|  |
|__|

If you know the area (the goal, 50 million), and you know one side (the counter i) then you can work out the other side. Where both sides are the same is the square root, and it acts like a pivot, if one is shorter than that then the other must be longer, and balance it out. That is, 100/2 = 50 that gives you both 2 and 50.

So you can count up to the square root to find all the short answers, work out the other side (the counter-balance) for each one, and then you have all the answers. 100/10 = 10 that gives you 10 as a divisor, and tells you that if you keep counting up to get to 100/50 = 2 you've already seen that from the other side and got 50.

That's why the second code has:

        divisors.append(i)
        divisors.append(x//i)

Adding two values to the list, after only testing one.

CodePudding user response：

Classic O(n) vs O(n^0.5)

The first one is doing 50000000 operations

The second one is doing 7000 operations (7000 times fewer)

And what about the time difference? 3000 times faster? Something doesn't add up.

Here!

divisors.sort()

You're doing this after each divisor pair is found, and that's an expensive operation. Simply shift it 2 indentation levels to the left (same level as print), and see the ~7000 times faster performance or more.

Why this is happening?

Well, if you found that 15 is divisible by 3, then why check every other number and then check 5 again, when you know that if 15 is divisible by 3, it's also divisible by 15/3. Also no number is divisible by any number bigger than its square root, where the result is also bigger than the square root. Thus, it doesn't make sense to run the loop for so long - it will find no solutions. Since 50000000 is definitely not divisible by any number bigger than 7071.067811865475 which will result in another number bigger than 7071.067811865475, checking 7072 and bigger numbers is a huge waste of time, if we add the result of the division for each divisor we find.