tomowama's blog

How competitive is PyPy 64-bit?
By tomowama, history, 20 months ago, In English

I am rather new to CP, and am curious that now that there is PyPy 64-bit on Codeforces, how much more competitive does that make python? I have seen in other blog posts on here that one of the main things slowing down python (PyPy) was the fact that >32 bit integers were being stored as big ints. Does this change make Python more competitive and actually usable? I only ask because I know c++ and python (I know python better than c++ as I've only recently been using c++ for cp), but can code solutions to problems much faster and "cleaner" in python.

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

Comments Comments (10)
| Write comment?
»
20 months ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

PyPy is fairly competitive. I solve most problems with PyPy and I know that others do too, such as pajenegod.

However, there are issues with problems with tight time limits where pythonic Python isn't fast enough and you have to use crab-Python, which can take some time to learn. Techniques in crab-Python involve flattening multidimensional lists to 1 dimension and manually performing index arithmetic, packing tuple elements into 64-bit ints before sorting because sorting ints is 10x faster than sorting tuples, finding ways to avoid dicts and sets, coping with the lack of balanced search trees (segment trees are nice if you can afford the space), and programming recursion with an explicit stack because recursion is too slow.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    shoutout to kclee2172 for being a Python god

    → Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Sounds difficult. Is it really still simpler than C++?)

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It depends on how stubborn you are.

      A good skill to have is to be able to judge from the limits and your expected solution whether you might experience issues with the time limit in Python. When this is the case you can opt to use C++ instead of Python.

      Generally I find that Python solutions are shorter and therefore faster to type than C++ solutions, which is why I prefer it.

      → Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Up to the rank of specialist, which is the highest I reached, you can use python without any major concerns, although there are a few things you have to take into account:

  • You need to use fast input if the problem requires you to read over 10⁵ elements and integer values up to 10⁹, otherwise your solution will probably get a TLE. You can use a template and forget about it.

  • If you use a dictionary and integers can be up to 10⁹ your solution can be hacked see https://mirror.codeforces.com/blog/entry/101817.

  • You can't generally use recursion.

  • Sometimes I've missed a balanced search tree although I have been able to use a BIT.

→ Reply
  • »
    »
    20 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you for your response!

    so you can’t really use normal dictionaries for large ints?

    since you aren’t using recursion, how are you handling tree algorithms?

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Sometimes recursion will work, it will depend on the constraints of the problem, but you have to be aware more often than not it will be too slow.

      Truth is you won't face many tree problems at those ranks, I only recall a D problem in a DIV3 contest, anyways for a tree if you want a inorder or postorder traversal you can use a stack to emulate the recursion, if you want a preorder traversal you can use a deque.

      → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        array-based queue: exists

        → Reply
        • »
          »
          »
          »
          »
          20 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          To the level I solve problems I never had the need to move to more efficient techniques but the other day I saw this https://mirror.codeforces.com/blog/entry/102802 and I assumed in PyPy you don't win much by using arrays. Do you have a different experience?

          → Reply
          • »
            »
            »
            »
            »
            »
            20 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh, sorry, I meant a list. Python keywords are confusing to a C++/Python mixed user aaaaaaaa

            → Reply