Time Complexity of String Operations

[youtoo]

On 22 jul, 01:39, "David Wahler" <dwah... at gmail.com> wrote:
> On Mon, Jul 21, 2008 at 10:31 PM, youtoo <you2000... at gmail.com> 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.