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

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

Can any one explain for 2003C - Черепаха и хорошие пары, why PyPy3-64 is being slower here 278391142 and getting TLE and also the memory limit, when the same code works fine with Python3 here 278391153. Thought PyPy always works faster than Python, what am I missing?

import sys
input = lambda: sys.stdin.readline().strip()

for _ in range(int(input())):
    n = int(input())
    s = input()
    a = [0] * 26
    
    for i in range(n):
        a[ord(s[i]) - ord('a')] += 1

    res = ""

    while True:
        tempval = 0
        for i in range(26):
            if a[i] != 0:
                res += chr(i + ord('a'))
                a[i] -= 1
                tempval = 1
        if tempval == 0:
            break

    print(res)

Never faced such issue till now with PyPy3-64 :( Any help from experienced python coders, I'd be greatful!

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

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

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

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

it's better to use res as a list, then .append each char to it. Then print(''.join(res)).

reason: list.append takes $$$\mathcal{O}(1)$$$, while string concatenation takes $$$\mathcal{O}(len(s))$$$

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

    Yeah, I've realized this after the contest and would not repeat such mistake later. But I've just been thinking if it passes with Python3, why didnt it with Pypy!

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

    Yes, you are right. I've experienced the same problem with strings once.

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

Python 3 is heavily optimized on strings, and you call print up to $$$10^4$$$ times, which can tap into this optimization. For instance, the code

s=''
for i in range(400000):s+='a'

runs in 139ms on Python 3, and 10890ms on PyPy 3.

Unforunately, Python 3 is slower in just about every other way, so it's probably not worth using.