5

I coded this problem at CodeChef and submitted it as Python3 solution:

import sys

n,k = map(int,sys.stdin.readline().split(" "))
nos = map(int,sys.stdin.readlines())
ans = 0
for i in nos:
    if i>0 and i%k == 0:
        ans += 1
print(ans)

But it gives you a Time Limit Exceeded, to my horror, if I write the code as:

import sys

n,k = map(int,sys.stdin.readline().split(" "))
nos = map(int,sys.stdin.readlines())
ans = 0
for i in nos:
    if i>0 and i%k == 0:
        ans += 1
print ans

and submit it as a Python2 solution, then the solution gets accepted.

I simply fail to understand where is this going?...

====### UPDATE ###====

solution by Sebastian works for Python3 but is a considerable 10secs slower than my python2.7 solution. I still did not get the answer that why is there a degradation of performance with latest version of the language compared to previous?...

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
whizzzkid
  • 1,174
  • 12
  • 30
  • 1
    [This question](http://stackoverflow.com/questions/14900232/unpickle-a-data-structure-vs-build-by-calling-readlines) seems to indicate that `readlines` has gotten slower in Python3 (by a factor of almost 3 in the example). Have you tried timing your code? – mtth Feb 16 '13 at 14:20
  • [This question](http://stackoverflow.com/questions/10321334/handling-large-inputs-in-python) may be relevant. – DSM Feb 16 '13 at 14:25
  • I think `map` (or in 2.x, `imap`) themselves are slower than the equivalent generator comprehension, try `(int(x) for line in sys.stdin.readlines())` to see of that helps? – millimoose Feb 16 '13 at 14:29
  • What's a TLE, please? I suppose it's something like "Too Long Error"? – MiniQuark Feb 16 '13 at 14:30
  • TLE (from the website requirements): Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach. – engineerC Feb 16 '13 at 14:36
  • Try it with just a `print(sum(not i%k for i in nos))` after the assignment to `nos` instead of the written out `for` loop. – martineau Feb 16 '13 at 19:31
  • @mtth agreed, but why?... why was this method slowed down?... – whizzzkid Feb 17 '13 at 14:53

3 Answers3

2

I can confirm that exactly the same solution passes the tests on python 2.7, but it timeouts on python 3.1:

import sys
try:
    from future_builtins import map # enable lazy map on Python 2.7
except ImportError:
    pass 

file = sys.stdin
n, k = map(int, next(file).split())
print(sum(1 for i in map(int, file) if i % k == 0))

file is an iterator over lines. The code supports large files due to map is lazy (doesn't consume the whole file at once).

The following code passes the tests on python 3.1:

import sys
n, k, *numbers = map(int, sys.stdin.buffer.read().split())
print(sum(1 for i in numbers if i % k == 0))

Note: it doesn't support arbitrary large inputs (as well as your code in the question).

jfs
  • 399,953
  • 195
  • 994
  • 1,670
  • I am impressed as a n00b by the code simplicity for the python3 solution you give, it works great!... but... there is a considerable time difference. code for python2(mine) runs in 30 secs for n files... where as this runs in 40+ secs for n files... that is a huge 10sec loss. I thought performance is improved when new versions are introduced. this is the first time I encountered slower performance because of a higher version. I think I should put in time on Python2.7 rather than Python3 – whizzzkid Feb 17 '13 at 14:43
  • This Perl-like tuple unpacking (yes, you kosher pythonistas - this invention comes straight from Perl, the ancestor of Python) is quite neat. I see no reason to keep it from some Python 2.8, but no - the dictators decided to use such incentives to force us to Python 3. Well, I might eventually use it in some 5-10 years, but this doesn't mean I am blind and can't see it's a fraud! It's like XHTML 2.0 - authors of it were proud and said it's the future. And then came sensible and pragmatic HTML5. Guido, better start Python 4, which should be compatible with 2.x (breaking 3.x, but that's OK) – Tomasz Gandor Dec 20 '13 at 08:56
0

In python3, things like map, zip return generators instead of a list. I think the generator brings the overhead that make your code TLE. To make a real list, use list comprehension [int(line) for line in std.sys]

Ray
  • 1,647
  • 13
  • 16
0

The error occurs the line that says, n,k = map(int,sys.stdin.readline().split(" ")). I tried to separate the n and the k, but it still seems to get stuck as soon as the map command is called. Here is a page that explains the map function: http://docs.python.org/2/library/functions.html#map Something seems strange with the syntax that neither I or IDLE could find. Hope this helps

erdekhayser
  • 6,537
  • 2
  • 37
  • 69
  • what if I do not call the map and just split it and use the list values, it should have done it then... but it still does not... – whizzzkid Feb 17 '13 at 14:35