O(n^2) string concatenation

[shmulvad]

Hi,

I randomly came across your blog post on this library and thought I'd take a look at the code. I noticed you have an accidental O(n^2) string concatenation. In a few places in your code, you're appending lists of strings. This is a problem as it creates new intermediate strings in each iteration. Here is one such example:

Fontimize/fontimize.py

Lines 186 to 190 in 317f1e1

	def optimise_fonts_for_html_contents(html_contents : list[str], fonts : list[str], fontpath : str = "", subsetname = "FontimizeSubset", verbose : bool = False, print_stats : bool = True) -> dict[str, typing.Any]:
	text = ""
	for html in html_contents:
	soup = BeautifulSoup(html, 'html.parser')
	text = text + soup.get_text()

A more efficient way to write the above would be something like the following as it creates a single new string object:

text = ''.join(BeautifulSoup(html, 'html.parser').get_text() for html in html_contents)

[vintagedave]

This is fantastic feedback; thank you. As you probably saw in the blog post, I'm fairly new to Python, and I've avoided some of the one-liners you tend to see because they take more work to understand when reading code. But what I wasn't aware of was that they were not functionally identical (that is, I thought a short one-liner version was the "same" in behaviour as the longer written out logic.)

So this is educational -- and as you say, a good spot for improvement. I will integrate it. Thankyou :)

[shmulvad]

Thanks, you're welcome. It's not the fact that it is a one-liner that makes it more efficient, but the ways the strings are concatenated. If you wanted to keep it looking more like your original code, you could do the following:

texts = []
for html in html_contents:
     soup = BeautifulSoup(html, 'html.parser')
     texts.append(soup.get_text())
text = ''.join(texts)

Note that the above is slightly less memory efficient than the one-liner since the intermediate strings are stored in a list rather than coming from a generator expression. You could also rewrite the multiline example into a generator expression, but I won't go into details here.

You should definitely not make everything a one-liner. Some of the examples you give in your blog post are better left as multiple lines. However, I think that in this case the one-liner is more readable than multiple lines.