Solving the 0-1 knapsack problem using continuation-passing style with memoization in F#

Continuation-passing style (CPS) is a technique for adapting non tail-recursive functions into tail-recursive functions. This article describes continuation-passing style and why it is essential to solving some problems, such as the 0-1 knapsack problem, in a functional way.

Tail-recursion

A function is recursive if it calls itself. For example, the recursive function below returns the largest element in a list.

let largest xs =
   let rec largest = function
      | [] -> failwith "Must have at least one element in list"
      | x::[] -> x
      | x::xs -> max x (largest xs)
   largest xs

In the case where the list contains only one element that element is the largest element. Otherwise, the largest element in the list is the largest of the head and the largest element of the tail list.

A function is tail-recursive if it calls itself only at the end of the function. For example, the tail-recursive function below also returns the largest element in a list.

let largest' xs =
   let rec largest largestSoFar = function
      | [] -> largestSoFar
      | x::xs -> largest (max largestSoFar x) xs
   match xs with
   | [] -> failwith "Must have at least one element in list"
   | x::xs -> largest x xs

The first function “delayed” the computation involving the head of the list until the largest element of the tail list was known, whereas this function pushes the largest element found so far through the rest of the computation as an argument.

Performance

Rewriting the function in this style may worsen its readability. However, it has performance benefits.

let xs = [0..10000]
for i = 1 to 10000 do largest' xs |> ignore
for i = 1 to 10000 do largest xs |> ignore
largest' [0..100000] |> ignore
largest [0..100000] |> ignore

Running the code above inside F# interactive results in the following output [1][2].

Real: 00:00:00.246, CPU: 00:00:00.234, GC gen0: 0, gen1: 0, gen2: 0
val it : unit = ()
>
Real: 00:00:00.550, CPU: 00:00:00.546, GC gen0: 0, gen1: 0, gen2: 0
val it : unit = ()
>
Real: 00:00:00.019, CPU: 00:00:00.031, GC gen0: 1, gen1: 0, gen2: 0
val it : unit = ()
>

Process is terminated due to StackOverflowException.

This shows that the tail-recursive function is approximately 2.3 times faster for lists of 10,000 elements and safer for longer lists. The plain recursive function runs out of stack space when asked to compute the largest element in a list with 100,000 elements. However, the tail-recursive function does not. This is because the F# compiler performs tail-call elimination [3]. Tail-call elimination is an optimization where tail-recursive functions are converted into while loops.

It is possible to see the difference in the code generated by the compiler using a decompiler like ILSpy. Below are C# translations of the IL code generated for both functions.

1. Plain recursive function

internal static int largest@4(FSharpList _arg1)
{
	if (_arg1.TailOrNull == null)
	{
		throw new Exception("Must have at least one element in list");
	}
	if (_arg1.TailOrNull.TailOrNull == null)
	{
		return _arg1.HeadOrDefault;
	}
	FSharpList xs = _arg1.TailOrNull;
	int x = _arg1.HeadOrDefault;
	int num = Program.largest@4(xs);
	if (x < num) 	{ 		return num; 	} 	return x; } 

2. Tail-recursive function

 
internal static int largest@11-1(int largestSoFar, FSharpList _arg1) 
{
   while (_arg1.TailOrNull != null) 	
   {
      FSharpList fSharpList = _arg1;
      FSharpList xs = fSharpList.TailOrNull;
      int x = fSharpList.HeadOrDefault;
      int arg_26_0 = (largestSoFar >= x) ? largestSoFar : x;
      _arg1 = xs;
      largestSoFar = arg_26_0;
   }
   return largestSoFar;
}

Continuation-passing style

Continuation-passing style provides an alternative means of making the original function tail-recursive. The original function "delayed" the computation until it received the result of a recursive call. If we use continuation-passing style, instead we pass the action we wish to perform on the result into the function. When the result is known the function carries out this action (the continuation).

let largest'' xs =
   let rec largest k = function
      | [] -> failwith "Must have at least one element in list"
      | x::[] -> k x
      | x::xs -> largest (fun x' -> k(max x x')) xs
   largest id xs

Line 6: Our initial intent is to return the value computed, therefore the first continuation we pass in is the identity function.
Line 4: When there is only one element in a list that element is the largest value and we use that in the continuation.
Line 5: When the largest element of the tail list is known we take the largest of that element and the head element and use that in the continuation.

Unfortunately using CPS can result in worse performance characteristics. Below are the results we obtained when we ran the function against the same tests that we ran the plain recursive and tail-recursive functions against.

let xs = [0..10000]
for i = 1 to 10000 do largest'' xs |> ignore
largest'' [0..100000] |> ignore
Real: 00:00:04.125, CPU: 00:00:04.102, GC gen0: 723, gen1: 77, gen2: 0
val it : unit = ()
>
Real: 00:00:00.023, CPU: 00:00:00.031, GC gen0: 1, gen1: 0, gen2: 0
val it : unit = ()
>

