python - Why are Lists faster than character arrays for string concatenation -

in article linked below, author compares efficiency of different string concatenation methodologies in python: http://www.skymind.com/~ocrow/python_string/

one thing did not understand is, why method 3 (mutable character arrays) result in slower performance method 4 (joining list of strings)

both of them mutable , think should have comparable performance.

"both of them mutable" misleading bit.

it's true in list-append method, list mutable. building list isn't slow part. if have 1000 strings of average length 1000, you're doing 1000000 mutations array, 1000 mutations list (plus 1000 increfs string objects).

in particular, means array have spend 1000x time expanding (allocating new storage , copying whole thing far).

the slow part list method str.join call @ end. isn't mutable, , doesn't require expanding. uses 2 passes, first calculate size needed, copy it.

also, code inside str.join has had (and has continued have since article written 9 years ago) lot of work optimize it, because it's common, , recommended, idiom many real programs depend on every day; array has barely been touched since first added language.

but if want understand differences, have @ source. in 2.7, main work array method in array_fromstring, while main work list method in string_join. can see how latter takes advantage of fact know of strings we're going joining @ start, while former can't.