472,378 Members | 1,648 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 472,378 software developers and data experts.

Time Complexity of String Operations

It has been extensively discussed the time complexity (quadratic) of
string concatenation (due to string's immutability).
But what is:

== the time complexity of string indexing? Is it constant?
== the time complexity of string slicing? Is it O(K) with K the
slice's length?

How are strings stored in Python? As arrays? As linked lists?

Thanks a lot!

yt.
Jul 22 '08 #1
3 11144
On Mon, Jul 21, 2008 at 10:31 PM, youtoo <yo********@gmail.comwrote:
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
Jul 22 '08 #2


youtoo wrote:
It has been extensively discussed the time complexity (quadratic) of
string concatenation (due to string's immutability).
But what is:

== the time complexity of string indexing? Is it constant?
== the time complexity of string slicing? Is it O(K) with K the
slice's length?

How are strings stored in Python? As arrays? As linked lists?
There is a Py wiki page on such issues. A wiki search should find it.

Jul 22 '08 #3

On 22 jul, 01:39, "David Wahler" <dwah...@gmail.comwrote:
On Mon, Jul 21, 2008 at 10:31 PM, youtoo <you2000...@gmail.comwrote:
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.
Jul 22 '08 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

3
by: Edg Bamyasi | last post by:
This Is A Late Cross Post from comp.lang.python. It seems the mistery is deeper then i expected. What is the running time of conactination on character strings. i.e. >> joe="123" >>...
4
by: GiriT | last post by:
Would appreciate some insight into how people are dealing with the implicit conversion of timezones that .NET does. If a server in one timezone delivers up a typed dataset to a component in...
12
by: pjhyett | last post by:
standard 2d array filling with increasing numbers for rows and columns: for(int i=0;i<n;i++) for(int j=0;j<n;j++) a = i + j; problem is it's O(n^2). I'm looking for a method to decrease the...
26
by: Lionel B | last post by:
Hi, Anyone know if the Standard has anything to say about the time complexity of size() for std::set? I need to access a set's size (/not/ to know if it is empty!) heavily during an algorithm...
12
by: toton | last post by:
Hi, I am reading a big file , and need to have a flag for current file position so that I can store the positions for later direct access. However it looks tellg is a very costly function ! But...
33
by: desktop | last post by:
In the C++ standard sec 23.1.2 table 69 it says that erase(q) where q is a pointer to an element can be done in amortized constant time. I guess that is not worst case since std::set is...
2
by: OuaisBla | last post by:
What I'd like to do and what I tought possible was to have a deque of string when the string was a reference (not a pointer) Then I simply tried: std::deque<std::string const &> mFifo; But,...
1
by: dondora | last post by:
hi there. this is my homework. I've been trying to get some result but things haven't been gone well. Those are the nested loop. And What I have to do is to get time complexity T(n) of the nested...
10
by: WebCM | last post by:
There is a function: http://paste.ubuntu.com/21865 It needs GMT date in YYYY-MM-DD HH:MM:SS format - in SQL: datetime. If date is the same as today, the function returns "Today". There is one...
2
by: Kemmylinns12 | last post by:
Blockchain technology has emerged as a transformative force in the business world, offering unprecedented opportunities for innovation and efficiency. While initially associated with cryptocurrencies...
0
by: antdb | last post by:
Ⅰ. Advantage of AntDB: hyper-convergence + streaming processing engine In the overall architecture, a new "hyper-convergence" concept was proposed, which integrated multiple engines and...
0
hi
by: WisdomUfot | last post by:
It's an interesting question you've got about how Gmail hides the HTTP referrer when a link in an email is clicked. While I don't have the specific technical details, Gmail likely implements measures...
0
Oralloy
by: Oralloy | last post by:
Hello Folks, I am trying to hook up a CPU which I designed using SystemC to I/O pins on an FPGA. My problem (spelled failure) is with the synthesis of my design into a bitstream, not the C++...
0
by: Carina712 | last post by:
Setting background colors for Excel documents can help to improve the visual appeal of the document and make it easier to read and understand. Background colors can be used to highlight important...
0
by: Rahul1995seven | last post by:
Introduction: In the realm of programming languages, Python has emerged as a powerhouse. With its simplicity, versatility, and robustness, Python has gained popularity among beginners and experts...
2
by: Ricardo de Mila | last post by:
Dear people, good afternoon... I have a form in msAccess with lots of controls and a specific routine must be triggered if the mouse_down event happens in any control. Than I need to discover what...
1
by: Johno34 | last post by:
I have this click event on my form. It speaks to a Datasheet Subform Private Sub Command260_Click() Dim r As DAO.Recordset Set r = Form_frmABCD.Form.RecordsetClone r.MoveFirst Do If...
1
by: ezappsrUS | last post by:
Hi, I wonder if someone knows where I am going wrong below. I have a continuous form and two labels where only one would be visible depending on the checkbox being checked or not. Below is the...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.