Friday, December 31, 2010

Time limit exceeded- Error!

When running the same code for sorting integers, but on a test case of size of order 10^6 I realized that it took more than 5s to sort the integers in python.

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(?)
        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..

No comments:

Post a Comment