3
\$\begingroup\$

I'm a beginner Python (2.7) programmer, and I've just started solving basic problems on SPOJ. I correctly solved the ADDREV problem (http://www.spoj.com/problems/ADDREV/), however my code takes 0.06s time and 8.8M memory to run. The top Python 2.7 rankers for the problem take <0.005s and 4.00M. Since I am starting out and this is a simple code snippet, I would love to get specific tips on how I can optimise the code below to reach these levels of efficiency. I am reading popularly available tips to optimise Python code, including the use of profilers, however I would really appreciate any tips I can already get here.

The problem as described there:

Input

The input consists of N cases (equal to about 10000). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.

Output

For each case, print exactly one line containing only one integer - the reversed sum of two reversed numbers. Omit any leading zeros in the output.

(Source: http://www.spoj.com/problems/ADDREV/)

Here's the code:

def reverse(num):   # Takes a string as input and reverses it, removing any leading or trailing zeros
    num = num.strip("0")
    return num[::-1]

num_cases = input()

for i in range(0, num_cases):
    usr_input = raw_input()
    arr = usr_input.split()
    reversed_sum = int(reverse(arr[0])) + int(reverse(arr[1]))
    print reverse(str(reversed_sum))
\$\endgroup\$
  • 4
    \$\begingroup\$ Welcome to Code Review! As we all want to make our code more efficient or improve it in one way or another, try to write a title that summarizes what your code does, not what you want to get out of a review. Please see How to get the best value out of Code Review - Asking Questions for guidance on writing good question titles. \$\endgroup\$ – Mathias Ettinger Jul 11 '16 at 12:33
  • 1
    \$\begingroup\$ Can you add the problem description to the question. \$\endgroup\$ – Peilonrayz Jul 11 '16 at 12:39
  • \$\begingroup\$ The memory consumption can probably be mitigated by using xrange(..) instead of range(..). There is no need to load 10.000 numbers into memory. \$\endgroup\$ – Sumurai8 Jul 11 '16 at 15:02
1
\$\begingroup\$

A simple optimization would be to use xrange(..) instead of range(..). range(..) in Python 2.7 loads the entire range into memory. xrange(..) on the other hand has "lazy evaluation", which means that it only calculates the next number in the sequence when it is needed. This reduces the memory footprint.

The other heavy thing you are doing is reversing strings three times, and stripping the strings from 0's each time. If you follow the algorithm completely, I don't think you can do much else. However... let's take a look at some not so random examples:

          1234 + 4123
Reversed: 4321 + 3214
Added:    7535
Reversed: 5357

That's an aweful lot like the result of 1234 + 4123. So what's the difference? Well... if two digits add up to more than 10, this is no longer true. We don't add the carry to the digit to the left, but to the digit to the right.

          1294 + 4123
Reversed: 4921 + 3214
Added:    8135
Reversed: 5318

Guess in which direction we write the output? Well, from left to right. So if we add each pair, we can just add the carry to the next digit we write. There are two more questions we have to answer. The first: What if one of the numbers is smaller? How do we align them?

          12 + 4123
Reversed: 21 + 3214
Added:    3235
Reversed: 5323

From that example we can deduce that REVADD'ing 12 + 4123 is like normal adding of 1200 + 4123. The last question is: What if the length of the result is not equal to the things we add?

          9876 + 7896
Reversed: 6789 + 6987
Added:    13776
Reversed: 67731

That is indeed what we would get if we would do the proposed algorithm. You would end up with something like this:

from __future__ import print_function

zero = ord('0')
doublezero = zero * 2

a, b = usr_input.split()
if len(a) < len(b):
    a, b = b, a

carry = 0

for j in xrange(0, len(b)):
    c = ord(a[j]) + ord(b[j]) - doublezero + carry
    print(chr((c % 10) + zero), sep='', end='')
    carry = c / 10

if carry and len(a) == len(b):
    print('1')
elif carry:
    print(chr(ord(a[j+1])+1), a[j+2:], sep='')
else:
    print(a[j+1:])
\$\endgroup\$
  • \$\begingroup\$ Thanks! This was very detailed. I used this approach, while modifying the code for some edge cases (eg. inputs '49 8', '72 + 37' etc. - I could identify 3 edge cases). I tested this on multiple numbers and it seems to work OK, but it gives a "wrong answer" on SPOJ. Further, it now takes 0.12s and consumes 8.8M. Any clues on how I should proceed? All Python solutions available publicly online use the same algorithm as I originally used - I cannot find any solution which takes 4.00M. I could post my new code here, but there isn't enough space here - should I post it as another answer? \$\endgroup\$ – Abhimanyu Sahai Jul 12 '16 at 7:59
  • \$\begingroup\$ @Abhimany: yes, you can post an answer to your own question if you have interesting (and relevant) new insights. \$\endgroup\$ – DarthGizka Jul 12 '16 at 9:47
  • \$\begingroup\$ See this meta question for everything you can do. \$\endgroup\$ – Sumurai8 Jul 12 '16 at 12:40
  • \$\begingroup\$ Thanks guys. Not reposting my code because it's actually pretty much what @Sumurai8 wrote, with just some additional code to account for the edge cases I mentioned. As for why it's giving "wrong answer" on SPOJ, I'll figure that out myself. \$\endgroup\$ – Abhimanyu Sahai Jul 13 '16 at 13:35
  • \$\begingroup\$ @AbhimanyuSahai I don't strip zeroes from the input. I suspect they sneaked in something like 000123 or 123000. \$\endgroup\$ – Sumurai8 Jul 13 '16 at 14:33
2
\$\begingroup\$

The biggest savings comes from computing the results directly from the textual representation of the inputs, instead of converting inputs to numbers, reversing them, adding them, reversing the result and then converting it to text.

Just add the character codes of the inputs to the current carry (initially 0, of course) and deduct the difference between '0' and 0 since the intermediate result contains it twice. If the result is greater than '9', subtract 10 and set the new carry to 1. Rinse and repeat.

P.S.: the task description talks about 'reversed' numbers but one might as well call them 'Little Endian'. That's why one can simply add the digits as they come in and push the result digits out, until the longer of the two inputs ends and the carry is down to 0...

\$\endgroup\$
  • \$\begingroup\$ Thanks! @sumurai8 below suggested a similar approach, and I went ahead and used that - but this still isn't solved as far as my goal of reducing time and memory consumption goes. Details below in my comment to his answer. \$\endgroup\$ – Abhimanyu Sahai Jul 12 '16 at 8:01
  • \$\begingroup\$ @Abhimanyu: Things are tricky with Python because the interpreter overhead changes the runtime cost of things compared to pedestrian compiled languages. In general, things get faster to the degree that processing is pushed into the engine (one call instead of several interpreted ops), meaning that processing characters individually may well be slower than calling builtin routines on whole strings. Your memory use should go down a bit if you replace range with xrange to avoid materialising the range. \$\endgroup\$ – DarthGizka Jul 12 '16 at 9:37
  • \$\begingroup\$ Timing and memory usage figures on SPOJ may depend also on the age of the Python binary. I've seen similar - now unreachable - figures for C#, because older Mono distros used a lot less core The coveted '0.00' timing (i.e. < 5 ms) can be very elusive if the servers are loaded, since it also depends on 'variable constants' like those used to correct for process startup times and so on, and the natural jitter is probably on the order of milliseconds already. Improvements for your SPOJ figures will likely not come from the algorithmic side of things but from the 'interpreterical' Python side. \$\endgroup\$ – DarthGizka Jul 12 '16 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.