The Beauty of 70 lines of C# 4.0 code – the Probabilistic Tree

Hi, Today I would like to tell you a TDD story about the Probabilistic Tree. I would like to do that because I did not show on my blog any source code example for a long time. And do not worry a Technical Lead can also prepare some C# code :). So, let start, like every TDD stories this one should begin with a Test method. So here is a code – use case stories of my Probabilistic Tree.

namespace ProbabilisticComposite
{
  using System;
  using NUnit.Framework;
  using System.Threading.Tasks;

  [TestFixture]
  public class ProbeCompositeTests
  {
    [Test]
    public void ProbeCompositeTest001()
    {
      var probeComposite0 = new ProbeComposite<int>(0);
      var probeComposite1 = new ProbeComposite<int>(1);
      var probeComposite2 = new ProbeComposite<int>(2);

      probeComposite0.Elements.TryAdd(new ProbeKey(20m), probeComposite1);
      probeComposite0.Elements.TryAdd(new ProbeKey(80m), probeComposite2);

      probeComposite1.Elements.TryAdd(new ProbeKey(20m), new ProbeComposite<int>(11));
      probeComposite1.Elements.TryAdd(new ProbeKey(40m), new ProbeComposite<int>(12));
      probeComposite1.Elements.TryAdd(new ProbeKey(40m), new ProbeComposite<int>(13));

      probeComposite2.Elements.TryAdd(new ProbeKey(25m), new ProbeComposite<int>(21));
      probeComposite2.Elements.TryAdd(new ProbeKey(75m), new ProbeComposite<int>(22));

      var e1Count = 0;
      var e2Count = 0;
      var e11Count = 0;
      var e12Count = 0;
      var e13Count = 0;
      var e21Count = 0;
      var e22Count = 0;

      var count = 1000;

      Parallel.For(0, count, (i) =>
      {
        foreach (var element in probeComposite0)
        {
          switch (element.Element)
          {
            case 1:
              lock (this)
                e1Count++;
              break;
            case 2:
              lock (this)
                e2Count++;
              break;
            case 11:
              lock (this)
                e11Count++;
              break;
            case 12:
              lock (this)
                e12Count++;
              break;
            case 13:
              lock (this)
                e13Count++;
              break;
            case 21:
              lock (this)
                e21Count++;
              break;
            case 22:
              lock (this)
                e22Count++;
              break;
          }
        }
      });

      Console.WriteLine("Test Counters:");

      Console.WriteLine("C01: {0}", e1Count);
      Console.WriteLine("C02: {0}", e2Count);
      Console.WriteLine("C11: {0}", e11Count);
      Console.WriteLine("C12: {0}", e12Count);
      Console.WriteLine("C13: {0}", e13Count);
      Console.WriteLine("C21: {0}", e21Count);
      Console.WriteLine("C22: {0}", e22Count);

      Console.WriteLine("C01+C02: {0}", e1Count + e2Count);
      Console.WriteLine("C11+C12+C13: {0}", e11Count + e12Count + e13Count);
      Console.WriteLine("C21+C22: {0}", e21Count + e22Count);

      Assert.AreEqual(count, e1Count + e2Count);
      Assert.AreEqual(count, e11Count + e12Count + e13Count);
      Assert.AreEqual(count, e21Count + e22Count);
    }
  }
}

As you can see I have a tree with root element (0) and with two branches (1 and 2). And those two branches have elements. First branch (1) has three elements (11, 12 and 13). The second branch has two elements (21 and 22). But the real advantages of that kind of decision tree is an iterate feature that uses a key with probability. So you may wonder about the output of this test and results of them. Result is Pass (with time: 0,046 seconds) and the output is shown below.

Test Counters:
C01: 192
C02: 808
C11: 186
C12: 405
C13: 409
C21: 233
C22: 767
C01+C02: 1000
C11+C12+C13: 1000
C21+C22: 1000

And what do you think? Do you catch the point of this idea? By iterating by the tree I can make a decision about choosing elements and when I iterate 1000 times I have exactly 1000 times sums of probabilistic decisions. So you may wonder how to use this Probabilistic Tree more convenient? Ok, I will show you another TDD code story below. This time it will be Console Application use case kind of test.

namespace ProbabilisticComposite
{
  using System;
  using System.Collections.Concurrent;
  using System.Threading.Tasks;
  
