Enormous Input and Output Test

N

n00m

Duncan Booth,

alas... still TLE:

2800839
2009-10-04 13:03:59
Q
Enormous Input and Output Test
time limit exceeded
-
88M
PYTH
 
J

Jon Clements

Duncan Booth,

alas... still TLE:

2800839
2009-10-04 13:03:59
Q
Enormous Input and Output Test
time limit exceeded
-
88M
PYTH

Just to throw into the mix...

What about buffering? Does anyone know what the effective stdin buffer
is for Python? I mean, it really can't be the multiplying that's a
bottleneck. Not sure if it's possible, but can a new stdin be created
(possibly using os.fdopen) with a hefty buffer size?

I'm probably way off, but something to share.

Cheers,

Jon.
 
N

n00m

50-80%% of users from the 1st page in ranklist are
super-extra-brilliant

#5 there: http://www.spoj.pl/users/tourist/
This 14 y.o. schoolboy won IOI 2009, in this August,
and he's about to get into Guiness' book as the youngest
winner for all the history of international olympiads on
informatics.
He lives at 20 minutes of walking from my house, -- it's
South East Belarus, near to Chernobyl (mutants?).
Hardly I'm able to do even 10% of what he can do, though
I'm older by 3 times than him.
 
N

nn

I did try a version where I just read the data in, split it up, and then
wrote it out again. On my test file that took about 2 seconds compared with
the 8 seconds it took the full code I posted, so while there may be scope
for faster I/O (e.g. using mmap), any real speedup would have to be in the
convert to int, multiply, convert back to str pipeline.

This takes 5 second on my machine using a file with 1,000,000 random
entries:

inf=open('tstf')
outf=open('tstof','w')
for i in xrange(int(inf.next(),10)):
n1,s,n2=inf.next().partition(' ')
print >>outf,int(n1,10)*int(n2,10)
outf.close()
inf.close()
 
N

n00m

This takes 5 second on my machine using a file with 1,000,000 random...

Surely it will fail to pass time limit too
 
I

Irmen de Jong

n00m said:
numerix's solution was excelled by Steve C's one (8.78s):
http://www.spoj.pl/ranks/INOUTEST/lang=PYTH
I don't understand nothing.

I just got my solution accepted, it ran in 14 seconds though.
I have no idea how to shave more seconds off, so I think 7.5 seconds for the fastest
solution is really mindboggling.

Things that eventually made my solution run within the time limit:
- I didn't use int()
- I used Psyco

Those two resulted in the biggest speed increase.
Tweaking with buffered/unbuffered IO was insignificant.

Cheers
Irmen
 
J

John Yeung

I just got my solution accepted, it ran in 14 seconds though.

Hey, that's pretty good. Until n00m instigated the most recent
INOUTEST craze, the only accepted answer besides numerix's was one
that barely squeaked in at 19.81s, and that result was achieved with
the older and apparently much faster (at least on the SPOJ machine)
Python 2.5.

(I see a lot of people trying to pass INOUTEST with Python these days,
many or most of them because they have read this thread.)
Things that eventually made my solution run within the time limit:
- I didn't use int()
- I used Psyco

Those two resulted in the biggest speed increase.
Tweaking with buffered/unbuffered IO was insignificant.

Thank you so much for these tips. I quickly threw something together
and now have my very own accepted INOUTEST answer! It's clearly not
optimized, and I think a lot of people will soon have solutions much
faster than mine and closer to yours, now that they are not wasting
their efforts chasing dead ends.

John


P.S. I hope people realize that the concise, intuitive, readable
answers we all tried in our first couple of (failed) attempts are much
more Pythonic than the beasts that were created just for SPOJ.
 
N

n00m

N00m The Instigator... hahaha :)
I always wish I was a producer, an entertainer,
an impressario, or even a souteneur (kidding).

Life is complex: it has both real and imaginary parts.
Some producer (Mr. Gomelsky) nicknamed Eric Clapton as
"Slow Hand", many years ago.
Gomel is my native town and apparently russian name
"Gomelsky" means "smb/smth belonging to Gomel".
 
I

Irmen de Jong

John said:
P.S. I hope people realize that the concise, intuitive, readable
answers we all tried in our first couple of (failed) attempts are much
more Pythonic than the beasts that were created just for SPOJ.

Well, it is not often that we need to micro optimize stuff (or how would you call it) in
Python, but this was a fun exercise to do that. You need to think about the small tricks
that you can use to speed up your code. And then you come up with things like:

- avoid method/function calls
- use table lookups instead of computation
- use iterators
- use tools like psyco to help you out in the odd case where the above doesn't cut it

These things are useful to keep in mind also in general I think!

-irmen


PS the actual loop of my solution isn't that much bigger than it was in my first, most
readable, attempt. But I think that has everything to do with the complexity of the
task: it is very simple. Ofcourse I cannot speak about the implementation of the
solutions that are still faster by a factor of 2...
 
Joined
May 30, 2012
Messages
1
Reaction score
0
My code runs till 16.62 sec

I wrote a code which runs till 16.62 sec. But did it by first converting numbers to int and then multiplying. Please can someone tell me how to multiply the numbers without converting them to integers. Please help.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top