As part of a (now finished) challenge I ended up creating a fraction class to use. After profiling my overall code I'm spending just under half of the time in __init__ for that class rather than doing something useful.

Here is the __init__:

class fraction(Number):

    __slots__ = ("n", "d")
    def __init__(self, n, d, returnint = False) -> None:

        if type(n) == int and type(d) == int:
            pass
        elif type(n) not in (fraction, int) or type(d) not in (fraction, int):
            raise TypeError("Can't create fraction ({a}, {b}) numerator and denominator must be int or fraction.".format(a = n, b = d))
        else:
            if type(n) == fraction:
                d = d * n.d
                n = n.n
            if type(d) == fraction: 
                n = n * d.d
                d = d.n
        
        if d == 0:
            raise ValueError("Denominator cannot be zero")
        
        a = n
        b = d
        while not b == 0:
            r = a%b
            a = b
            b = r
        gcd = int(a)
        self.n = int(n/gcd)
        self.d = int(d/gcd)

And here's an example output from cprofile on the overall code:

1971273 function calls (1935347 primitive calls) in 3.232 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
...
272503/250039    1.516    0.000    1.541    0.000 doomsday.py:46(__init__)
...

Yes, I'm creating a lot of them and for some variants of my solution I can potentially adjust the algorithm to avoid fractions but ... it really niggles, and in other situations I can't get away without a lot of fractions.

I also tried splitting out the simplification steps (from a=n to gcd = int(a)) and reprofiling - that showed me that 50-60% of the time was going on this (but added a 10% overhead for the extra function call). There is still just under 25% of my run time going to simply initiating the object and doing no real calculation.

How can I speed this up?

CodePudding user response：

Thanks to the commenters for pointers.

tldr; using a class will have overhead. Refactoring the main code to use integer maths is faster.

Using an object / class has a clear overhead. I've improved the performance of the original code in two ways:

1. Using isinstance() instead of type() ==
2. Removing the calls to int() in the simplification code

After these changes, approximately half of the time spent in __init__ is overhead (including the if statements). The other half is running the simplification.

Based on that I have also refactored my main code to use integer maths by implementing the Bareiss algorithm (see this (my) answer here: https://scicomp.stackexchange.com/questions/34512/bareiss-algorithm-vs-lu-decomposition/41262#41262) for matrix determinants and to avoid using fractions as much as possible.

The final code looks like this:

class fraction(Number):

    __slots__ = ("n", "d")
    def __init__(self, n, d, returnint = False) -> None:

        if isinstance(n, int) and isinstance(d, int):
            pass
        elif not isinstance(n, (fraction, int)) or not isinstance (d, (fraction, int)):
            raise TypeError("Can't create fraction ({a}, {b}) numerator and denominator must be int or fraction.".format(a = n, b = d))
        else:
            if isinstance(n, fraction):
                d = d * n.d
                n = n.n
            if isinstance(d, fraction): 
                n = n * d.d
                d = d.n
        
        if d == 0:
            raise ValueError("Denominator cannot be zero")
        
        a = n
        b = d
        while not b == 0:
            r = a%b
            a = b
            b = r
        gcd = a
        self.n = n//gcd
        self.d = d//gcd

And here for completeness a view on the overhead of setting up an object:

from timeit import timeit


class dummy(object):
    __slots__ = "i"

    def __init__(self, i = 0):
        self.i = i

def do_int(x):
    a = x

def do_dummy(x):
    a = dummy(x)

print("Int")
print(timeit(lambda: do_int(6)))

print("Class")
print(timeit(lambda: do_dummy(6)))

gives:

Int
0.261943900026381
Class
0.7345267999917269