Shuaib's blog

Python vs. C++
By Shuaib, 13 years ago, In English

It is a bit unfortunate that a solution to problem D in round-85 (div2) implemented in C++ passes system tests, but same solution implemented in Python times out on test case 40. Does that mean Python isn't a good pick for such time constrained problems?


C++:

int main()
{
    int n; cin>>n;
    int f[100001]; for(int i=0;i<100001;i++) f[i] = -100000;
    for(int i=0;i<n;i++)
    {
        int x, y;
        cin>>x>>y;
        int r = 0;
        for(int j=1;j*j<=x;j++)
        {
            if(x%j==0)
            {
                int p = x/j;
                int q = j;
                if(f[p]<i-y)
                    r++;
                f[p] = i;
                if(f[q]<i-y)
                    r++;
                f[q] = i;
            }
        }
        cout<<r<<endl;
    }
    return 0;
}

Python:

import math

n = int(raw_input())
f = [-100000 for i in range(0, 100001)]
for j in range(0, n):
    x, y  = tuple(int(i) for i in raw_input().strip().split(" "))
    c = 0
    for i in xrange(1, int(math.sqrt(x)+1)):
        if x%i==0:
            q = x/i
            p = i
            if(f[p]<j-y):
                c+=1
            f[p] = j 
            if(f[q]<j-y):
                c+=1
            f[q] = j
    print c

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
http://shootout.alioth.debian.org/
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think Python is simply too slow for that, my similar solution in Java took 450 ms, and I have pretty optimized input reading... Python can be around 5-30 times slower than Java (depending on task), so do the math... This is a biggest drawback of Python on contests, I don't recommend it for that reason.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
It is not "unfortunate". You just should assess "timing complexity" of the problem when you start implementing its algorithm. If you find that you need to perform about 10e7 operations on array elements, for example, you just should not try to write this in any scripting language. You may even fail with java. It is very common issue - because of that TopCoder does not allow python in SRMs (only in Marathons if I remember correctly).

However in some cases it may happen that you've missed some better approach to the problem.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why we should afford this consuming time? as for java : Java Virtual Machine needs to start 30 ms as i read before, Is that fair? the same 2 codes in java and C++ one passes and the other fails . USACO ignores this consuming time. I hope that 0.5 secs be added to the problems for java and Python codes :(
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Java not only start slower, but also work slower. It is not wonder.

      It is not honest to give more time for java/python programmers. Imagine the light athletics competition. If some sportsman prefer to wear foot fins instead of normal shoes - does it mean that all other sprinters should give him more time?

      I personally use java, but I never would complain about TLE for my solutions. My favorite language is my choice and it is my responsibility!

      And by the way remember - Petr uses Java - and wins anyway!
      → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    You are right actually. One has to be aware of the slowness of a particular language and take care that it doesn't cause a T.E. Though I wonder if like Topcoder, CF should also disallow such slow languages.
    → Reply
13 years ago, # |
← Rev. 9   Vote: I like it 0 Vote: I do not like it

It works fine actually. :)

Take a look: codeforces.com/problemset/status/112/D


Your fixed code near the top with (search for gorlum0) 3.5s and my own with 2s.


This might help for example.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Right. But this isn't very healthy. When you have to worry about language specific optimizations, and not algorithmic optimisations, it hints something isn't right (I guess in this case the choice of language).
    → Reply