CODEWITHSUNDEEP
pythonstringconcatenation
malanb5
malanb5

Reputation: 314

String Concatenation to Prevent Movement of Two Strings In Memory

To concatenate two strings, the memory manager will try to realloc one the memory location of one string so that the other will be able to fit the other string in memory next to it. https://stackoverflow.com/a/34008199/8366477Is the time-complexity of iterative string append actually O(n^2), or O(n)? If it cannot realloc in place, then it will have to move both into a new memory location.

Question is to avoid this overhead of moving two strings into a new memory location, is there a preferred, efficient way of concatenating two strings in Python. I'm thinking of using StringIO to make it into a text buffer? What are your thoughts?

Upvotes: 0

Views: 415

Answers (1)

ShadowRanger
ShadowRanger

Reputation: 155506

For just two strings, big-O is irrelevant, as there is nothing you can do to improve it. a + b is fine; you can't amortize the growth, so you can just concatenate them, performing one allocation for the new string, and two copies into that single allocation, one from each source.

For a larger number of strings, the standard Python approach is to make a tuple (for many strings known at once) or list (for a set of strings built up piecemeal) and call ''.join(seq) on it. str.join computes the combined lengths of all the inputs, preallocates the buffer for the result, and copies each component into that buffer, one after another, keeping the runtime O(n).

You could use io.StringIO to achieve a similar effect, but it's not necessary, and under the hood, it has to do similar work to building up a list and joining it.

Upvotes: 5

Related Questions