Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 220
Sarat Adusumilli Avatar asked Jun 22 '15 06:06

Sarat Adusumilli


4 Answers

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

like image 53
Pruthvi Raj Avatar answered Oct 23 '22 10:10

Pruthvi Raj


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.

like image 39
6502 Avatar answered Oct 23 '22 12:10

6502


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
like image 30
LittleQ Avatar answered Oct 23 '22 11:10

LittleQ


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..

like image 34
Binnut Avatar answered Oct 23 '22 10:10

Binnut