The Rain and The Shade

July 1, 2011

Generating Weighted Random

Filed under: C# Coding — ovaisakhter @ 2:02 pm

Have you ever been given a requirement by the Business people something like, we want 5% of the visitors of the site to look at the participate in the survey. The first thought that comes to your mind (At least it came in my mind) that we will need to maintain a data store where will maintain count of all the visitors. We will show the popup to every 5th visitor or something like that. When your code is deployed into load balanced  environment then this data store will be some database and then things begin to become hairy you need to deal with problems like locking and concurrency, and most importantly performance, and interestingly you will never be able to get the exact percentage without seriously hurting the performance.

The situation will also become interesting when the requirement will become like 10% will see survey 1, 20% will see survey number 2 and rest will not see any survey.

Some while back I was facing the same problem a friend of mine(Mads Voigt Hingelberg) suggested me a great way out.

It is very simple if you think about it.

Take the example I described above, when a user comes generate a random number from 0 to 100 if this number is from 0 to 10 show him the survey 1, if it is from 10 to 30 show him the survey 2 and if the number is above 30 do not show him anything. This approach may not give you 100% accurate results (which you will not be getting that anyway) but if you take a large enough sample you will see the values are pretty close to what you are looking for.

I wrote a simple class to handle this problem generically.

public class WeightedRandom<T> {
 private readonly List<Range<T>> _cases = new List<Range<T>>(); private static readonly object LockObject = new object();
 private readonly Random _rand = new Random();
  public WeightedRandom(IEnumerable<WeightedRandomDto<T>> cases) { if (cases.Sum(x=>x.Percentage) != 100)
 { throw new ApplicationException("The total of the percentages should be exactly 100");
 }
 var tmpCases = cases.OrderBy(a => a.Percentage);
 var from = 0;
 foreach (var weightedRandomEntry in tmpCases) {
 var range = new Range<T> {Object = weightedRandomEntry.Object, To = from + weightedRandomEntry.Percentage};
 if (from != 0) {
 range.From = from + 1; }
 from = range.To ; _cases.Add(range);
 }
 }
 public T GetNext() {
 lock (LockObject) {
 var random = GetRandom();
 foreach (var range in _cases)
 {
 if (range.From <= random && random <= range.To) {
 return range.Object; }
 }
 return default(T); }
 }   private struct Range<TP>
 { public TP Object { get; set; }
 public int From { get; set; } public int To { get; set; }
  }
 private int GetRandom() {
 var ret = _rand.Next(0,100); return ret;
 } } the constructor takes a collection of
 public struct WeightedRandomDto<T>
    {
        public WeightedRandomDto(int percentage, T obj)
            : this()
        {
            Percentage = percentage;
            Object = obj;
        }
 
        public int Percentage { get; private set; }
        public T Object { get; private set; }
    }

Here is the code that you can use to use this

var list = new List<WeightedRandomDto<string>>
 { new WeightedRandomDto<string>(10, "case 1"),  new WeightedRandomDto<string>(30, "case 2"), new WeightedRandomDto<string>(30, "case 4"), new WeightedRandomDto<string>(30, "case 5") }; _weightedRandom = new WeightedRandom<string>(list.ToArray()); var ret = _weightedRandom.GetNext();

Have fun and do remember to share your feedback.

Advertisements

1 Comment »

  1. Nice idea to solve an interesting problem 🙂 — Aakif Hassan

    Comment by Aakif Hassan — July 2, 2011 @ 9:11 pm | Reply


RSS feed for comments on this post. TrackBack URI

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

Create a free website or blog at WordPress.com.

%d bloggers like this: