Here is my code:
import time, profile
def timing():
t1 = time.time()
f1()
print "f1: %.3f" %(time.time()-t1)
t2 = time.time()
f2()
print "f2: %.3f" %(time.time()-t2)
def f1():
lint = int
list = [lint(raw_input()) for i in range(lint(raw_input()))]
list.sort()
for l in list:
print l
return
def f2():
list = [int(raw_input()) for i in range(int(raw_input()))]
list.sort()
for l in list:
print l
return
profile.run('timing()', 'sort.tmp')
Vim is really programmers best friend like earthworms are farmers'
Vim helped me write a test case of this size in < 60 sec, and now I am there ready with a profiler and the time module to measure the time it takes to run that sort call.. The sort call that is a built-in function is probably not the culprit, I think in case I could parallelly carry on the reading and the sorting process the much needed optimisation can be brought..
This particular problem at the codechef.com under the easy problems tab is not that easy to do in python.. Everytime I get TLE error..
Some handy commands in vim:
:set binary
:set noeol
let me turn off the automatic end-of-line vim adds to every file editted in it.. And the profiler and time tools are easily available on the web can be found using google!
Here is the profiler output.
>>> import pstats
>>> p = pstats.Stats('sort.tmp')
>>> p.sort_stats('cumulative').print_stats(15)
Thu Dec 30 16:17:31 2010 sort.tmp
2103371 function calls in 114.964 CPU seconds
Ordered by: cumulative time
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.000 0.000 114.964 114.964 profile:0(timing())
1 0.109 0.109 114.964 114.964 sort.py:2(timing)
1 0.000 0.000 114.964 114.964
1 93.992 93.992 114.855 114.855 sort.py:10(f1)
2103357 19.643 0.000 19.643 0.000 :0(raw_input)
2 1.110 0.555 1.110 0.555 :0(sort)
2 0.110 0.055 0.110 0.055 :0(range)
1 0.000 0.000 0.000 0.000 :0(setprofile)
4 0.000 0.000 0.000 0.000 :0(time)
0 0.000 0.000 profile:0(profiler)
1 0.000 0.000 0.000 0.000 sort.py:18(f2)
Suggestions solicited.. Just in case someone has faced this before, I have to submit a solution in python that sorts the huge integers in < 5 sec..
