INTEST on Codechef in Python 3

Question

I have written a program in Python 3 for the INTEST problem on Codechef (included in question). The program is taking a lot of time (55.76s) in Python 3. The same code takes almost 1/10 of the time time (4.97s) in C.

The purpose of this problem is to verify whether the method you are using to read input data is sufficiently fast to handle problems branded with the enormous Input/Output warning. You are expected to be able to process at least 2.5MB of input data per second at runtime.

Input

The input begins with two positive integers \$n\$ \$k\$ (\$n, k\le10^7\$). The next \$n\$ lines of input contain one positive integer \$t_i\,ドル not greater than \10ドル^9\,ドル each.

Output

Write a single integer to output, denoting how many integers \$t_i\$ are divisible by \$k\$.

Example

Input:

7 3
1
51
966369
7
9
999996
11

Output:

4

My questions are:

1. How is it that the Python 3 code is taking so much time or which line of code specifically is taking the most time?
2. Any modifications that can speed up the code?

My CodeChef submissions with time and code.

import sys
__author__ = 'Gourav Chawla'
"""
 Problem Code: INTEST
 Problem URL: http://www.codechef.com/problems/INTEST
 Compatability: Python 3.x
"""
n, k = input().split()
n = eval(n)
k = eval(k)
inputVar = 0
count = 0
# inputVar = [eval(x) for x in input().split()]
inputVar = list(map(int, sys.stdin.readlines()))
for i in inputVar:
 if i % k == 0:
 count += 1
print(count)

• Marc-Andre: Welcome to Code Review! You could add the description of the problem in your question.
• Gourav Chawla: Oh, okay. But isn't the description too long for the question?
• Marc-Andre: See this question on meta for more information : meta.codereview.stackexchange.com/questions/1993/… . No it's not too long, it's important to understand your code to have the definition of the problem.
• Gourav Chawla: Got your point. Made the necessary changes.

Answer 1

I think that there must be something wrong with the way CodeChef runs Python, or with the way it reports the times. The time limit for the problem is 8 seconds, but your Python submissions are passing even though they take 55 seconds and so ought to be out of time even with the five times allowance given to Python programs.

On my laptop, if I create about 80 megabytes of input:

import random
n, k = 10**7, 17
f = open('cr93327.data', 'w')
f.write('{} {}\n', n, k)
for _ in range(n):
 f.write('{}\n'.format(random.randrange(0, 10**7)))

Then this C program runs in 3.3 seconds:

#include <stdio.h>
int main() {
 unsigned n, k, i, m, count = 0;
 scanf("%u %u", &n, &k);
 for (i = 0; i < n; i++) {
 scanf("%u", &m);
 count += (m % k == 0);
 }
 printf("%u\n", count);
 return 0;
}

And this Python 3 program runs in 6.1 seconds:

import sys
n, k = map(int, next(sys.stdin.buffer).split())
count = 0
for i in map(int, sys.stdin.buffer):
 if not i % k:
 count += 1
print(count)

So Python is about twice as slow as C, not ten times as slow.

• Gourav Chawla: The codechef problem thing seems to be right because when I tried the same code on Spoj, it gave me 1.9s time. But then again Spoj might be using different servers and processing speed may differ on the sites in question hence the different output.