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 seven 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()

We'll include a ninth approach using re.findall() with a regex to select the first letters of each word, and str.join() to make the acronym.

Benchmarks

To benchmark these approaches, we wrote a small benchmarking script using the timeit module along with the third party libraries numbpy 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 run time. 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 10x or more times slower than the fastest methods (straight looping and list-comprehensions).

Of these variants, the loop approach is by far the fastest (and easiest 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.

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 faster.

Keep in mind that all these approaches are very fast, and that benchmarking at this granularity can be unstable.

Measurements were taken on a 3.1 GHz Quad-Core Intel Core i7 Mac running MacOS Ventura. 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.