3
\$\begingroup\$

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?

\$\endgroup\$
6
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ "If headers was a set [...] there's no need for it", if headers contains 10k elements, I'm pretty sure it would make a huge difference. \$\endgroup\$ – IEatBagels Aug 24 '18 at 12:01
  • \$\begingroup\$ @IEatBagels: I understand the "no need for it" part as there is no need to make it a set, because the whole structure of the code can be refactored to something even better. \$\endgroup\$ – Graipher Aug 24 '18 at 12:08
  • 2
    \$\begingroup\$ @IEatBagels Yeah that was just some sloppy phrasing. The "perhaps" was to suggest that you could do this, but there is really no need for checking headers like this at all. I'll revise \$\endgroup\$ – Bailey Parker Aug 24 '18 at 12:10
  • 1
    \$\begingroup\$ I think the OP also needs to get content in the <span> elements? Presumably you could just add this to the while condition in get_content, but I'm wondering if there's a robust way to get all content up to the next header? \$\endgroup\$ – Cain Aug 24 '18 at 15:15
  • 1
    \$\begingroup\$ @Cain Yes I omitted that detail, because it wasn't crucial to the performance issues. That would actually be in the yield, it would be like yield (extract_header_spans(header), list(get_content(header.nextSibling)))). As for robust, I don't know how you quantify that but nextSibling is a very common dom traversal technique. \$\endgroup\$ – Bailey Parker Aug 24 '18 at 15:44
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the further explanation of why it's problematic! \$\endgroup\$ – Matyas Aug 25 '18 at 14:16
  • 1
    \$\begingroup\$ And simply doing this made it totally usable (like 100x faster), wow \$\endgroup\$ – Matyas Aug 25 '18 at 14:29
  • \$\begingroup\$ @matyas I'm glad to hear that :) \$\endgroup\$ – IEatBagels Sep 3 '18 at 1:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.