On 22 jul, 01:39, "David Wahler" <[EMAIL PROTECTED]> wrote: > On Mon, Jul 21, 2008 at 10:31 PM, youtoo <[EMAIL PROTECTED]> wrote: > > It has been extensively discussed the time complexity (quadratic) of > > string concatenation (due to string's immutability). > > Actually, it is roughly linear, at least for reasonable string lengths: > > $ python -V > Python 2.5.2 > $ python -mtimeit -s "n=1000; a='#'*n" "a+a" > 1000000 loops, best of 3: 1 usec per loop > $ python -mtimeit -s "n=10000; a='#'*n" "a+a" > 100000 loops, best of 3: 5.88 usec per loop > $ python -mtimeit -s "n=100000; a='#'*n" "a+a" > 10000 loops, best of 3: 59.8 usec per loop > > Repeatedly constructing a string by appending a constant number of > characters at a time, however, is quadratic in the final string length > (although VM optimizations may affect this). > > > But what is: > > > == the time complexity of string indexing? Is it constant? > > Yes. > > > == the time complexity of string slicing? Is it O(K) with K the > > slice's length? > > I suspect so, since the time is dominated by the time taken to copy > the data into a new string object. > > > How are strings stored in Python? As arrays? As linked lists? > > Arrays; see Include/stringobject.h in the Python source distribution. > > -- David
Thank you very much! yt. -- http://mail.python.org/mailman/listinfo/python-list
