Performance deep dive

In this article, we'll find out how to most efficiently form an acronym from an input string.

The approaches page lists many idiomatic approaches to this exercise:

1. Using a loop
2. Using a list-comprehension
3. Using functools.reduce()
4. Using map()
5. Using a generator-expression
6. Using re.finditer() with str.join()
7. Using re.findall() with str.join()
8. Using re.sub()
9. Using two generator-expressions and str.join()

We will also include a tenth approach, which is a variant of the re.findall() approach. This variant uses a regex to select the first letters of each word, instead of the entirety of each word.

Benchmarks

To benchmark these approaches, we wrote a small benchmarking script using the timeit module along with the third party libraries numpy and pandas.

All approaches are O(n) — they require (at minimum) a loop through the entire input to create results, and the work scales in line with the length of the function input. That doesn't mean that all of these approaches take the same amount of time to run. Despite being O(n), overhead such as number of function calls, module importing/loading, regex backtracking, generator tracking, string concatenation, and lambda evaluation can add significant time. Some of the slowest strategies (mostly regex solutions) are 5 (or more) times times slower than the fastest methods (straight looping and list comprehensions).

Of these variants, the loop approach is by far the fastest (and easiest to read) for inputs under length 45. Above length 45, repeated string creation and concatenation via + starts to slow things down, and the list-comprehension approach becomes more efficient due to its loop optimizations and use of str.join().

At the largest input sizes, map() and generator expressions become more efficient (as does functools.reduce() for certain inputs), as they are not saving intermediary results to memory in the same way list comprehensions or string concatenation do.

Among the least efficient and least readable are the regex solutions. While regex definitely has its place, the lack of readability and significant slowdown in this case become an issue. Of particular interest is the re.sub() vs re.findall() (first letters) solutions. Even though the re.sub() solution takes only 652 steps in the regex engine, re.sub() and its unpacking is slow enough that the 1766 steps for the first letters re.findall() solution is often faster.

Keep in mind that all these approaches are very fast, and that benchmarking at this granularity can be unstable, especially on modern CPUs. Note that there can also be bias in benchmarking.

Measurements were taken on an M3 Mac running MacOS Sonoma. Tests used timeit.Timer.autorange(), repeated 3 times. Time is reported in seconds taken per string after calculating the 'best of' time. The timeit module docs have more details, and note.nkmk.me has a nice summary of methods.