Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Containers That Never Change

September 19, 2013

Last week, I introduced a programming style that never changes the value of a variable once that value has been established. In that article, I made a statement that one reader questioned:

If we try to write this program recursively using the technique we mentioned earlier, we find that each recursive call passes the entire result array as an argument. As a result, the program's runtime will be quadratic in the number of iterations — hardly a happy state of affairs.

Here's why I made this claim.

We start with the example to which I was referring last week:

 
vector<unsigned> collatz_vec(unsigned n)
{
          
     assert(n != 0);
     vector<unsigned> result;
          
     while (n != 1) {
          
               result.push_back(n);
               if (n % 2 == 0)
                     
                   n /= 2;
               
               else
                     
                   n = 3 * n + 1;

     }
     return result;
    
}
 

Next, we rewrite it as a tail-recursive function. We do so by observing that the variables that change in the loop are result and n, so we define an auxiliary function with those values as parameters:

 
     vector<unsigned> collatz_aux(unsigned n, vector<unsigned> result)
     {
           if (n == 1)
                return result;
           new_result = concat(result, n);
           if (n % 2 == 0)
                return collatz_aux(n / 2, new_result);
           else
                return collatz_aux(3 * n + 1, new_result);
     }
 

We now rewrite our collatz_vec function to call our auxiliary function:

 
     vector<unsigned> collatz_vec(unsigned n)
     
     {
           assert (n != 0);
           return collatz_aux(n, vector<unsigned>());
     }
 

The subexpression vector<unsigned>() is a convenient way of constructing a vector with no elements.

At this point, we have a problem: How do we write concat? The obvious technique is something like this:

 
     vector<unsigned> concat(vector<unsigned> v, unsigned n)
     {
           v.push_back(n);
           return v;
     }

This function violates the restriction we wished to impose against changing the value of a variable once such a value was established. Unfortunately, so long as we stick with vectors, it's the best we can do. At least, by using this function, we have been able to encapsulate the idea of appending an element to a vector to create a new vector. However, this function copies all of the elements of v, which means that our collatz_vec function winds up running in quadratic time — because as result grows, all of the vector's elements must be copied on each iteration.

In short, in order to make the recursive collatz_vec function run in a reasonable amount of time, we need some kind of vector-like data structure that allows us to append an element in O(1) time, rather than having to copy all of the elements each time we wish to append one. Putting it more simply, the whole notion of appending rests on being able to change the data structure to which we are appending. What we want is to be able to create a new data structure that contains all of the elements of the old one, along with one additional element, and we wish to do so in O(1) time.

There are many data structures of this kind. Lisp used one of the simpler ones. Next week I'll start explaining how it works.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video