  class Program
  {
    static void Main()
    {
      var concurrentQueue1 = new ConcurrentQueue<int>();
      for (int i = 0; i < 100; i++)
        concurrentQueue1.Enqueue(1);

      var concurrentQueue2 = new ConcurrentQueue<int>();
      for (int i = 0; i < 200; i++)
        concurrentQueue2.Enqueue(2);

      var concurrentQueue3 = new ConcurrentQueue<int>();
      for (int i = 0; i < 250; i++)
        concurrentQueue3.Enqueue(3);

      var concurrentQueue4 = new ConcurrentQueue<int>();
      for (int i = 0; i < 450; i++)
        concurrentQueue4.Enqueue(4);

      var probeComposite0
        = new ProbeComposite<ConcurrentQueue<int>>(new ConcurrentQueue<int>());

      probeComposite0.Elements
        .TryAdd(
          new ProbeKey(concurrentQueue1.Count,
            () => (decimal)(concurrentQueue1.Count)),
          new ProbeComposite<ConcurrentQueue<int>>(concurrentQueue1));

      probeComposite0.Elements
        .TryAdd(
          new ProbeKey(concurrentQueue2.Count,
            () => (decimal)(concurrentQueue2.Count)),
          new ProbeComposite<ConcurrentQueue<int>>(concurrentQueue2));

      probeComposite0.Elements
        .TryAdd(
          new ProbeKey(concurrentQueue3.Count,
            () => (decimal)(concurrentQueue3.Count)),
          new ProbeComposite<ConcurrentQueue<int>>(concurrentQueue3));

      probeComposite0.Elements
        .TryAdd(
          new ProbeKey(concurrentQueue4.Count,
            () => (decimal)(concurrentQueue4.Count)),
          new ProbeComposite<ConcurrentQueue<int>>(concurrentQueue4));

      Console.WriteLine("DeQueues:");
      Parallel.For (0, 1100, (i) =>
      {
        if (i >= 50 && i <= 100)
          concurrentQueue1.Enqueue(1);
        if (i >= 100 && i <= 150)
          concurrentQueue2.Enqueue(2);        
        foreach (var queue in probeComposite0)
        {
          int element;
          queue.Element.TryDequeue(out element);
          Console.Write(element);
        }
      });      
      Console.WriteLine();

      Console.WriteLine("Q1C: {0}", concurrentQueue1.Count);
      Console.WriteLine("Q2C: {0}", concurrentQueue2.Count);
      Console.WriteLine("Q3C: {0}", concurrentQueue3.Count);
      Console.WriteLine("Q4C: {0}", concurrentQueue4.Count);

      Console.ReadKey();
    }
  }
}

I think it is very easy to understand, I have 4 queues with the different count at the beginning and I try to make a decision how to remove elements of that 4 queues. I wish at the end have empty queues but in somehow I would like to figure out very fast about the correct order in an easy way. The decision is more difficult because in the parallel process I try to add 100 extra elements to queues. And with that making load balance decision is more difficult. So, you may wonder about an output and here it is.

DeQueues:
4232123434444414424332134214323314123244242443444244244441432133212223
4324432444443244424243433324412422424344444313442234243444242144223334
2442341343344234344242333241414433243444421224444143323323343133234341
4413131242124124334424143343444323344422334344344342444434234224434244
4343241424124243433313424341413414413244421121343141424344244342224442
4341232344444431334414434334244442431334224224111224114424412344434334
3343442442344144441341334242141244324444244143144444242144243344331432
2421424143422322132222424124411223343332242111221441422444411334213212
4342443414143443441312434244124121331442212343312232413112344241432444
1323441443324332432443142443331111441231342231133313314423423422343443
4414434224442322224313144221344434124444411442424343324422324234432334
3122432313333414224342442342144142334424434242142334243441422442244114
4134244442344423414434212423432234432211342142324434414314422244314144
3221243241231442222144244424434414312424324441242242344324432342334434
4344321444221313422342442143344141131344424242311224134244232434313433
42243343144223444233334233114412144344212123222134420
Q1C: 0
Q2C: 0
Q3C: 0
Q4C: 0

So I had all of four empty queues with output with order. So, it is a pretty nice decision tree, isn’t? Did you see advantages that this 4 queue can be changed in time and in a different way and this is kind of load balancer for them? And at last of my story, I would like to show the beauty of 70 lines of code. The Probabilistic Tree Implementation is shown below.

namespace ProbabilisticComposite
{
  using System;
  using System.Collections.Generic;
  using System.Collections.Concurrent;
  using System.Runtime.CompilerServices;

  public class ProbeKey
  {
    public decimal Probability { get; private set; }
    private Func<decimal> CurrentProbeFunc { get; set; }

    public ProbeKey(decimal beginProbability, Func<decimal> currentProbeFunc = null) {
      Probability = beginProbability;
      CurrentProbeFunc = currentProbeFunc;
    }

    internal void TryRefreshProbability() {
      if (CurrentProbeFunc != null)
        Probability = CurrentProbeFunc();
    }
  }

  public class ProbeComposite<T> : IEnumerable<ProbeComposite<T>>
  {
    public T Element { get; private set; }
    public ConcurrentDictionary<ProbeKey, ProbeComposite<T>> Elements { get; private set; }

    public ProbeComposite(T element) {
      Element = element;
      Elements = new ConcurrentDictionary<ProbeKey, ProbeComposite<T>>();
    }

    private static readonly Random RandomGen = new Random(DateTime.UtcNow.Millisecond);

    [MethodImplAttribute(MethodImplOptions.Synchronized)]
    private static decimal CalculateThreshold(decimal probeSum) {
      return probeSum * (decimal)RandomGen.NextDouble();
    }

    public IEnumerator<ProbeComposite<T>> GetEnumerator() {
      var probeSum = 0m;
      foreach (var element in Elements.Keys)
      {
        element.TryRefreshProbability();
        probeSum += element.Probability;
      }
      var threshold = CalculateThreshold(probeSum);
      var thresholdLookUp = 0m;
      var thresholdLookDown = 0m;

      foreach (var element in Elements)
      {
        thresholdLookUp += element.Key.Probability;

        if (threshold < thresholdLookUp && threshold >= thresholdLookDown)
          yield return element.Value;

        thresholdLookDown += element.Key.Probability;

        foreach (var elementOfElemnts in element.Value)
          yield return elementOfElemnts;
      }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
      return GetEnumerator();
    }
  }
}

I hope you enjoy this little TDD story :).

Regards,

P ;).

Leave a Reply

Your email address will not be published. Required fields are marked *

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.