3
\$\begingroup\$

So I just wrote the following extension method to do roulette selection on a generic list. I'm specifically unsure of the use of the while loop. Is this beautiful or a disgusting mess?

// This is either yuck or beautiful
public static T rouletteSelect<T>(this List<T> list, Func<T, double> fitnessFunc, double max)
{
    T selected;
    while (fitnessFunc(selected = list.getRandom()) / max <= Rand.NextDouble()) { }
    return selected;
}
\$\endgroup\$
0

1 Answer 1

3
\$\begingroup\$

I am on the it's disgusting side.

I usually think at extension methods as something that could be useful by themselves. In your case you need to provide some external context with max, which could lead to confusing code. Who should be in charge of updating it? In my opinion you should have something that has both the responsibilities of keeping track of the current max values and to select the next one.

Also, I'm not sure if you're talking about this selection method, but there they divide the fitness value of an item by the sum of the fitness values of all the items, not by a maximum value.

You cannot test it. The calls to list.getRandom() and Rand.NextDouble() make it impossible. I'd rather make the dependencies on random number generators explicit.

As a matter of style I don't like having an empty body for a loop.

Given that you want to implement the selection method I linked earlier, I'd probably go for another different approach. I'm not sure yours actually implements it (but I have not looked at it for long enough to be sure it doesn't work as you would expect to).

public static T RouletteSelect<T>(this List<T> list, Func<T, double> fitnessFunction, double randomValue)
{
    var fitnessValues = list.Select(x => fitnessFunction(x));
    var totalFitness  = fitnessValues.Sum();
    var probabilities = fitnessValues.Select(x => x/totalFitness).ToList();
    var i = 0;
    var sum = probabilities[0];
    while(randomValue <= sum)
    {
      i = i + 1;
      sum += probabilities[i];
    }
    return list[i];
}
\$\endgroup\$
6
  • \$\begingroup\$ I do have need for this in enough varying contexts in my project that the making it an extension method does make sense, and the use of max rather than total also makes sense in my context. I can confirm that my method works. The testability point is a good one and one I had not thought of. Can you elaborate at all on your thoughts on the empty while? \$\endgroup\$ Commented Aug 6, 2014 at 21:29
  • \$\begingroup\$ What is the probability of picking an item you want to obtain with your code? \$\endgroup\$ Commented Aug 6, 2014 at 21:32
  • \$\begingroup\$ It varies significantly between use cases. Values can reasonably be expected to range from 0.01 through to 0.99. Speed is a (genuine) concern. \$\endgroup\$ Commented Aug 6, 2014 at 21:52
  • \$\begingroup\$ I am a bit confused. Maybe it is just because I associate with the name roulette select the method I linked and it looks you're implementing it in a quite different way. My question about probabilities wanted to be more specific. With the method in my answer probabilities are $$p_i = \frac{f_i}{\Sigma_{j=1}^{N} f_j}$$. What are with yours? \$\endgroup\$ Commented Aug 6, 2014 at 22:00
  • \$\begingroup\$ Are mine not exactly the same? They should be exactly the same. My method is actually pretty much exactly the one described in the last paragraph of the article you linked. \$\endgroup\$ Commented Aug 6, 2014 at 22:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.