Challenge #8 – The Big O Problem

30 October 2019 Solved Twig Intermediate

It's time to get "algorithmical" and solve a problem that could easily be implemented using a poorly performing algorithm the performant way.

Challenge

The challenge is quite straightforward. For each of the entries in a structure, output the the title of the entry and its ancestors in a breadcrumb manner. So for example given the following structure:

Entry 1
    Entry 2
        Entry 3
        Entry 4
    Entry 5
Entry 6
    Entry 7

The output should be:

Entry 1
Entry 1 > Entry 2
Entry 1 > Entry 2 > Entry 3
Entry 1 > Entry 2 > Entry 4
Entry 1 > Entry 5
Entry 6
Entry 6 > Entry 7

The catch is that the algorithm should have a complexity of O(1), meaning that the runtime, and in our case the number of database queries, should remain constant regardless of how many entries exist in the structure. If, on the other hand, the number of database queries grows linearly and is proportional to the number of entries then your algorithm has a complexity of O(n).

This is called "Big O notation" and can be visualised as follows:

Big O Notation

For a more in-depth explanation check out A Simplified Explanation of the Big O Notation by Karuna Sehgal.

If you learn better from stories about carrier pigeons and lawn mowing then you can watch the first few minutes of this fun video.

Rules

The algorithm should be written in twig using Craft tags, so using the {% nav %} tag is allowed. It must output a structure's entries as described above with a complexity of O(1). It should not rely on any plugins and the code will be evaluated based on the following criteria in order of priority:

  1. Readability
  2. Brevity
  3. Performance

Therefore the code should be readable and easy to understand. It should be concise and non-repetitive, but not at the expense of readability. It should be performant, but not at the expense of readability or brevity.

Tips

You can keep track of how performant your algorithm is by turning on the debug toolbar on the front-end of your site and keeping an eye on the number of database queries required to output the structure. Get a baseline by outputting the structure entries without their ancestors, then see how many extra queries are necessary to output the titles of their ancestors. If the number of database queries increases as you add more entries to the structure then you're likely working with a O(n) algorithm. If it remains constant then congratulations, you have achieved O(1)!

Debug Toolbar DB

Solution

On reading and understanding the challenge, your first impulse might be to reach for the getAncestors() method that entry elements provide. After all, this is the code sample provided in the Displaying Breadcrumbs for an Entry guide:

{% if entry.level > 1 %}
    <ul class="crumbs">
        {% for crumb in entry.getAncestors() %}
            <li>{{ crumb.getLink() }}</li>
        {% endfor %}
    </ul>
{% endif %}

entry.getAncestors() fetches the entry's ancestors which are then looped over and output. Under the hood, however, each call to getAncestors() results in a new database query. This is fine in the example above, since we are dealing with a single entry. The problem begins if we use the method within a loop.

Consider the following solution:

{% nav entry in entries %}

    {% set ancestors = entry.getAncestors() %}
    {% for ancestor in ancestors %}
        {{ ancestor.title }} >
    {% endfor %}

    {{ entry.title }}
    <br>
    
    {# Repeat for children #}
    {% children %}

{% endnav %}

This will output the entries exactly as required, however, notice how the ancestors are fetched using entry.getAncestors() within the {% nav %} tag . The nav tag works like a for loop except that the elements are output hierarchically. This ultimately means that the getAncestors() method is called once for every entry. As the number of entries grows, so does the number of calls to the getAncestors() method and hence to the database. In effect we are dealing with an O(n) algorithm.

To make this an O(1) algorithm, we need to eliminate the use of getAncestors() and come up with an alternative solution. Since we need to loop over the entries anyway, there is an opportunity for us to store them as we go and reuse them in subsequent iterations. We can create a new array variable in twig. Each time we go down a level we will add the entry title to the array using the merge filter. Finally we can output the array values using the join filter.

{# Create new array #}
{% set breadcrumbs = [] %}

{# Add an entry title to the array #}
{% set breadcrumbs = breadcrumbs|merge([entry.title]) %}

{# Output the array values separated by `>` #}
{{ breadcrumbs|join(' > ') }}

Note that the merge filter requires that an array is passed into it, so we must wrap entry.title in square brackets to force it into a new array.

We can now begin writing a more efficient algorithm using the approach as above:

{% set breadcrumbs = [] %}

{% nav entry in entries %}

    {% set breadcrumbs = breadcrumbs|merge([entry.title]) %}
    {{ breadcrumbs|join(' > ') }}
    <br>

    {# Repeat for children #}
    {% children %}

{% endnav %}

This is a step in the right direction, however it will produce the following incorrect output:

Entry 1
Entry 1 > Entry 2
Entry 1 > Entry 2 > Entry 3
Entry 1 > Entry 2 > Entry 3 > Entry 4
Entry 1 > Entry 2 > Entry 3 > Entry 4 > Entry 5
Entry 1 > Entry 2 > Entry 3 > Entry 4 > Entry 5 > Entry 6
Entry 1 > Entry 2 > Entry 3 > Entry 4 > Entry 5 > Entry 6 > Entry 7

What we need to do to correct this is to reset the breadcrumbs in each iteration according to the entry level. We can do this using the slice filter together with the entry.level attribute.

{# Output: Entry 1 > Entry 2 > Entry 4 #}

{# Current entry level: 2 #}

{# Reset the breadcrumbs to the current entry level minus one #}
{% set breadcrumbs = breadcrumbs|slice(0, entry.level - 1) %}

{# Output: Entry 1 #}

Note that since array indexing is zero-based in PHP (and twig), we need to slice the breadcrumbs array from 0 to entry.level - 1.

By applying the slice filter followed by the merge filter, we effectively prune the breadcrumbs array up until (and not including) the entry with the same level as the current entry level and then append the current entry title on to the end.

{% set breadcrumbs = [] %}

{% nav entry in entries %}

    {% set breadcrumbs = breadcrumbs|slice(0, entry.level - 1)|merge([entry.title]) %}
    {{ breadcrumbs|join(' > ') }}
    <br>

    {# Repeat for children #}
    {% children %}

{% endnav %}

Similar solutions: Prateek Rungta, Sarah Schütz.

Since the array is pruned only when the level is less than or equal to the level from the previous iteration, this O(1) algorithm outputs the ancestors of the current entry correctly and in the most performant way.

Entry 1
Entry 1 > Entry 2
Entry 1 > Entry 2 > Entry 3
Entry 1 > Entry 2 > Entry 4
Entry 1 > Entry 5
Entry 6
Entry 6 > Entry 7

This solution by Alex Roper takes a similar approach but uses a for loop instead of the nav tag and gets into the logic of how structures work. For each entry, the algorithm loops over all of the entries again, comparing their lft and rgt values with those of the current entry. See if you can figure out from the solution how structures are stored in Craft's structureelements database table using the nested set model.

Submitted Solutions

  • Alex Roper
  • Prateek Rungta
  • Sarah Schütz
  • David Hellmann