Living without a constraint solver

For a while I was hooked on constraint solvers, to the point I relied on them to solve even the most simplistic problem, paying a hefty price in simulation time. One of those simple problems is selecting values from a list. The typical wrong way to do this is with the constraint solver. You’d usually declare a constraint like this:

class A {
  rand integer thing;
  constraint my_con {
    thing in {7,8,34};
  }
}

Obviously, this is short and sweet, but picking a value for the “thing” variable invokes the constraint solver. It is much more efficient to approach the problem by randomly picking from a list:

integer things[] = [7,8,34];
thing = things[random()%things.length];

A variant of that is when we want to pick a sequence of things, without repetition. Once we’ve gone through the sequence, we want to shuffle it and start over. I coded the following in D, to demonstrate:


import tango.io.Stdout;
import tango.math.Random;

// The Knuth Shuffle (from wikipedia)
void shuffle(int [] list) {
  auto rand = new Random();
  int n = list.length;
  while (--n > 0) {
    int k = rand.next(n+1);
    int temp = list[n];
    list[n] = list[k];
    list[k] = temp;
  }
}

class Buffer {
  int size;
  byte [] data;
  this(int size) {
    this.size = size;
  }
}

void main() {
  // Some buffers with interesting sizes
  Buffer [] buffers;
  buffers.length = 3;
  buffers[0] = new Buffer(7);
  buffers[1] = new Buffer(8);
  buffers[2] = new Buffer(34);

  // A list of numbers
  int [] list;
  list.length = buffers.length;
  foreach(idx, ref value;list) value = idx;
  shuffle(list);

  // Use the shuffled list to traverse
  // the list of buffers in random order
  foreach(idx,value;list) {
    Stdout.formatln(
      "buffers[{0}].size = {1}",
      idx,
      buffers[value].size
    );
  }
}

Shuffling the list is a O(n) operation, and there is no need to invoke a constraint solver. Each time you need to go through a list of things in random order, you can use the shuffled list of integers to traverse it.

Advertisements

2 Responses to Living without a constraint solver

  1. Paddy3118 says:

    Why D and not Python?
    random.shuffle is included and does the Knuth thing.

  2. Martin d'Anjou says:

    I was learning D at he time I wrote the article, and just felt like trying it in D.

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

%d bloggers like this: