How to get REALLY fast python over a simple loop

Question

Edit2: I finally got it to pass at 10.54 seconds. I used nearly all of your answers to get there and thus it was hard to choose one as 'correct' but I believe the one I chose sums it up the best. Thanks to you all. Final passing code is below.

Edit: I included some of the suggested updates in the included code.

I'm working on a spoj problem, INTEST. The goal is to specify the number of test cases (n) and a divisor (k), then feed your program n numbers. The program will accept each number on a newline of stdin and after receiving the nth number, will tell you how many were divisible by k.

The only challenge in this problem is getting your code to be FAST because it k can be anything up to 10^7 and the test cases can be as high as 10^9.

I'm trying to write it in python and having trouble speeding it up. Any ideas?

Extensions and third-party modules are not allowed. The code is also run by the SPOJ judge machine, so I do not have the option of changing interpreters.

Thanks, Mike

import sys
import psyco
psyco.full()

def main():
    from sys import stdin, stdout
    first_in = stdin.readline()
    thing = first_in.split()
    n = int(thing[0])
    k = int(thing[1])
    total = 0

    list = stdin.readlines()
    for item in list:
        if int(item) % k == 0:
            total += 1

    stdout.write(str(total) + "\n")

if __name__ == "__main__":
    main()

Answer 1

Use psyco, it will JIT your code, very effective when there is big loop and calculations.

Edit: Looks like third party modules are not allowed,

So, you may try converting your loop to list comprehensions, it supposed to be run at C level, so it should be faster a little bit.

sum(1 if int(line) % k == 0 else 0 for line in sys.stdin)

Answer 2

[Edited to reflect new findings and passing code on spoj]

Generally, when using Python for spoj:

• Don't use "raw_input", use sys.stdin.readlines(). That can make a difference for large input. Also, if possible (and it is, for this problem), read everything at once (sys.stdin. readlines()), instead of reading line by line ("for line in sys.stdin...").
• Similarly, don't use "print", use sys.stdout.write() - and don't forget "\n". Of course, this is only relevant when printing multiple times.
• As S.Mark suggested, use psyco. It's available for both python2.5 and python2.6, at spoj (test it, it's there, and easy to spot: solutions using psyco usually have a ~35Mb memory usage offset). It's really simple: just add, after "import sys": import psyco; psyco.full()
• As Justin suggested, put your code (except psyco incantation) inside a function, and simply call it at the end of your code
• Sometimes creating a list and checking its length can be faster than creating a list and adding its components.
• Favour list comprehensions (and generator expressions, when possible) over "for" and "while" as well. For some constructs, map/reduce/filter may also speed up your code.

Using (some of) these guidelines, I've managed to pass INTEST. Still testing alternatives, though.

Answer 3

For other readers, here is the INTEST problem statement. It's intended to be an I/O throughput test.

On my system, I was able to shave 15% off the execution time by replacing the loop with the following:

print sum(1 for line in sys.stdin if int(line) % k == 0)

Answer 4

Hey, I got it to be within the time limit. I used the following:

• Psyco with Python 2.5.
• a simple loop with a variable to keep count in
• my code was all in a main() function (except the psyco import) which I called.

The last one is what made the difference. I believe that it has to do with variable visibility, but I'm not completely sure. My time was 10.81 seconds. You might get it to be faster with a list comprehension.

Edit:

Using a list comprehension brought my time down to 8.23 seconds. Bringing the line from sys import stdin, stdout inside of the function shaved off a little too to bring my time down to 8.12 seconds.

Answer 5

Just recently Alex Martinelli said that invoking code inside a function, outperforms code run in the module ( I can't find the post though )

So, why don't you try:

import sys
import psyco

psyco.full1()

def main():

    first_in = raw_input()
    thing = first_in.split()
    n = int(thing[0])
    k = int(thing[1])
    total = 0
    i = 0

    total = sum(1 if int(line) % k == 0 else 0 for line in sys.stdin)

    print total
if __name__ == "__main__":
    main()

IIRC the reason was code inside a function can be optimized.

Answer 6

Using list comprehensions with psyco is counter productive.

This code:

 count = 0
 for l in sys.stdin:
     count += not int(l)%k

runs twice as fast as

count = sum(not int(l)%k for l in sys.stdin)

when using psyco.