Tag Archives: C++

Memoization

1 Reply

A coworker and I were recently discussing SDE interview questions, and I proposed that one of them could involve the use of memoization, which stores calculated values so they don’t need to be recalculated later. He hadn’t dealt with memoization much, so I wrote up two little sampler programs to demonstrate the value it can add. These programs calculate the Nth Fibonacci number, in the typical lazy recursive way (iterative could be better since it wouldn’t require all those stack frames, but this is just to prove a point).

First, here is the non-memoized form:

#include <iostream>

class Fibber
{
    private:
        std::map<unsigned int, double> _fibs;

    public:
        double fib_of(unsigned int idx)
        {
            if(idx <= 2)
            {
                return 1;
            }

            return fib_of(idx - 1) + fib_of(idx - 2);
        }
};

int main()
{
    Fibber x;

    for(int i = 1; i <= 100; i++)
    {
        std::cout << x.fib_of(i) << std::endl;
    }
}

Now, if we take that same program but add memoization:

#include <iostream>
#include <map>

class Fibber
{
    private:
        std::map<unsigned int, double> _fibs;

    public:
        double fib_of(unsigned int idx)
        {
            if(idx <= 2)
            {
                return 1;
            }
            
            double ret = 0;
            std::map<unsigned int, double>::iterator loc_iter = _fibs.find(idx);
            if(loc_iter != _fibs.end())
            {
                ret = loc_iter->second;
            }
            else
            {
                double calculated = fib_of(idx - 1) + fib_of(idx - 2);
                _fibs.insert(std::pair<unsigned int, double>(idx, calculated));
                ret = calculated;
            }

            return ret;
        }
};

int main()
{
    Fibber x;

    for(int i = 1; i <= 100; i++)
    {
        std::cout << x.fib_of(i) << std::endl;
    }
}

The difference in performance between the two is night-and-day.

The non-memoized variety will slow to an unresponsive crawl in very short order, because it has to calculate all the values leading up to the current value, repeatedly for each value; it forgets all the interim values on the way.

The memoized version remembers the interim values, and therefor only calculates them once, storing each in the cache.

Removing while iterating

Leave a reply

The context of this post is Java, but the concept applies to other languages as well. (C#, etc).

Have you ever encountered a need to remove elements from a collection while iterating over it? This is not allowed:

for(Foo f : fooList) {
    if(f.bar()) {
        fooList.remove(f);
    }
}

A ConcurrentModificationException will be thrown, since you are attempting to modify a list during iteration. It makes sense; after all, if you remove something, the list is in a new state, and who is to say what the next element is at that point?

There is however a solution, and it involves a commonly used pattern in C++, which is to use an iterator. An iterator provides you with access to the next element in its iteration, as well as access to the original iteration index. This allows you to manipulate whatever list you are iterating over, since your iteration does not rely on its current state, only the state of which the iterator was based on.

Here is the above example reworked:

  for (Iterator iter = fooList.iterator(); iter.hasNext(); Foo f = iter.next()) {
    if(f.bar()) {
      iter.remove();
    }
  }

The .remove() option on the iterator removes the element from the underlying collection, but does not impact the iterator.

Generics vs Templates

Leave a reply

Are you familiar with the difference between Generics in languages like Java and C#, and Templates in C++ ? Functionally they serve the same purpose, to dynamically type a class, but they are actually quite different, and may not be implemented as you might expect.

Let’s start with Generics. In languages like Java and C#, you can declare a class like so:

    public class Foo<T>
    {
        private T _bar:
        public Foo(T bar)
        {
            _bar = bar;
        }
    }

Doing so will force the consumer of this class to specify its type like so:

    Foo<T> myFoo = new Foo<T>("Stringly typed!");

The type is enforced to be ‘String’ in this case. But is the enforcement at compile time or runtime? You might be surprised to learn that it is at compile time. It is nothing more than compile-time convention to force the programmer to be type-safe. The actual objects at run-time have no notion that they can or cannot be a certain type, and are simply expected to be properly enforced at compile time.

So now that we understand how they work in Java and C#, what about Templates in C++? They serve a very similar purpose, but how are they actually implemented compared to the other languages? It turns out that at compile-time C++ will actually generate all possible combinations of the template based on the possible types that could be passed to it as determined by the compiler looking at the rest of the code. This makes sense, since the name of the feature is ‘template’, but it’s not often thought about in that fashion by average C++ developers.

Coffee and See Plus Plus

Leave a reply

Do you remember the first time you had coffee? A lot of people relate their first experience with coffee as a bad one. It’s common to hear people say that coffee is an acquired taste. For me this is untrue. I’ve always loved coffee from my very first taste, but I understand why people say it, and I want to relate that idea to C++ for a minute. C++ is a language that by more modern language standards is archaic, but it’s still arguably quite important to learn so that you understand manual memory management and how other languages are implemented.

Ok, so lets say you dive into C++ because you’re interested in knowing everything there is to know about programming. You discover it’s like your coffee experience; It’s bitter, it smells funny, and gives you jitters, but you keep on sipping it because you know it will give you benefits. Depending on your mileage, you might fast forward 6 months and find yourself practically hooking it up to your arm with an IV needle. Now that you feel comfortable with it and the knowledge it gave you, you’re ready to move on to new things. You’re satisfied that you used it as a learning tool, but are you really done with it? No; you’ll find that it’s still extremely pervasive in many areas of our industry.

And in that sense, it’s more like cocaine than coffee.

The gaming industry, or any industry that possesses an interest in high-performance computing applications, is addicted to C++. Regardless of how far managed code and garbage collection has come, they cling to it, because it’s got a lot of momentum attached to it. “JUST ONE MORE HIT MAN, JUST ONE MORE HIT”. I sympathize on the one hand because C++ ought to be mandatory learning material for computer science students (because it does teach you about how things work under the covers), but at the same time haven’t we come far enough with the performance of other languages that we can just go ahead and take C++ out back of the shed?