When asked to find the largest element in a list of 10,000 elements the tail-recursive function was approximately 17.5 times faster than the CPS function whilst the plain recursive function was approximately 7.5 times faster.

Multiple recursion

Sometimes we are forced to write continuation-passing style functions despite the fact they can have worse performance characteristics than "hand written" tail-recursive functions. Consider the example below. It is a recursive function that calculates the nth Fibonacci number.

let fib n =
   let rec fib = function
      | 0 -> 0
      | 1 -> 1
      | n -> fib(n-1) + fib(n-2)
   fib n

We cannot easily "hand write" a tail-recursive solution to this problem because it seems to require two recursive calls. However, we can easily turn it into a tail-recursive function using CPS.

let fib' n =
   let rec fib k = function
      | 0 -> k 0
      | 1 -> k 1
      | n -> fib (fun x -> fib (fun y -> k(x+y)) (n-2)) (n-1)
   fib id n

0-1 Knapsack problem

A more interesting problem with the multiple recursion trait is the 0-1 knapsack problem.

Given a set of items, each with a weight and a value, determine the count of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

Below is a recursive function that finds the greatest total value possible by choosing a combination of the first \large i items weighing up to \large w. For the first \large i items this total either includes the \large i^{th} item's value or it does not.

If the item is included, the solution must be equal to \large {value}(i) plus the greatest total value possible by choosing a combination of the first \large i-1 items weighing up to \large w - {weight}(i).

If the \large i^{th} item is not included, the solution must be equal to finding the greatest total value possible by choosing a combination of the first \large i-1 items weighing up to \large w.

let bestValue weightOf valueOf desiredWeight (items:_[]) =
   let weightOf i = weightOf items.[i-1]
   let valueOf i = valueOf items.[i-1]
   let rec bestValue = function
      | 0, _ | _, 0 -> 0.
      | i, w when weightOf i > w -> bestValue (i-1, w)
      | i, w ->
         let withoutItem = bestValue (i-1, w)
         let withItem = bestValue (i-1, w - weightOf i) + valueOf i
         max withoutItem withItem
   bestValue (items.Length, desiredWeight)

Obviously, this solver suffers from the same problems we highlighted in the other non tail-recursive functions. It cannot be used safely with large numbers of items. Though, once again, we can rewrite this function using continuation passing-style.

let bestValue' weightOf valueOf desiredWeight (items:_[]) =
   let weightOf i = weightOf items.[i-1]
   let valueOf i = valueOf items.[i-1]
   let rec bestValue k = function
      | 0, _ | _, 0 -> k 0.
      | i, w when weightOf i > w -> bestValue k (i-1, w)
      | i, w ->
         bestValue (fun withoutItem ->
            bestValue (fun withItem ->
                  let withItem = withItem + valueOf i
                  k(max withoutItem withItem)
               ) (i-1, w - weightOf i)
            ) (i-1, w)
   bestValue id (items.Length, desiredWeight)

Enhancing readability

When we introduced tail-recursive functions we mentioned that "hand writing" functions in this style can impair the readability of the solution somewhat. If we compare the two 0-1 knapsack problem solvers, we can see that continuation-passing style exacerbates this issue further. Thankfully, we can use the continuation monad to improve readability whilst keeping the function tail-recursive. We can define our own monads (or computation expressions) in F# by defining a builder class with some special methods. Below is an example showing how we might define a builder that allows us to use the continuation monad.

type ContinuationBuilder() =
   member b.Bind(x, f) = fun k -> x (fun x -> f x k)
   member b.Return x = fun k -> k x
   member b.ReturnFrom x = x
let cont = ContinuationBuilder()

Two examples using the continuation monad are below. First, we show an adapted Fibonacci function. Second, we show an adapted 0-1 knapsack problem solver. They both use continuation-passing via the continuation monad. However, they look much closer to the original naive functions than the continuation-passing style functions.

let fib'' n =
   let rec fib n = cont {
      match n with
      | 0 -> return 0
      | 1 -> return 1
      | n ->
         let! x = fib(n-1)
         let! y = fib(n-2)
         return x + y
   }
   fib n id

let bestValue'' weightOf valueOf desiredWeight (items:_[]) =
   let weightOf i = weightOf items.[i-1]
   let valueOf i = valueOf items.[i-1]
   let rec bestValue (i, w) = cont {
      match i, w with
      | 0, _ | _, 0 -> return 0.
      | i, w when weightOf i > w -> return! bestValue (i-1, w)
      | i, w ->
         let! withoutItem = bestValue (i-1, w)
         let! beforeItem = bestValue (i-1, w - weightOf i)
         let withItem = beforeItem + valueOf i
         return max withoutItem withItem
   }
   bestValue (items.Length, desiredWeight) id

