current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite
1

Here is a simple piece of code in Python. It 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 and 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.

share|improve this question
 
Why do you need to read from STDIN? I guess it will be faster with a file. –  hdima Mar 16 '13 at 17:58
 
You mean to read the whole input at once? I need STDIN because that's how the program sumbitted to SPOJ should work. –  REACHUS Mar 16 '13 at 18:02
add comment

3 Answers

up vote 1 down vote accepted

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
share|improve this answer
 
Much better time: 0.02 (is it because of using readline() instead of input()?), slightly better memory: 4.0M. –  REACHUS Mar 16 '13 at 19:12
 
(after your update) It's still slower than the best implementations on SPOJ but I've learned a few things - thanks. –  REACHUS Mar 17 '13 at 16:10
add comment
up vote 1 down vote

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.

share|improve this answer
 
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. –  REACHUS Mar 16 '13 at 13:40
 
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? –  Yuushi Mar 16 '13 at 14:22
 
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. –  REACHUS Mar 16 '13 at 17:26
 
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. –  hdima Mar 16 '13 at 18:33
add comment
up vote 1 down vote

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.
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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