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.
