We know we can use sep.join() or = to concatenate strings. For example,

a = ["123f", "asd", "y]
print("".join(a))
# output: 1234asdy

In Java, stringbuilder would creat a new string, and put the two string on the both sides of plus together, so it will cost O(n^2). But in Python, how will join method do for multiway merge?
A similar question is How python implements concatenation? It explains = for two way merge.

CodePudding user response：

for cpython version 3.X you can see the source code here and it does indeed calculate the total length beforehand and only does 1 allocation.

On a side note, if your application is limited by the speed of joining strings such that you have to think about join implementation then you shouldn't be using python, and instead go for c .

CodePudding user response：

The operation is O(n). join takes an iterable. If its not already a sequence, join will create one. Then, using the size of the the separator and the size of each string in the list, a new string object is created. A series of memcpy then creates the object. Creating the list, getting the sizes and doing the memcpy are all linear.

= is faster and still O(n). A new object the size of the two strings to be concatenated is created, and 2 memcpy do the work. Of course it is only concatenating two strings. If you want to do more, join soon becomes the better option.