Sometimes a string contains multiple consecutive spaces, which may be undesirable for further processing. Our goal is therefore to transform the string so that every sequence of two or more consecutive spaces is replaced with a single space character. Let’s write a function to accomplish this.
As is often the case, there is more than one way to solve a problem. Below, you can see four different implementations, each following a different approach and making use of different Python features.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
from itertools import groupby def collapse_spaces1(text: str) -> str: # Loop-based solution using the str.replace() method. while ' ' * 2 in text: text = text.replace(' ' * 2, ' ') return text def collapse_spaces2(text: str) -> str: # Recursive solution using the str.replace() method. # The recursion depth depends not on the length of the text, but on the length of the longest # consecutive sequence of spaces. Therefore, it is practically impossible to exceed # Python's default recursion limit of 1000 calls. if ' ' * 2 not in text: return text return collapse_spaces2(text.replace(' ' * 2, ' ')) def collapse_spaces3(text: str) -> str: # Solution based on character-by-character processing. result = [] prev_space = False for c in text: if c == ' ': if not prev_space: result.append(c) prev_space = True else: result.append(c) prev_space = False return "".join(result) def collapse_spaces4(text: str) -> str: # Solution using the itertools.groupby() function. return "".join(' ' if c == ' ' else ''.join(group) for c, group in groupby(text)) |
The first function checks whether the string contains two consecutive spaces. If it does not, the string already satisfies our requirement. Otherwise, every occurrence of two consecutive spaces is replaced with a single space by calling the replace() method. The process is then repeated, because the original string may have contained sequences longer than two spaces.
The second function follows exactly the same logic, but uses recursion instead of a loop. Whenever recursion is involved, it is important to consider the maximum possible recursion depth, as otherwise we might exceed Python’s default recursion limit (1000 calls). In this case, however, that is not a concern because the recursion depth depends not on the length of the string, but on the length of the longest sequence of consecutive spaces. In real-world text, such sequences are typically too short to exceed Python’s default recursion limit.
These first two functions have relatively simple logic and concise implementations, but they share one drawback: they may need to traverse the input string multiple times. The third function eliminates this by scanning the input only once. Whenever it encounters multiple consecutive spaces, it keeps only a single space in the output string. The trade-off is that the implementation is longer and less straightforward, making it both more time-consuming to write and somewhat harder for readers to understand. On the other hand, because it processes the input in a single pass, we would expect it to be faster.
The fourth function uses the groupby() function from the itertools module to produce the desired result in a single line of code. Although this solution is remarkably concise, it is arguably less readable because its behavior is not immediately obvious. However, according to the official Python documentation, the tools provided by itertools are designed to be both fast and memory-efficient, as they are implemented in C within CPython. Based on this, we might expect this solution to outperform at least the first two implementations.
The benchmark results, however, tell a different story, as shown below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
from timeit import timeit def test_time_performances(text, *functions): for func in functions: print('{} -> {:.5f}'.format(func.__name__, timeit(lambda: func(text), number=1000))) print() tested_functions = [collapse_spaces1, collapse_spaces2, collapse_spaces3, collapse_spaces4] txt = ' A bb c d\n efg \tf g h i ' test_time_performances(txt, *tested_functions) # Output: # collapse_spaces1 -> 0.00042 # collapse_spaces2 -> 0.00047 # collapse_spaces3 -> 0.00153 # collapse_spaces4 -> 0.00503 txt = ('ab cd ef gh ' * 5000) test_time_performances(txt, *tested_functions) # Output: # collapse_spaces1 -> 0.55371 # collapse_spaces2 -> 0.55463 # collapse_spaces3 -> 3.18906 # collapse_spaces4 -> 11.7909 txt = 'a' + ' ' * 1000 + 'b' test_time_performances(txt, *tested_functions) # Output: # collapse_spaces1 -> 0.01070 # collapse_spaces2 -> 0.01074 # collapse_spaces3 -> 0.02245 # collapse_spaces4 -> 0.00776 |
While the character-by-character solution and the groupby()-based implementation both have linear time complexity (O(n)), the algorithms based on str.replace() may traverse the string multiple times and therefore have less favorable theoretical complexity. In practice, however, str.replace() is so heavily optimized in CPython that these implementations turned out to be the fastest in most of the tested scenarios. The solution using groupby() outperformed them only in special cases where the input contained one or more very long runs of consecutive space characters. Since such input is uncommon in real-world applications, the solutions based on str.replace() are generally the best choice.
You might also wonder why we do not use the split() method instead and simply write: ' '.join(text.split()). After all, when split() is called without an argument, consecutive whitespace characters are treated as a single delimiter.
There are two reasons. First, this approach does not always produce the desired result. The split() method treats not only the regular space character (U+0020) as whitespace, but also characters such as ‘\n’, ‘\t’, ‘\r’, and ‘\f’. Second, any leading or trailing spaces are removed by split(), which may not be what we want.
If you would like to learn more about string methods—including replace() and split()—see the chapter “Public Methods of Built-in Types” in the ebook Python Knowledge Building Step by Step From the Basics to Your First Desktop Application. The section “When the Snake Bites Its Tail – Function Recursion” of the chapter “Special Function Definitions” provides an introduction to recursion. Finally, the section “Special Iterators” of the chapter “Using the Standard Library Modules” presents the tools available in the itertools module along with practical examples. If you are interested in measuring execution time, see the section “Suspending Program Execution and Measuring Elapsed Time”.