I am reading one of Guido van Rossum's essays on optimization in Python.

We are interested in converting a Python list of integers to their character equivalents. Here's the straightforward algorithm.

def f3(list):
    string = ""
    for character in map(chr, list):
        string = string + character
    return string

Guido claims that the following algorithm avoids the quadratic behavior in the string concatenation.

def f5(list):
    string = ""
    for i in range(0, 256, 16): # 0, 16, 32, 48, 64, ...
        s = ""
        for character in map(chr, list[i:i+16]):
            s = s + character
        string = string + s
    return string

How does this actually help and what is the significance of the value 16 in f5?

f5 does not actually turn out to be faster, but I want the intuition that went into trying this strategy of optimization.

Note: we can assume that we are working with a list of length exactly 256.

  • 2
    $\begingroup$ Note: This essay is ancient. I don't know how ancient, but it looks like it dates back to about 1994-1996. It definitely predates Python 1.5 (since the B typecode in the array module was added after it was written), and it probably predates Python 1.4 (since it uses string.joinfields instead of string.join or str.join). A modern Python programmer would probably jump to ''.join(map(chr, l)) in seconds. $\endgroup$ – user2357112 Jan 28 '16 at 0:05
  • $\begingroup$ Using append with strings in place of creating new ones by + should be faster. $\endgroup$ – Kaveh Feb 20 '16 at 2:19

Let's assume that adding two strings of lengths $a,b$ takes time $a+b$. Consider the following strategy to convert a list of $n$ characters into a list:

Read the list in chunks of $k$, convert them to strings, and sum the chunks.

Creating each chunk takes time $\Theta(1+2+\cdots+k) = \Theta(k^2)$, and we do this $n/k$ times, for a total of $\Theta(nk)$. Adding the chunks takes time $\Theta(k+2k+\cdots+n) = \Theta(k(1+2+\cdots+n/k)) = \Theta(k(n/k)^2) = \Theta(n^2/k)$. In total, we get a complexity of $\Theta(n(k+n/k))$. The optimal choice of $k$ is $\sqrt{n}$, and this gives a complexity of $\Theta(n^{3/2})$. In contrast, the trivial algorithm has $k = 1$ and so complexity $\Theta(n^2)$.

More generally, you can consider $d$ levels of recursion. Let $f_d(n)$ denote the optimal complexity of such a scheme, measuring just the merging steps. Clearly $f_1(n) \approx n^2/2$. Given an algorithm with $d$ levels, we can construct a $d+1$-level algorithm which cuts the input into chunks of length $k$, runs the $d$-level algorithm on each of them, and concatenates the result. This takes time roughly $(n/k)f_d(k) + n^2/2k$. For example, $$ \begin{align*} 2f_2(n) &\approx \max_k nk + n^2/k \approx 2n^{3/2} & (k=\sqrt{n}), \\ 2f_3(n) &\approx \max_k 2nk^{1/2} + n^2/k \approx 3n^{4/3} & (k=n^{2/3}), \\ 2f_4(n) &\approx \max_k 3nk^{1/3} + n^2/k \approx 4n^{5/4} & (k=n^{3/4}). \end{align*} $$ We get that $2f_d(n) \approx dn^{(d+1)/d}$. Calculus shows that the best choice of $d$ is $d = \log n$, in which case we obtain $2f_{\log n}(n) = \Theta(n\log n)$. However, this scheme is not necessarily achievable.

If we choose a branching factor of 2 then we get an algorithm whose running time is $\Theta(n\log n)$ which resembles merge sort. In fact, the sorting lower bound gives a lower bound of $\Omega(n\log n)$ on any such merging procedure.

We can also prove the lower bound directly. For a sequence $\sigma_1,\ldots,\sigma_m$ of chunk lengths summing to $n$, define its potential by $$ \Phi(\vec\sigma) = nH(X_{\vec\sigma}), \text{ where } \Pr[X_{\vec\sigma} = i] = \frac{\sigma_i}{n}. $$ Here $H$ is the entropy function.

The potential function starts at $\Phi(1,\ldots,1) = n\log n$ and ends up at $\Phi(n) = 0$. Suppose that $\vec\tau$ is obtained from $\vec\sigma$ by merging $\sigma_i$ and $\sigma_j$ to a new chunk $\tau_k$. We can sample $X_{\vec\sigma}$ by first sampling $X_{\vec\tau}$, and if the result is $k$, sample according to the marginal distributions $\frac{\sigma_i}{\sigma_i+\sigma_j},\frac{\sigma_j}{\sigma_i+\sigma_j}$. Calculation shows that $$ \begin{align*} \Phi(\vec\sigma) = nH(\vec\sigma) &= nH(\vec\tau) + n\Pr[X_{\vec\tau}=k] h\left(\frac{\sigma_i}{\sigma_i+\sigma_j}\right) \\ &= \Phi(\vec\tau) + (\sigma_i+\sigma_j) h\left(\frac{\sigma_i}{\sigma_i+\sigma_j}\right) \\ &= \Phi(\vec\tau) + O(\sigma_i+\sigma_j). \end{align*} $$ Here $h$ is the binary entropy function.

This shows that the potential difference is a lower bound on the running time. Since the overall potential difference is $n\log n$, we obtain a lower bound of $\Omega(n\log n)$. Furthermore, the calculation shows that it's best to always merge chunks of identical size.

  • $\begingroup$ This makes sense, thanks. Would it make sense to chunk the chunks then -- is there an easy to see lower bound to this algorithm? $\endgroup$ – bourbaki4481472 Jan 27 '16 at 20:09
  • 1
    $\begingroup$ Try it out yourself and see if it improves. $\endgroup$ – Yuval Filmus Jan 27 '16 at 20:18
  • $\begingroup$ Looks like if you chunk the chunks, the complexity is $\Theta(n^{4/3})$. $\endgroup$ – bourbaki4481472 Jan 27 '16 at 20:41
  • 1
    $\begingroup$ Try doing it recursively $\log n$ times. $\endgroup$ – Yuval Filmus Jan 27 '16 at 20:43
  • 1
    $\begingroup$ That's exactly right. $\endgroup$ – Yuval Filmus Jan 27 '16 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.