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 any source code examples on my blog for a long time. And do not worry. A Technical Lead can also prepare some C# code :). So, let’s start. Like every TDD story, 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. The first branch (1) has three elements (11, 12, and 13). The second branch has two elements (21 and 22). But the advantage of that decision tree is an iterate feature that uses a key with probability. So you may wonder about the output of this test and the results of them. The 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 decide about choosing elements, and when I iterate 1000 times I have exactly 1000 times the sums of probabilistic decisions. So you may wonder how to use this Probabilistic Tree more conveniently? Ok, I will show you another TDD code story below. This time it will be a 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 straightforward to understand, I have 4 queues with different counts at the beginning, and I try to make a decision how to remove elements of that 4 queues. I wish at the end to have empty queues, but somehow I would like to figure out very fast about the correct order in an easy way. The decision is more difficult because I try to add 100 extra elements to queues in the parallel process. And with that, making a load balance decision is more difficult. So, you may wonder about output, and here it is.
DeQueues: 4232123434444414424332134214323314123244242443444244244441432133212223 4324432444443244424243433324412422424344444313442234243444242144223334 2442341343344234344242333241414433243444421224444143323323343133234341 4413131242124124334424143343444323344422334344344342444434234224434244 4343241424124243433313424341413414413244421121343141424344244342224442 4341232344444431334414434334244442431334224224111224114424412344434334 3343442442344144441341334242141244324444244143144444242144243344331432 2421424143422322132222424124411223343332242111221441422444411334213212 4342443414143443441312434244124121331442212343312232413112344241432444 1323441443324332432443142443331111441231342231133313314423423422343443 4414434224442322224313144221344434124444411442424343324422324234432334 3122432313333414224342442342144142334424434242142334243441422442244114 4134244442344423414434212423432234432211342142324434414314422244314144 3221243241231442222144244424434414312424324441242242344324432342334434 4344321444221313422342442143344141131344424242311224134244232434313433 4224334314422344423333423311441214434421212322213442 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 it? Did you see the advantages that this 4 queue can be changed in time and in a different way, and this is a 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 ;).