Commented Code ...blog

Nov 09, 2012

Lazy Evaluation in C++11

EDIT: Thanks to Bret for the idea with std::unique_ptr

In a recent conversation at work, I was attempting to explain some of the new features added by the C++11 Standard. While discussing, I eventually started bringing up other development concepts I'd recently discovered while learning some new languages. So I thought why not put them together. Here is some Lazy Evaluation using Lambda Functions in C++11.

Lazy you say...

Lazy Evaluation, for those of you unfamiliar, is a strategy for processing information in a way that delays the system from doing work until it is actually needed. In many cases of software development, you may be tasked to perform a set of actions on a set of data at numerous times that induce an...extreme load on the system. If the process allows, the load is acceptable because all of the output generated is usable by the process. But sometimes you have to do a lot of work to generate results that you may have to consider "the cost of doing business."


Some non-lazy examples

For a simple example, lets say we need an array containing N number of values in the Fibonacci Sequence. The user can ask for the mth number in the list as long as

0 <= m <= N

To make this program we either need to

  • Generate the list of a huge value N up front
  • Wait for the user to input m and then make an array where m == N

One big N

So lets try out the first example.

#include <iostream>
#include <vector>

using namespace std;

vector<int> PreCalc;

void fillPreCalc (int n)
{
  PreCalc = vector<int>(n);
  PreCalc[0] = 0;
  PreCalc[1] = 1;

  for (int i = 2; i <= n; i++)
  {
    PreCalc[i] = PreCalc[i-1] + PreCalc[i-2];
  }
}

int main (void)
{
  int m;

  fillPreCalc(100);

  cout << "Enter a value for m: ";
  cin >> m;

  cout << "The " << m << " number in the Fibonacci Sequence is "
       << PreCalc[m] << endl;

  cout << "Enter another value for m: ";
  cin >> m;

  cout << "The " << m << " number in the Fibonacci Sequence is "
       << PreCalc[m] << endl;

  return 0;
}

First thing we do is calculate our Fibonacci Numbers and store them into a vector. All the work is done up front and the results can be used many times without having to do the work again. Sounds great. The only problem is we have to decide the size of N to calculate. If calculate for N == 100 but we only want to know the first three numbers, the other 97 we just calculated ate up time we could have saved if our N was 3.

Calculate in place

If we don't want to waste any time then we need to set m == N.

#include <iostream>

using namespace std;

int InCalc (int m, int x = 0, int y = 1)
{

  if (m == 0)
    return x;
  else
    return InCalc(--m, y, x+y);
}

int main (void)
{
  int m;

  cout << "Enter a value for m: ";
  cin >> m;

  cout << "The " << m << " number in the Fibonacci Sequence is "
       << InCalc(m) << endl;

  cout << "Enter another value for m: ";
  cin >> m;

  cout << "The " << m << " number in the Fibonacci Sequence is "
       << InCalc(m) << endl;

  return 0;
}

Now when we call InCalc() we calculate up to the mth number and no more. The only problem is if we want to find another m we have to generate another sequence of values.

Be efficient, be lazy

If only there was a way to get the Pros of both examples without the Cons. We would have a system that:

  • Stores all calculated values for future use
  • Only calculates up to the largest value m input

We can start by creating a structure that allows for storing sequential data. Each time we calculate a new Fibonacci Number we can stick it to the end of the list. If we need a value less than N we won't need to do any redundant calculations. So the first requirement is done.

The second requirement is a little more difficult. Calculating for a case where m == N, our previous example used recursion to quickly and efficiently get the job done. Each step through the recursion contains state information from the previous step (i.e. the value of the previous two Fibonacci Numbers). So we need to make our structure save the state of our recursion to get the second requirement.

Drum roll please!

Here we go...

#include <iostream>
#include <functional>
#include <memory>

using namespace std;

struct fib
{
  int value;
  function<fib* ()> genNext;
  unique_ptr<fib> next = nullptr;

  fib(int m, int n) :
    value(m),
    genNext([=] () -> fib* { return new fib(n, m + n); })
    {}

  fib() : fib(0, 1) {}

  int& operator[] (int x)
  {
    if (x == 0)
      return value;
    else
    {
      if (next == nullptr)
        next = unique_ptr<fib>(genNext());

      return (*next)[--x];
    }
  }
};

int main (void)
{
  fib f = fib();

  for (int i = 0; i < 10; i++)
    cout << f[i] << endl;

  return 0;
}

Starting with our structure fib we are able to store our value and a pointer to the next structure. Using the overloaded [] operator we can step through our list of values. Requirement 1...check!

Now for the fun part. C++11 standard has replaced the horrible function pointers of C with std::function. We can store a function call as an object, in our case function<fib* ()> genNext; What function do we store in this object? The constructor of our next structure in the Fibonacci Sequence of course.

[=] () -> fib* { return new fib(n, m + n); }

Using a Lambda Function we are able to store our state, the previous two Fibonacci Numbers, which is called if our next number is requested. If the request never comes then no need to calculate. If we request a case where m > N we call the Lambda Function to generate the next number until m == N. All cases where the user requests m < N we cycle through our list and never perform a redundant calculation.

Being lazy is pretty cool.

<perm> | /coding/c++ | 2012.11.09-16:20.00 | <comments> | <reddit> | <digg> | <stumbleupon> | <tweet>