Блог пользователя Pranava23

Автор Pranava23, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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.

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.