Am using binary search for insertions. I am inserting the numbers in the list as soon as I read them.
Hence the order is(nlogn).
I have also added the lines" import psyco, psyco.full()" at the beginning of the code,Yet I am getting time limit exceeded.
Please help! Is the time limit set for python reasonable or codechef unreasonably more favorable to cpp as indicated by the large number of successful submissions for cpp/c against almost nil for java/python?
Or is there a way to fix the problem?
@akiba:
Before I make any comment ,I want you to go through this famous faq/blog,Time Limits Based on Programming Language.
See the timelimit for python =3*(timelimit for c++) .
So, for TSORT problem the timelimit for Python coder =3*5=15 seconds ,which i think is fine(although still very tight ) for sorting 10^6 integers in python.
So,your algorithm must be very efficient (use linear time sorting algo for sorting the given 10^6 integers(either counting sort or Radix sort)).
Codechef “as indicated by the large number of successful submissions for cpp/c against almost nil for java/python” does not unreasonably more favour cpp.To keep balance ,they increased the python timelimit thrice in contrast to c/c++.You see more c/cpp submissions because most people still prefer c/cpp as their powerful /strong/favourite programming language since at present its the fastest language (after assembly languages),so even if your algorithm implementation(code-optimisation) is slightly poor/slower,still there is a huge chance for the c/cpp solution to get accepted with in time limit because of fastness of language.
Lastly still ,Is there a way to fix the problem?
Yes there is ,Here is one example::
Use the inbuilt sort function (complexity O(nlogn))of python.
#!/usr/bin/python
import sys
def main():
testdata = map(int, map(str.strip, sys.stdin.readlines()))
numbers = testdata.pop(0)
testdata.sort()
for number in testdata:
print number
main()
Another method includes :counting sort ,Radix Sort,and Heap sort.Sorting algorithm other than these will exceed the timelimit.
Thank you for the response. It was insightful. But, now I am even more confused. I tried using different coding strategies, as variations of your code. The two are attached. Earlier also I had tried using inbuilt sorting method, but the time limit exceeded, then! So, I thought may be by way of taking input was not efficient. But, alas the results are same.
I have attached 2 codes, would be really helpful if you could comment on why they are exceeding time limit. I am new at python, so pardon my lack of knowledge.
Code1:[Same as yours but with different way of creating array,using inbuilt sort O(nlogn)]
import sys
def main():
i = int(sys.stdin.readline())
tt = []
while(i!=0):
tt.append(int(sys.stdin.readline()))
i = i-1
tt.sort()
for number in tt:
print number
main()
Code2:[Taking input the way you had taken and using counting sort: O(n)]
import sys
def main():
testdata = map(int, map(str.strip, sys.stdin.readlines()))
numbers = testdata.pop(0)
k = [0]*(numbers+1)
for number in testdata:
k[number] = k[number]+1
i = 0
while(i!=k):
r = 0
oo = k[i]
while(r!=oo):
print i
main()Don’t know if you are notified about it, but I have put my further doubts as answer to this question. Hoping for a helpful response! Thanx
@akiba::
Inserting the test data using append is slower ,not only in python but in any programming language. The reason is ,one have to iterate till the last inserted member of the container to add the new member ,on every append operation.(Think in this way : appending data at the end of the link-list always takes more time than inserting it in to array ).So obviously ,your first program will time-out.
map(int, map(str.strip, sys.stdin.readlines())),yes that’s the efficient and fast way to take input in python .
The code-2 has in fact shocked me too.Your counting sort seems fine to me.
I even don’t have much idea which sorting algorithm the python sort() function use.
But I believe , just by 2 -3 seconds you are getting a TLE. I doubt the better algorithm than Counting Sort exists for this TSORT problem. And yeah ,that means ,python is not a good choice in contrast to other programming languages , particularly for THIS problem .