Slow Python!

I solved the problem STDYTAB of June Long Challenge 2015 in python as well as in C++ with the same logic. The solution in C++ got AC, but the same in python got TLE for some tasks in the last sub-task. You can check out the solutions:

Solution in python

Solution in C++

Now, my point is, is the time limit for python[currently 5x] still a bit more strict? or this case is an example that supports the fact that we cannot find an exactly equivalent time limit for a language with respect to another one.

Note: I am neither a pro at coding in C++ nor a pro at coding in python. I think the fact that every variable in python should be initialized first(at least with None) makes it slower further, specially when it comes to declaring a list of a fixed length beforehand to be able to assign value at any arbitrary index. Any suggestion to optimize the code is welcome.

@snk967 I had a small attempt at speeding up your Python version. There are a couple of things that you can do to make it faster but I didn’t manage to get it passing the time limit.

One is using range instead of xrange. I didn’t see any noticeable improvement but according to the last paragraph of the first section of this link it can make a difference when repeatedly using the same range. range vs xrange

The second thing that can be done is to initialise your array slightly differently.

C=[[0] * LIMIT for _ in xrange(2*LIMIT+1)]

The above code does the same as what you were doing but instead of two loops it just repeats 0 Limit + 1 times. This did improve performance but no by enough to pass either of the failing cases.

Maybe someone else can give some better performance improvements.

1 Like

I am very glad that you gave it a try. Perhaps, we needed another algorithm (and some tricks) like this solution in python3.