1
\$\begingroup\$

Here is a solution to the SPOJ's JPESEL problem. Basically the problem was to calculate cross product of 2 vectors modulo 10. If there is a positive remainder, it's not a valid PESEL number; (return D) if the remainder equals 0, it's a valid number (return N).

import re, sys
n = input()
t = [1,3,7,9,1,3,7,9,1,3,1]
while(n):
    p = map(int, re.findall('.',sys.stdin.readline()))
    # Another approach I've tried in orer to save some memory - didn't help:
    # print 'D' if  sum([int(p[0]) * 1,int(p[1]) * 3,int(p[2]) * 7,int(p[3]) * 9,int(p[4]) * 1,int(p[5]) * 3,int(p[6]) * 7,int(p[7]) * 9,int(p[8]) * 1,int(p[9]) * 3,int(p[10]) * 1]) % 10 == 0 else 'N'
    print 'D' if ( sum(p*q for p,q in zip(t,p)) % 10 ) == 0 else 'N'
    n-=1

The solution above got the following results at SPOJ:

Time: 0.03s
Memory: 4.1M

where the best solutions (submitted in Python 2.7) got:

Time: 0.01s
Memory: 3.7M

How can I optimize this code in terms of time and memory used?

Note that I'm using different function to read the input, as sys.stdin.readline() is the fastest one when reading strings and input() when reading integers.

\$\endgroup\$
  • \$\begingroup\$ Why do you need to read from STDIN? I guess it will be faster with a file. \$\endgroup\$ – hdima Mar 16 '13 at 17:58
  • \$\begingroup\$ You mean to read the whole input at once? I need STDIN because that's how the program sumbitted to SPOJ should work. \$\endgroup\$ – syntagma Mar 16 '13 at 18:02
1
\$\begingroup\$

You can try to replace re module with just a sys.stdin.readline() and replace zip interator with map and mul function from operator module like this:

from sys import stdin
from operator import mul

readline = stdin.readline
n = int(readline())
t = [1,3,7,9,1,3,7,9,1,3,1]

while n:
    p = map(int, readline().rstrip())
    print 'D' if (sum(map(mul, t, p)) % 10) == 0 else 'N'
    n -= 1

Update

It seems getting item from a small dictionary is faster than int so there is a version without int:

from sys import stdin

readline = stdin.readline
val = {"0": 0, "1": 1, "2": 2, "3": 3, "4": 4, "5": 5, "6": 6,
       "7": 7, "8": 8, "9": 9}
val3 = {"0": 0, "1": 3, "2": 6, "3": 9, "4": 12, "5": 15, "6": 18,
        "7": 21, "8": 24, "9": 27}
val7 = {"0": 0, "1": 7, "2": 14, "3": 21, "4": 28, "5": 35, "6": 42,
        "7": 49, "8": 56, "9": 63}
val9 = {"0": 0, "1": 9, "2": 18, "3": 27, "4": 36, "5": 45, "6": 54,
        "7": 63, "8": 72, "9": 81}

n = int(readline())
while n:
    # Expects only one NL character at the end of the line
    p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, _ = readline()
    print 'D' if ((val[p1] + val3[p2] + val7[p3] + val9[p4]
                   + val[p5] + val3[p6] + val7[p7] + val9[p8]
                   + val[p9] + val3[p10] + val[p11]) % 10 == 0) else 'N'
    n -= 1
\$\endgroup\$
  • \$\begingroup\$ Much better time: 0.02 (is it because of using readline() instead of input()?), slightly better memory: 4.0M. \$\endgroup\$ – syntagma Mar 16 '13 at 19:12
  • \$\begingroup\$ (after your update) It's still slower than the best implementations on SPOJ but I've learned a few things - thanks. \$\endgroup\$ – syntagma Mar 17 '13 at 16:10
1
\$\begingroup\$

Likely what is taking up extra time is the line:

 p = map(int, re.findall('.',sys.stdin.readline()))

There are a few things here. Firstly, regular expressions are relatively expensive. Underneath, it likely needs to compile the regular expression (which in this case is very simple, but still). Further, you don't need regular expressions to do this in python. For example, assume the string was something like '343898934'. Then this is equivalent to:

p = [int(k) for k in '343898934']

The above will likely be slightly faster.

The second place here that could be optimized (memory wise) is that map in Python 2.x returns a list as opposed to a generator. So instead we could do:

p = (int(k) for k in sys.stdin.readline())

The fact that this also removes the re import may also impact timing and memory usage, depending on how they measure.

\$\endgroup\$
  • \$\begingroup\$ Thanks. I understand it should run faster after such changes but I've changed my solution exactly as you said and now it's actually slower: time: 0.11, memory: 4.5M. \$\endgroup\$ – syntagma Mar 16 '13 at 13:40
  • \$\begingroup\$ Interesting. I can understand that it might be slower (perhaps the overhead of setting up a generator here is worse than simply creating a small list). Likewise the memory usage. Perhaps try using the list comprehension version? \$\endgroup\$ – Yuushi Mar 16 '13 at 14:22
  • \$\begingroup\$ After changing to list comprehension: time: 0.12 (longer), memory: 4.5M (same as before). I'm wondering whether this can be related to SPOJ's timing system. \$\endgroup\$ – syntagma Mar 16 '13 at 17:26
  • \$\begingroup\$ map can be faster here (you can test it with timeit module). I think you should try readline = sys.stdin.readline before the loop and then map(int, readline().rstrip()) inside the loop. \$\endgroup\$ – hdima Mar 16 '13 at 18:33
1
\$\begingroup\$

There are a few tricks you can try to improve upon hdima's answer.

  • Put all the code in a function because Python accesses local variables more efficiently than global variables.
  • for i in xrange(n) is faster than while n: n -= 1, but even better is to avoid the counter variable:
  • Use itertools.islice to read n lines: for line in islice(stdin, n)
  • stdout.write('D\n') is faster than print 'D'
  • Even faster is to write all once by stdout.write("".join( <list comprehension> )) but this makes memory usage dependent on size of input. To avoid that, you could add an outer loop that splits the work in chunks.
\$\endgroup\$

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.