Challenge #8 – The Big O Problem

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:

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)!

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

Solution submitted by Alex Roper on 6 November 2019.

{% set entries = craft.entries.section('nav').all() %}
    
{% for entry in entries %}
  
  {% set crumb = [] %}
  
  {# Loop thru all entries again, matching items in the nested set model.
     Match items where the current entry's left and right domain falls between 
     the item's left and right domain, including the current entry.
  -#}
  {% for item in entries if (entry.lft >= item.lft) and (entry.rgt <= item.rgt) %}
    {% set crumb = crumb|merge([item.title]) %}
  {% endfor %}
  
  {# Output the full breadcrumb with > separators #}
  {{ crumb|join(' > ') }}<br>

{% endfor %}

• Prateek Rungta

Solution submitted by Prateek Rungta on 6 November 2019.

{% set entries = craft.entries.section('pages').all() %}

{% nav entry in entries %}
    
    {# Build ancestor lists for nested elements
       by using previous breadcrumbs #}
    {% set ancestors = entry.level > 1
      ? breadcrumbs[0 : entry.level - 1]
      : [] %}
    
    {# Add current entry to ancestors and render titles #}
    {% set breadcrumbs = ancestors|merge([entry]) %}
    {{ breadcrumbs|column('title')|join(' > ') }}
    
    {# Repeat for all children #}
    <br>
    {% children %}
    
{% endnav %}

• Sarah Schütz

Solution submitted by Sarah Schütz on 8 November 2019.

{% set entries = craft.entries().section('entry').all() %}

{% macro render(entries) %}
    {% nav entry in entries %}
        {{ entry.title }}

        {% ifchildren %}
            > {% children %}
        {% endifchildren %}
    {% endnav %}
{% endmacro %}

{% set entryStack = [] %}
{% for entry in entries %}
    {% set level = entry.level %}

    {# remove all entries with a level higher or equal to the current entry #}
    {% set entryStack = entryStack | slice(0, level - 1) %}

    {# add current entry to stack #}
    {% set entryStack = entryStack | merge([entry]) %}

    {# render the current entry stack #}
    <p>{{ _self.render(entryStack) }}</p>
{% endfor %}

• David Hellmann

Solution submitted by David Hellmann on 9 November 2019.

{% set entries = craft.entries.section('challange').all() %}
{% set storage = '' %}
{% for entry in entries %}
  {% if entry.level == 1 %}
    {% set storage = entry.title %}
    {{ entry.title }}<br>
  {% endif %}

  {% if entry.level == 2 %}
    {{ storage }} > {{ entry.title }}<br>
    {% set storage = storage ~ ' > ' ~ entry.title %}
  {% endif %}

  {% if entry.level == 3 %}
    {{ storage }} > {{ entry.title }}<br>
  {% endif %}
{% endfor %}