Velocity Reviews > Enormous Input and Output Test

Enormous Input and Output Test

n00m
Guest
Posts: n/a

 10-03-2009
Hi, py.folk!

I need your help to understand how
http://www.spoj.pl/problems/INOUTEST/
can be passed in Python.

I see two guys who managed to get accepted:
http://www.spoj.pl/ranks/INOUTEST/lang=PYTH

My code for this is:
===========================================
import psyco
psyco.full()

import sys

def noo(b):
b = b.split()
return str(int(b[0]) * int(b[1])) + '\n'

def foo():
##sys.stdin = open('D:/1583.txt', 'rt')
a = a[1:int(a[0]) + 1]
a = map(noo, a)
sys.stdout.writelines(a)

foo()
===========================================

But it gets "Time Limit Exceeded" verdict.
Any ideas?

Chris Rebert
Guest
Posts: n/a

 10-03-2009
On Sat, Oct 3, 2009 at 6:54 AM, n00m <(E-Mail Removed)> wrote:
> Hi, py.folk!
>
> I need your help to understand how
> http://www.spoj.pl/problems/INOUTEST/
> can be passed in Python.

<snip>
> def foo():
> Â* Â*##sys.stdin = open('D:/1583.txt', 'rt')

That line is probably a Very Bad Idea (TM) as it reads the *entire*
enormous file into memory *at once*. It would probably be much better
to iterate over the file, thus only reading one individual line at a
time. I'm betting the massive malloc()ing involved with .readlines()
is a large part of the slowness.

<snip>
> But it gets "Time Limit Exceeded" verdict.
> Any ideas?

Cheers,
Chris
--
http://blog.rebertia.com

Terry Reedy
Guest
Posts: n/a

 10-03-2009
n00m wrote:
> Hi, py.folk!
>
> I need your help to understand how
> http://www.spoj.pl/problems/INOUTEST/
> can be passed in Python.
>
> I see two guys who managed to get accepted:
> http://www.spoj.pl/ranks/INOUTEST/lang=PYTH
>
> My code for this is:
> ===========================================
> import psyco
> psyco.full()
>
> import sys
>
> def noo(b):
> b = b.split()
> return str(int(b[0]) * int(b[1])) + '\n'
>
> def foo():
> ##sys.stdin = open('D:/1583.txt', 'rt')
> a = a[1:int(a[0]) + 1]
> a = map(noo, a)
> sys.stdout.writelines(a)
>
> foo()
> ===========================================
>
> But it gets "Time Limit Exceeded" verdict.
> Any ideas?

Don't waste your time with problem sites that judge raw-clock time over
(and before) accuracy, thereby greatly favoring low-level languages and
hack tricks over clear high-level code.

n00m
Guest
Posts: n/a

 10-04-2009
On Oct 4, 2:29*am, Chris Rebert <(E-Mail Removed)> wrote:

>
> That line is probably a Very Bad Idea (TM) as it reads the *entire*
> enormous file into memory *at once*. It would probably be much better
> to iterate over the file, thus only reading one individual line at a
> time. I'm betting the massive malloc()ing involved with .readlines()
> is a large part of the slowness.

Certainly not.
The culprit is line "a = map(noo, a)".
Without it execution time = 2.59s (I've just checked it).

n00m
Guest
Posts: n/a

 10-04-2009
PS
Time Limit for this problem = 20s

alex23
Guest
Posts: n/a

 10-04-2009
On Oct 3, 11:54*pm, n00m <(E-Mail Removed)> wrote:
> I need your help to understand howhttp://www.spoj.pl/problems/INOUTEST/
> can be passed in Python.
>
> My code for this is:
> ===========================================
> import psyco
> psyco.full()
>
> import sys
>
> def noo(b):
> * * b = b.split()
> * * return str(int(b[0]) * int(b[1])) + '\n'
>
> def foo():
> * * ##sys.stdin = open('D:/1583.txt', 'rt')
> * * a = sys.stdin.readlines()
> * * a = a[1:int(a[0]) + 1]
> * * a = map(noo, a)
> * * sys.stdout.writelines(a)
>
> foo()
> ===========================================
>
> But it gets "Time Limit Exceeded" verdict.
> Any ideas?

map() is really at its most efficient when used with built-ins, not
user defined functions. In those cases, I believe you're better off
using a for-loop or list comprehension. Also: are you sure they
support psyco? It's not part of stdlib...

I thought something simpler might work:

import sys

nums = map(int, line.split())
print nums[0] * nums[1]

But although this processes 5.5MB < 2 secs on my PC (which meets the
2.5MB/sec criteria outlined in INTEST), I'm getting the same result
that you are.

Do you know how big the input data set actually is?

n00m
Guest
Posts: n/a

 10-04-2009
> Do you know how big the input data set actually is?

Of course, I don't know exact size of input.
It's several MBs, I guess. And mind the fact:
their testing machines are PIII (750MHz).

n00m
Guest
Posts: n/a

 10-04-2009
PS
Yes, they support psyco since long time ago
(otherwise I'd get Compilitation Error verdict).
I used Psyco there many many times.

alex23
Guest
Posts: n/a

 10-04-2009
On Oct 4, 1:58*pm, n00m <(E-Mail Removed)> wrote:
> > Do you know how big the input data set actually is?

>
> Of course, I don't know exact size of input.
> It's several MBs, I guess. And mind the fact:
> their testing machines are PIII (750MHz).

Well, then, that's moved the problem from "challenging" to
"ludicrous". Being asked to conform to one constraint with no
knowledge of the others seems kind of ridiculous.

On my machine, the above code handles ~50MB in ~10sec.

n00m
Guest
Posts: n/a

 10-04-2009
> On my machine, the above code handles ~50MB in ~10sec.

Means their input > 40-50MB
2.
I just see: two guys did it in Python
and I feel myself curious "how on earth?".