Imperative solution to the 0-1 knapsack problem written in C#

We have set out how we can define a readable tail-recursive solver using the continuation monad. Yet we are still to prove that this can exhibit good performance. We will use the imperative solver below, written in C#, as the baseline for testing performance.

public static double BestValue(Tuple[] items, int desiredWeight)
{
   var bestValues = new Value[items.Length + 1, desiredWeight + 1];
   for (var w = 0; w    for (var i = 0; i    for (var i = 1; i    {
      var item = items[i-1];
      var weight = item.Item1;
      var value = item.Item2;
      for (var w = 1; w  w)
         {
            bestValues[i, w] = bestValues[i-1, w];
         }
         else
         {
            var withoutItem = bestValues[i-1, w];
            var beforeItem = bestValues[i-1, w-weight];
            var withItem = beforeItem + value;
            bestValues[i, w] = Math.Max(withItem, withoutItem);
         }
      }
   }

   return bestValues[items.Length, desiredWeight];
}

We tested the solvers using the code below to generate test data.

let genItems n = 
   [| for i = 1 to n do
         let weight = i % 5
         let value = float(weight * i)
         yield weight, value
   |]

This is a plot of the time each of the solvers took to find the optimum solution for various sizes of input. It shows that the solver using the continuation monad has a much worse asymptotic time-complexity than the imperative solver.

Memoizing

If we look at the solver using the continuation monad more closely it is easy to see how we might improve it. The main function makes multiple recursive calls to itself computing values that may have already been computed in sub-problems. Therefore, we can improve the function by memoizing it.

The function below memoizes recursive functions. This particular memoizer only works for functions using continuation-passing style or the continuation monad and that accept two integer inputs inside a known range.

let memoize2D w h f =
   let cache = Array2D.zeroCreate w h
   let hasCached = Array2D.zeroCreate w h
   let rec memoize x y k =
      if hasCached.[x,y] then k cache.[x,y]
      else f memoize x y (fun f_x_y ->
         cache.[x,y]          hasCached.[x,y]  memoize x y k

We have adapted the solver using the continuation monad to make use of this memoizer below.

let bestValue''' weightOf valueOf desiredWeight (items:_[]) =
   let inline weightOf i = weightOf items.[i-1]
   let inline valueOf i = valueOf items.[i-1]
   let bestValue bestValue i w = cont {
      match i, w with
      | 0, _ | _, 0 -> return 0.
      | i, w when weightOf i > w -> return! bestValue (i-1) w
      | i, w ->
         let! withoutItem = bestValue (i-1) w
         let! beforeItem = bestValue (i-1) (w - weightOf i)
         let withItem = beforeItem + valueOf i
         return max withoutItem withItem
   }
   let bestValue = memoize2D (items.Length+1) (desiredWeight+1) bestValue
   bestValue items.Length desiredWeight id

We tested this solver against the imperative solver and the non-memoized solver using the continuation monad. It shows that by using memoization we have reduced the asymptotic time-complexity to the same as the imperative solver. It now has linear time-complexity.

However, this is only an approximate asymptotic bound. If we plot just the imperative solver against the memoized solver it shows that the imperative solution is substantially faster.

Summary

In this article, we demonstrated that we can define a natural recursive solution to the 0-1 knapsack problem using F#. We investigated the safety of this function for large input sizes and found that defining tail-recursive functions is important. We discussed how we could improve the readability of tail-recursive functions using the continuation monad. Finally, we compared the performance of functional solvers to an imperative solver and showed that we could get the same approximate asymptotic time-complexity by using memoization. However, we also pointed out that in reality the imperative function is much faster. This is probably due to the expense of allocating functions in the memoized solver.

Notes

1. The code had an additional definition to avoid boxing comparisons.

let inline max (x:int) (y:int) = max x y

2. To turn on timing information in F# interactive you can use the following declaration.

#time;;

3. Tail-call elimination is used only in the 'Release' configuration by default. It must explicitly turned on in 'Debug' configuration.

About these ads
This entry was posted in Uncategorized and tagged , , , , , . Bookmark the permalink.

2 Responses to Solving the 0-1 knapsack problem using continuation-passing style with memoization in F#

  1. Hand-written (non CPS) a tail-recursive solution for Fibonacci using minimal caching.

    let fib n =
    let rec fib’ back1 back2 = function
    | 0 -> 0
    | 1 -> back1 + back2
    | n -> fib’ back2 (back1 + back2) (n – 1)
    fib’ 1 0 n

    List.map fib [0..10]

    Regarding the knacpsack solver, what’s the space complexity for the memoization solution?

  2. zbray says:

    That’s a very good solution!

    The space complexity of the memoized solver is O(i*w) where i is the number of items and w is the desired weight. However, instead of using a 2D array you could use a dictionary. In practice this might use less memory, as not all combinations of i and w will be evaluated.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s