Pranava23's blog

By Pranava23, history, 5 weeks ago, In English

I submitted a fairly easy question with N(log(N)) complexity and N<=10^5 which as per theory should pass all test case with a time limit of 1sec. I got TLE in PyPy3 which supposedly runs faster ("Almost always, if you send a solution on PyPy, it works much faster") but the same solution got accepted in Python3.

Can someone please explain the logic and reason behind the same?

Question

PyPy3 Solution

Python3 Solution

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Pranava23 (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You are repeatedly doing pop(0) which takes O(n) per pop call. I'm not entirely sure why PyPy3 is slower here but the TLE is not really Python's fault.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I used a simple iteration instead of the pop operation and the solution passed in both PyPy3 and Python3 but still, it was a bit faster in Python3 I don't know the reason behind the same, is there any reason for the same? Thank you:)

    PyPy3

    Python3

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      CPython has faster built in input and output compared to PyPy. If you want faster IO in PyPy then you can use something like this.

      Back to why pop(0) was slower in PyPy than in CPython. Found this issue reported 4 months ago that has now been fixed. So whenever Codeforces updates its PyPy version, the solution with pop(0) should hopefully no longer TLE in PyPy.

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

The key word here is almost. The differences between Python3 and PyPy3 are complicated (and honestly I don't really know anything about them). But you can't really make a blanket statement about one always being faster than the other, which is why CF adds "almost" to their message.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

so what is the conclusion ?