0

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?

malanb5
  • 304
  • 2
  • 13
  • If you have exactly two strings, then the question is meaningless. Big-O notation is only useful when N is actually able to scale. While it's true that *longer* strings will take more time to process, nothing you can do will change that. It is not always possible to reallocate more memory *in place*, so things like StringIO can't really help. – Karl Knechtel Jun 06 '20 at 01:43
  • Thanks @KarlKnechtel for the explanation! – malanb5 Jun 06 '20 at 04:05

1 Answers1

5

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.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271