String Traversal and Immutability

String Traversal and Immutability — Tech Epitome

Immutability and its cost

In most languages a string cannot be modified after it is created. Concatenation therefore allocates a new string and copies both operands into it.

python

1# Quadratic: each += copies everything accumulated so far2def build_slow(chars):3    out = ""4    for char in chars:5        out += char        # allocates a new string every iteration6    return out7 8 9# Linear: collect the pieces, join once10def build(chars):11    pieces = []12    for char in chars:13        pieces.append(char)14    return "".join(pieces)

The same result, very different cost

Language	Buffer to use
Python	a list plus "".join(...)
Java	StringBuilder
C++	std::string with += (already amortised)
JavaScript	an array plus .join("")

Building strings without the copy.

Indexing and searching

String operations and their real costs.
Operation	Time	Space
Read character at index	O(1)	O(1)
Length	O(1)	O(1)
Concatenate	O(n + m)	O(n + m)
Substring / slicecopies in most languages	O(k)	O(k)
Search for a substring	O(n · m) naive	O(1)

String operations and their real costs.

Quick quiz

Strings and immutability

1What is the right way to build a long string in a loop?

Repeated += concatenation

Collect the pieces and join once at the end

Use recursion

Preallocate with spaces and overwrite

2Taking a substring is always an O(1) operation.

True

False