[pypy-issue] Issue #2186: PyPy vs CPython2 O(N^2) vs O(N) (pypy/pypy)

Roman Sinayev issues-reply at bitbucket.org
Mon Nov 9 22:59:17 EST 2015

New issue 2186: PyPy vs CPython2 O(N^2) vs O(N)

Roman Sinayev:

String concatenation seems to involve copying the whole string, while in Python2 people tend to simply add substrings. Example program:

import random
import time

def timing(f):
    def wrap(*args):
        time1 = time.time()
        ret = f(*args)
        time2 = time.time()
        print('%s function took %0.3f ms' % (f.__name__, (time2-time1)*1000.0))
        return ret
    return wrap

def test():
    s = b''
    for i in range(1*1000*1000):
        c = chr(random.randint(1,128))
        s += c
    return s

if __name__=='__main__':

More information about the pypy-issue mailing list