CODEWITHSUNDEEP
pythonperformancegenerator
Sarat Adusumilli
Sarat Adusumilli

Reputation: 109

Why is using a generator function twice as fast in this case?

The code which is common for both the implementations:

from math import sqrt

def factors(x):
    num = 2
    sq = int(sqrt(x))
    for i in range(2, sq):
        if (x % i) == 0:
            num += 2
    return num + ((1 if sq == sqrt(x) else 2) if x % sq == 0 else 0)

1. Implementation which doesn't make use of a generator function:

i = 1
while True:
    if factors(i * (i+1) * 0.5) > 500:
        print(int(i * (i+1) * 0.5))
        break
    i += 1

2. Implementation which makes use of a generator function:

def triangle():
    i = 1
    while True:
        yield int(0.5 * i * (i + 1))
        i += 1

t = triangle()

while True:
    num = t.__next__()
    if factors(num) > 500:
        print(num)
        break

The Question:

The first implementation takes about 4 seconds while the second one takes approximately 8.2 seconds. Why is there such a big difference between the run times of the two implementations?

Upvotes: 10

Views: 1310

Answers (4)

Pruthvi Raj
Pruthvi Raj

Reputation: 3036

temp1():

def temp1():
        i = 1
        while True:
            if factors(i * (i+1) * 0.5) > 500:
                print(int(i * (i+1) * 0.5))
                break
            i += 1

temp2():

def temp2():
    def triangle():
        i = 1
        while True:
            yield int(0.5 * i * (i + 1))
            i += 1

    t = triangle()

    while True:
        num = t.next()
        if factors(num) > 500:
            print(num)
            break

cProfile for both:

enter image description here After changing the factors call in temp1() to factors(int(...)), It turns out that temp1() takes the similar time

Modified temp1 to pass int rather than float:

def temp1():
    i = 1
    while True:
        if factors(int(i * (i+1) * 0.5)) > 500:
            print(int(i * (i+1) * 0.5))
            break
        i += 1

enter image description here

So it turns out that in your first implementation you are passing float to the factors() and floating point arithmetic is complex than integer arithmetic

Why Floating point operations are complex??

Because the way floats are represented internally is different from ints, they are represented in 3 parts as sign , mantissa and exponent (IEEE 754) whereas representation of integer is much simple and so are operations like addition and subtraction on integers, even multiplication and division are performed using a combination of addition,subtraction and shift operations internally . since integer addition and subtraction are simple, so are their division/multiplications and hence floating point operations are some what expensive

Why Floating point modulo is expensive than Integer?

The answer is same as above , A modulo operation is nothing but combination of primitive operations mentioned above as follows:

a mod n = a - (n*int(a/n))

Since primitive operations for floats are more expensive, so is modulo for floats

Upvotes: 11

6502
6502

Reputation: 114579

In the explicit case you're not taking the int of the expression before calling factors and therefore the value passed will be a floating-point number.

In the generator case you're instead yielding int(...), calling factors passing an integer number.

Upvotes: 8

LittleQ
LittleQ

Reputation: 1925

You can remove factors() of the code, make 500 much larger.

# implementation 1
i = 1
while True:
    if (i * (i + 1) * 0.5) > n: # n=100000
        # print int(i * (i + 1) * 0.5),
        break
    i += 1

and %timeit, to compare with implementation 2:

def triangle():
    i = 1
    while True:
        yield i * (i + 1) * 0.5
        i += 1

t = triangle()

while True:
    num = t.next()
    if num > n:
        # print num,
        break

Upvotes: 3

Binnut
Binnut

Reputation: 90

The only difference as far as I know is that you do the calculation i * (i+1) * 0.5 twice in the first example. It is not a expensive computation, but it might make a big difference since it is such a big portion of the program..

Upvotes: 2

Related Questions