Challenge #8 – The Big O Problem

30 October 2019 Solved Twig Intermediate

It’s time to get algorith­mic­al” and solve a prob­lem that could eas­ily be imple­men­ted using a poorly per­form­ing algorithm the per­form­ant way.

Chal­lenge

The chal­lenge is quite straight­for­ward. For each of the entries in a struc­ture, out­put the the title of the entry and its ancest­ors in a bread­crumb man­ner. So for example giv­en the fol­low­ing structure:

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

The out­put 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 com­plex­ity of O(1), mean­ing that the runtime, and in our case the num­ber of data­base quer­ies, should remain con­stant regard­less of how many entries exist in the struc­ture. If, on the oth­er hand, the num­ber of data­base quer­ies grows lin­early and is pro­por­tion­al to the num­ber of entries then your algorithm has a com­plex­ity of O(n).

This is called Big O nota­tion” and can be visu­al­ised as follows:

Big O Notation

For a more in-depth explan­a­tion check out A Sim­pli­fied Explan­a­tion of the Big O Nota­tion by Kar­una Sehgal.

If you learn bet­ter from stor­ies about car­ri­er pigeons and lawn mow­ing then you can watch the first few minutes of this fun video.

Rules

The algorithm should be writ­ten in twig using Craft tags, so using the {% nav %} tag is allowed. It must out­put a structure’s entries as described above with a com­plex­ity of O(1). It should not rely on any plu­gins and the code will be eval­u­ated based on the fol­low­ing cri­ter­ia in order of priority:

  1. Read­ab­il­ity
  2. Brev­ity
  3. Per­form­ance

There­fore the code should be read­able and easy to under­stand. It should be con­cise and non-repet­it­ive, but not at the expense of read­ab­il­ity. It should be per­form­ant, but not at the expense of read­ab­il­ity or brevity.

Tips

You can keep track of how per­form­ant your algorithm is by turn­ing on the debug tool­bar on the front-end of your site and keep­ing an eye on the num­ber of data­base quer­ies required to out­put the struc­ture. Get a baseline by out­put­ting the struc­ture entries without their ancest­ors, then see how many extra quer­ies are neces­sary to out­put the titles of their ancest­ors. If the num­ber of data­base quer­ies increases as you add more entries to the struc­ture then you’re likely work­ing with a O(n) algorithm. If it remains con­stant then con­grat­u­la­tions, you have achieved O(1)!

Debug Toolbar DB

Solution

On read­ing and under­stand­ing the chal­lenge, your first impulse might be to reach for the get­Ancest­ors() meth­od that entry ele­ments provide. After all, this is the code sample provided in the Dis­play­ing Bread­crumbs 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 ancest­ors which are then looped over and out­put. Under the hood, how­ever, each call to getAncestors() res­ults in a new data­base query. This is fine in the example above, since we are deal­ing with a single entry. The prob­lem begins if we use the meth­od with­in a loop.

Con­sider the fol­low­ing 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 out­put the entries exactly as required, how­ever, notice how the ancest­ors are fetched using entry.getAncestors() with­in the {% nav %} tag . The nav tag works like a for loop except that the ele­ments are out­put hier­arch­ic­ally. This ulti­mately means that the getAncestors() meth­od is called once for every entry. As the num­ber of entries grows, so does the num­ber of calls to the getAncestors() meth­od and hence to the data­base. In effect we are deal­ing with an O(n) algorithm.

To make this an O(1) algorithm, we need to elim­in­ate the use of getAncestors() and come up with an altern­at­ive solu­tion. Since we need to loop over the entries any­way, there is an oppor­tun­ity for us to store them as we go and reuse them in sub­sequent iter­a­tions. We can cre­ate a new array vari­able in twig. Each time we go down a level we will add the entry title to the array using the merge fil­ter. Finally we can out­put the array val­ues 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 fil­ter requires that an array is passed into it, so we must wrap entry.title in square brack­ets to force it into a new array.

We can now begin writ­ing a more effi­cient 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 dir­ec­tion, how­ever it will pro­duce the fol­low­ing incor­rect 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 cor­rect this is to reset the bread­crumbs in each iter­a­tion accord­ing to the entry level. We can do this using the slice fil­ter togeth­er 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 index­ing is zero-based in PHP (and twig), we need to slice the bread­crumbs array from 0 to entry.level - 1.

By apply­ing the slice fil­ter fol­lowed by the merge fil­ter, we effect­ively prune the bread­crumbs array up until (and not includ­ing) the entry with the same level as the cur­rent entry level and then append the cur­rent 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 %}

Sim­il­ar solu­tions: Prateek Rungta, Sarah Schütz.

Since the array is pruned only when the level is less than or equal to the level from the pre­vi­ous iter­a­tion, this O(1) algorithm out­puts the ancest­ors of the cur­rent entry cor­rectly and in the most per­form­ant 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 solu­tion by Alex Rop­er takes a sim­il­ar approach but uses a for loop instead of the nav tag and gets into the logic of how struc­tures work. For each entry, the algorithm loops over all of the entries again, com­par­ing their lft and rgt val­ues with those of the cur­rent entry. See if you can fig­ure out from the solu­tion how struc­tures are stored in Craft’s structureelements data­base table using the nes­ted set mod­el.

Submitted Solutions

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