[Python] Tips for making a fraction calculator code more optimized (faster and using less memory)

Question

Hello Everyone,

Basicly, what I need for the program to do is to act a as simple fraction calculator (for addition, subtraction, multiplication and division) for the a single line of input, for example:
-input: 1/7 + 3/5
-output: 26/35

My initial code:

import sys

def euclid(numA, numB):
    while numB != 0:
        numRem = numA % numB
        numA = numB
        numB = numRem
    return numA

for wejscie in sys.stdin:
    wyjscie = wejscie.split(' ')
    a, b = [int(x) for x in wyjscie[0].split("/")]
    c, d = [int(x) for x in wyjscie[2].split("/")]
    if wyjscie[1] == '+':
        licz = a * d + b * c
        mian= b * d
        nwd = euclid(licz, mian)
        konA = licz/nwd
        konB = mian/nwd
        wynik = str(konA) + '/' + str(konB)
        print(wynik)
    elif wyjscie[1] == '-':
        licz= a * d - b * c
        mian= b * d
        nwd = euclid(licz, mian)
        konA = licz/nwd
        konB = mian/nwd
        wynik = str(konA) + '/' + str(konB)
        print(wynik)
    elif wyjscie[1] == '*':
        licz= a * c
        mian= b * d
        nwd = euclid(licz, mian)
        konA = licz/nwd
        konB = mian/nwd
        wynik = str(konA) + '/' + str(konB)
        print(wynik)
    else:
        licz= a * d
        mian= b * c
        nwd = euclid(licz, mian)
        konA = licz/nwd
        konB = mian/nwd
        wynik = str(konA) + '/' + str(konB)
        print(wynik)

Which I reduced to:

import sys

def euclid(numA, numB):
    while numB != 0:
        numRem = numA % numB
        numA = numB
        numB = numRem
    return numA

for wejscie in sys.stdin:
    wyjscie = wejscie.split(' ')
    a, b = [int(x) for x in wyjscie[0].split("/")]
    c, d = [int(x) for x in wyjscie[2].split("/")]
    if wyjscie[1] == '+':
        print("/".join([str((a * d + b * c)/euclid(a * d + b * c, b * d)),str((b * d)/euclid(a * d + b * c, b * d))]))
    elif wyjscie[1] == '-':
        print("/".join([str((a * d - b * c)/euclid(a * d - b * c, b * d)),str((b * d)/euclid(a * d - b * c, b * d))]))
    elif wyjscie[1] == '*':
        print("/".join([str((a * c)/euclid(a * c, b * d)),str((b * d)/euclid(a * c, b * d))]))
    else:
        print("/".join([str((a * d)/euclid(a * d, b * c)),str((b * c)/euclid(a * d, b * c))]))

Any advice on how to improve this futher is welcome.

Edit: one more thing that I forgot to mention - the code can not make use of any libraries apart from sys.

Answer 1

Probably the biggest improvement you could make would be to use Python (2.6)'s fractions library:

>>> import fractions
>>> fractions.Fraction(1,7) + fractions.Fraction("3/5")
Fraction(26, 35)

Answer 2

You could factor out the code that reduces the fraction to lowest terms from the individual '+', '-', etc. That should make the code a little cleaner and more compact and readable.

Answer 3

You could use memoization on the euclid function which may help speed up depending on the input data. However this will use more memory

You can also use a tuple assignment in euclid

def euclid(numA, numB):
    while numB != 0:
        numA, numB = numB, numA % numB
    return numA

map is faster here

a, b, c, d = map(int, wyjscie[0].split("/")+wyjscie[2].split("/"))

Answer 4

Factoring out euclid into a helper function is a good idea. I'd suggest trying to further break up your code into more helper functions.

One idea is to create four functions (add, subtract, multiply, divide) like this one:

def multiply(val1, val2):
    # Unpack the tuples.
    numerator1, denominator1 = val1
    numerator2, denoninator2 = val2

    # Figure out the resulting numerator and denominator here.

    # Return the result as a tuple.
    return numerator, denominator

Refactor your code to use the helper functions and I think your main code will be cleaner.

Answer 5

I'd create a class containing numerator and denominator fields (both integers) and implementing __add__, __sub__, __mul__, and __div__ methods. Then you can simply use ordinary math functions to combine the instances.

It might be overkill for your purposes, but the code will be a lot cleaner.

In fact, the class-based approach is exactly how the fractions module is implemented. Normally I'd suggest examining the source code of the fractions module to see how it's written, but since this is for homework I'm not sure that would be allowed. It might be worth checking out after the assignment is over, just to see how a full-blown fractional-number type is implemented.