Python - Iterating over contents of BeautifulSoup element very slow

Question

I have a large HTML document where everything is inside a main div, structured like this:

<div class="main">
    \\block 1
    <div class="header"><span>content1a</span><span>content1b</span></div>
    <p>content1c</p>

    \\block 2
    <div class="header"><span>content2a</span><span>content2b</span></div>
    <p>content2c</p>

    ...
</div>

As you can see the contents of the header divs are related to the paragraphs, so my Python code separates these tag blocks into lists of a list so I can take out their contents later:

main_div = soup.find("div", class_="main")
headers = main_div.find_all("div", class_="header")

all_blocks = []
current_block = []

for tag in main_div.contents:
    if tag in headers:
        all_blocks.append(current_block)
        current_block = [tag]
    else:
        current_block.append(tag)

all_blocks.append(current_block)  # append final block
all_blocks = all_blocks[1:]  # take off first empty list

Problem is this seems to take forever on a ~12MB HTML file I'm feeding it (less than 1% done after 1h, while parsing the file with bs4 only took 25s). Is there something really inefficient in my code or is this going to be slow anyway?

Answer 1

It seems like you have the following:

<div class="main">
    <div class="header">a</div>
    <p>b</p>

    <div class="header">c</div>
    <p>d</p>
</div>

And you want to extract a list of the headers grouped with the content:

[('a', 'b'), ('c', 'd')]

The slow part of your code is most certainly the if tag in headers. If header is a list of 10k elements, then for each element in .main you are searching through potentially 10k elements. This is horribly inefficient. If headers was a set, this would be more efficient, but there's no need for it to be (or for you to check if tag in headers).

def get_header_content_pairs(doc):
    main = doc.find("div", class_="main")
    headers = main.find_all("div", class_="header")

    for header in headers:
        yield (header, list(get_content(header.nextSibling)))

def get_content(element):
    while element.name == 'p':
        yield element
        element = element.nextSibling

Haven't tested this, but the gist is instead of doing all that work, you take advantage of the fact that each BS element knows about its nextSibling. You find all of the .headers. For each of them, you continue checking nextSibling until you find something that isn't a <p>. You aggregate these and return them with their header.

Answer 2

Like @BaileyParker pointed out quickly, using a set might also be a solution to improve your code. Although I didn't test to see if this approach or his might be the fastest, I want to explain a little bit why switching headers from an array to a set might make a great improvement without much code modification.

Each time you use the in operator on an array, a range of things could happen : The element could be at the first position, which would be nice, or it could be the last, which would be long. For the sake of the example, let's say the element is always at the middle (that makes an okay mean).

So, if your headers element has 1000 elements, then we could assume that every time you call in , you go through 500 elements to find the good one.

This is because the array isn't very good at the contains operation. It's strong to Add/Remove/Get at a specific index though, but it doesn't really fit our use case. For the Contains operator, the array operates in O(n) time complexity.

The set, however, is very good at Contains, because chances are you don't need to iterate through anything. When you add an element to the set, its hash is computed and then used as a key for an underlying array (it's a little more complicated than that but the idea's there), meaning you can always access a specific elements in one shot.

I think you should try converting your headers array into a set. To do so, all you need to do is change :

headers = main.find_all("div", class_="header")

to

headers = set(main.find_all("div", class_="header"))

You might be thinking : "Okay but this operation is going to take long". It's not wrong, but it'll still be much faster than using the array every time you want to use the in operator.