Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Design

Synchronized Recursion


Jun01: Algorithm Alley

.


Enumerating Combinations Using BitSets


Recursive algorithms often express solutions elegantly, but they tend to have practical drawbacks. For a recent application I was writing, the drawback was that my clean recursive solution to a problem didn't work well as the implementation of a Java Iterator. It's understandable that a recursive method — or any code with its state kept primarily on the run-time stack — wouldn't be good at answering the question, "What's the next item I'm interested in?"

Why should that matter? If an algorithm lends itself toward building up a solution set, why not simply let it build up that set? After all, even if you need an Iterator, you can write one that merely walks through an in-memory vector. (That is, in practice, how a typical Iterator works anyway — it's backed by a full store of items.) However, if your algorithm produces a solution set that contains millions of items, or even just a few very large items, constructing the full set can get cumbersome quickly.

Suppose, for example, you want all combinations of size N out of a set of size M (see the accompanying text box entitled "Enumerating Combinations Using BitSets," for one way to approach the problem in Java). As you probably know, the number of combinations grows rapidly with the size of the underlying set. If you need to consider all combinations of size 5 out of a set of 50 elements, it's utterly wasteful to enumerate them all first and walk through them later. In most situations, it would be far better to consider one at a time instead of storing the entire solution set simultaneously.

This desire, however, may be at odds with a recursive solution. And as you can see from Example 1, the problem of enumerating combinations has a recursive solution that's so short and simple, it's hard to ignore. The question then becomes, how can you adapt this recursive solution to a situation where memory is limited, or where the solution size is so large that you couldn't possibly buy enough memory?

Requiring Generality and Reusability

If the question is merely how to adapt an arbitrary recursive algorithm so that you can process each solution individually (rather than building up a solution set), then you can, of course, process the solutions as you come up with them, inline.

Example 2 is an example of this technique. Ultimately, at every stage of the recursion, you either return having failed to find a solution or having succeeded. If you modify the code executed on success so that it simply calls a method, passing it the current solution, then you've solved the problem. You get to enumerate all individual solutions without requiring that they all exist in memory simultaneously.

This solution is not as attractive as it may sound, however. It ties the implementation to a particular application. What if you want a reusable library that lets you enumerate combinations of entirely different things in different applications? In all except the smallest and most limited applications, it's often not desirable to mix the code that solves a problem with the code that uses the solution.

Callback Functions and Interfaces

Whenever you have a general routine that needs to call application-specific code, you can design the general routine so that it accepts a callback function. If the general routine were written in C, you could pass it a pointer to a specific function. Then, when the general routine had a need for your specific function, it could dereference the pointer it received. The same general routine could thus be adapted for different applications.

In Java, the same style involves a little more forethought. Since you can't pass around pointers to functions — a limitation that's certainly sensible in an object-oriented environment — you'd probably end up writing an interface that defines the relationship between the general routine and the callback handler. Then, you could pass classes that implement this interface to the general routine, which would in turn call the appropriate callback methods when necessary.

Consider Example 3(a) as if it were part of a reusable library being distributed. As part of this distribution, a public interface called CombinationHandler would be included; see Example 3(b). This interface would have one method:

public void process(BitSet combination);

which implements application-specific processing of a BitSet representing a combination. That is, users of the library should implement the CombinationHandler.process() method and there include the code involved in processing combinations.

Users of the library then pass a class that implements the CombinationHandler interface into the recursive function in Example 3(a); this instance propagates throughout the stack so that the recursive method can use it as needed. When a solution is found, the recursive method calls the CombinationHandler.process() method with the current solution as an argument; this call passes the general routine's solution to application-specific code. Thus, as aforementioned, a general routine can be customized with specific functionality.

A Multithreaded Solution

However, there's arguably a much better solution, one that expresses the problem more simply and even, in certain environments, yields performance improvements. In any situation where you're producing combinations, there are logically two pieces of your program: the piece that produces the combinations and the one that uses them. If you separate these two logical groupings into two separate threads, a straightforward solution comes together quickly, and it meets both goals — reusability and memory savings.

The recursive method in Listing One is run inside a thread begun when the enclosing Combinations iterator class is instantiated; it acts as a "producer" thread, doing the work necessary to produce a set of combinations. Separately, the next() and hasNext() methods act in a "consumer" thread. These two functions are exposed as part of the Iterator interface; they're available to our caller, which can process their results without any idea of how the results are actually obtained. The recursive solution is hidden, as is, for most purposes, the presence of a second thread. And no new interface, such as CombinationHandler, encumbers users of this class; callers can deal with results just as if they'd called any other Iterator. (Of course, this Iterator is one that doesn't implement the remove() method since there's no backing list.)

The key modification to the original algorithm this approach represents is the interruption of the recursive method by synchronization logic. Effectively, this turns a recursive algorithm with state represented by a run-time stack into one that can be asked, "What's the next solution?" This is done without substituting a more complicated algorithm that requires state to be passed to it in order to reestablish context; the recursive algorithm is simply directed to halt and hold its state until new solutions are needed. In fact, the algorithm remains simple: The synchronization logic is the same no matter what level of the recursion finds a solution and thus needs to run through it.

As mentioned, this approach also yields a potential performance improvement. In an environment where there are multiple processors, or even merely if the consuming thread involves some processing where the CPU doesn't need to be entirely busy (such as if it ever waits for I/O), then the producing thread can continue to run, preparing the next combination. In these cases, if the processing that the consuming thread performs is lengthy enough, the next combination will generally be ready by the time it's needed. Admittedly, the time saved for each combination is likely going to be small, but since the number of overall combinations can be so large, this improvement can be significant.

You might claim that my initial goal is compromised: I was attempting to save memory by not storing all solutions at once, but instead I need to store a run-time stack (to support the recursion) throughout the entire lifetime of the extra thread. But this run-time stack is, in almost all cases, substantially smaller than the entire solution set would be. For the particular example I've been using, I'll need a quantity of stack frames at most equal to the number of elements in the underlying set; each frame stores normal stack-preservation information as well as a handful of small variables. The BitSet used by all levels of the recursion is the same BitSet; just a reference is passed, and all computation is performed in place. You only clone the BitSet when you hand it off to the consumer thread, and you do that just so that you can immediately continue processing without worrying that you might be overwriting data on which the consumer depends. Of course, the consumer can keep in memory each cloned BitSet it receives, invalidating any potential storage advantage — but that's the consumer code's choice. If it needs only to consider each BitSet in turn, letting previous BitSets be garbage collected, then this approach can yield the memory savings you were looking for.

Daemon Threads and User Threads

Java Threads have a daemon attribute that affects the way the JVM handles application completion. An application is considered to be finished when all of its normal, or user, threads are finished. A thread can be set as a daemon thread with Thread.setDaemon(); applications with user threads that are completed but with daemon threads that remain running are still considered to be completed, and the JVM can exit even if that involves precipitously halting any remaining daemon threads.

The worker thread in our example is, in some ways, an ideal candidate for status as a daemon thread, since it exists solely to serve user threads and requires no cleanup of its own (a requirement that would preclude abrupt termination). Consider what would happen if this thread were not set as a daemon thread. Suppose the code that handles combinations is simply looking for a particular combination and doesn't need to enumerate them all. When this code finds what it is looking for, it moves on to other processing, and eventually the application terminates. If the application does not call System.exit(), the JVM will be left hanging, for the combination-producing thread has not completed and will never complete.

Setting the worker thread as a daemon thread avoids this problem. Because the presence of this extra thread is otherwise not important to an application (since it consumes almost no resources other than the small amount of memory previously discussed), the presence of this extra daemon thread can be all but forgotten by the library users.

Conclusion

I've presented several strategies that attempt to adapt a generally memory-intensive recursive algorithm for use in environments where memory may be limited and reusability is required. Building an entire solution set and then returning it to the caller may use too much memory. Processing solutions inline within the library prevents it from being reusable. Using a callback-like methodology is adequate, but encumbers users with an extra, moderately awkward interface. A multithreaded solution that separates the producer and consumer seems more logical; it creates sensible groupings of code, allows for in-place computation of solutions (involving memory used to keep the run-time stack but avoiding storage of a potentially vast solution set), and even yields a performance improvement in I/O-bound applications or those running on multiple processors. Multithreading should be looked at not merely as a technique appropriate to situations where concurrency is required; it remains, as well, a tool that assists you in breaking apart separate pieces of an application, helping to make the overall solution simpler.

The example presented here is an interesting case where systems-oriented techniques are used to solve problems generally considered the domain of theoretical algorithms. In a purely functional language, by contrast, where side effects are not tolerated, you do not have the control over the system necessary to implement a solution like the one described here. The ability to interrupt a recursive algorithm with synchronization logic used to communicate solutions to a separate thread across shared memory leads to a useful and productive adaptation of what remains, at heart, a simple and elegant algorithm.

References

Lea, Doug. Concurrent Programming In Java: Design Principles and Patterns, Second Edition, Addison-Wesley, 2000.

DDJ

Listing One

package com.shawnbayern.util;
import java.util.*;
import java.lang.reflect.*;

/**
 *  A class that acts as an Iterator that walks through combinations
 *  over the class's input (an array).  The order of items in each
 *  combination is, incidentally, guaranteed to be the same as the
 *  order of those same items in the original array.
 */

public class Combinations implements Iterator {

    /**
     *  For testing.
     *  Example:  java com.shawnbayern.util.Combinations abcdefg 5
     */
    public static void main(String args[]) {
        // convert the first argument into a Character[]
        char[] full = args[0].toCharArray();
        Character[] fullCollection = new Character[full.length];
        for (int i = 0; i < full.length; i++)
            fullCollection[i] = new Character(full[i]);

        // get the combination size requested
        int combSize = Integer.parseInt(args[1]);

        // print out a list of combinations
        Iterator i = new Combinations(fullCollection, combSize);
        while (i.hasNext()) {
            Character[] curComb = (Character []) i.next();
            for (int j = 0; j < curComb.length; j++)
                System.out.print(curComb[j]);
            System.out.println();
        }
    }

    Object[] a;                         // the array we handle
    int n;                              // size of combinations
    BitSet latest = null;               // shared between threads
    boolean needNewLatest = false;      // do we need a new BitSet?
    Object latestSync = new Object();   // used just for its monitor
    boolean hasNextShouldFetch = true;  // should hasNext fetch?  has
                                        // the last one been used?

    /**
     *  Returns a new Combinations Iterator for all combinations of
     *  size n out of array a.
     */
    public Combinations(Object[] a, final int n) {
        if (n > a.length)
            throw new IllegalArgumentException(
                "combination size cannot be larger than array size");
        if (n < 0)
            throw new IllegalArgumentException(
                "combination size cannot be negative");

        this.a = a;
        this.n = n;

        // start our worker thread
        Thread t = new Thread(new Runnable() {
            public void run() {
                startBitCombinationsIteration(n);
            }
        });
        t.setDaemon(true);
        t.start();
    }


    /** Returns true if we have another combination to present. */
    public boolean hasNext() {
        /*
         * This method does the actual work; next() is just a thin
         * shell that calls us (to confirm the presence of a new entry
         * and, then, to read it).
         *
         * We therefore don't want to run multiple times in a row,
         * without an intervening call to next().
         *
         * Thus, simply return status -- that is, don't do the
         * internal work involved in getting a new BitSet -- if we
         * were called more recently than next() or otherwise
         * instructed not to run.
         */
        if (!hasNextShouldFetch)
            return (latest != null);

        /*
         * After this iteration, don't run again until someone
         * else asks for us
         */
        hasNextShouldFetch = false;

        // consume the combination
        try {
            synchronized (latestSync) {
                needNewLatest = true;
                latestSync.notify();  // signal that we're ready
                latestSync.wait();    // wait for the worker thread
            }
            return (latest != null);
        } catch (InterruptedException ex) {
            // shouldn't happen
            throw new IllegalStateException(
                "hasNext shouldn't have been interrupted");
        }
    }


    /** Returns the next combination we have to present. */
    public Object next() {
        // let hasNext() do the work
        if (!hasNext())
            throw new NoSuchElementException();

        /*
         * Apply the BitSet to array a.  That is, produce a new
         * array of the same type as a and fill it with every
         * element whose index corresponds to a 1 bit in the BitSet.
         * We don't do any of the real work in determining the
         * combinations; we just use the 'latest' one that's been
         * found and let hasNext() keep it up to date.
         */
        Object c = Array.newInstance(a[0].getClass(), n);
        for (int j = 0, k = 0; j < a.length; j++)
            if (latest.get(j))
                Array.set(c, k++, a[j]);

        hasNextShouldFetch = true;        // we'll want another one
        return c;
    }


    /** Just to fulfill the contract. */
    public void remove() {
        throw new UnsupportedOperationException();
    }


    /** Starts computation of combinations. */
    private void startBitCombinationsIteration(int n) {
        BitSet bs = new BitSet();
        getBitCombinations(bs, 0, 0, n);

        /*
         * Now that our recursion's done, we need to wait until a new
         * 'latest' is needed and then set it to null to indicate that
         * we have nothing more to present
         */
        try {
            synchronized(latestSync) {
                while (!needNewLatest) {
                    latestSync.wait();
                }
                latest = null;
                needNewLatest = false;
                hasNextShouldFetch = false;  // nothing more to get
                latestSync.notify();         // signal that we're done
            }
        } catch (InterruptedException ex) {
            // shouldn't happen
            throw new IllegalStateException(
                "startBitCombinationsIteration "
                + "shouldn't have been interrupted");
        }
    }


    /** Recursively performs the work of startBitCombinations above. */
    private void getBitCombinations(
                BitSet bs, int start, int current, int target) {
        try {
            if (current == target) {
                synchronized(latestSync) {
                    while (!needNewLatest) {
                        latestSync.wait();  // wait until we're needed
                    }

                    /*
                     * clone it so that we can continue working on
                     * the original, preparing the next 'latest' for
                     * when it's needed
                     */
                    latest = (BitSet) bs.clone();
                    needNewLatest = false;

                    latestSync.notify();  // signal that we're done
                }
                return;
            }
        } catch (InterruptedException ex) {
            // shouldn't happen
            throw new IllegalStateException(
                "getBitCombinations shouldn't have been interrupted");
        }

        if (start == a.length)
            return;

        bs.set(start);
        current++;
        getBitCombinations(bs, start + 1, current, target);

        bs.clear(start);
        current--;
        getBitCombinations(bs, start + 1, current, target);

    }
}

Back to Article


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.