I have such code
senders.FirstOrDefault(sender => !sender.IsBusy);
This line is called pretty often.
The problem is that it always returns the first non-busy sender; the same first sender is returned pretty often, but the last one is returned very rarely. How to easily balance this?
Ideally, on every call I should return the most rarely used sender. I.e. between all non-busy senders select the one that was selected the least number of times during the last second.
Maybe something like:
public static T RandomOrDefault<T>(this IEnumerable<T> dataSet)
{
return dataSet.RandomOrDefault(y => true);
}
public static T RandomOrDefault<T>(this IEnumerable<T> dataSet, Func<T, bool> filter)
{
var elems = dataSet.Where(filter).ToList();
var count = elems.Count;
if (count == 0)
{
return default(T);
}
var random = new Random();
var index = random.Next(count - 1);
return elems[index];
}
then you can call it with:
senders.RandomOrDefault(sender => !sender.IsBusy);
If you want to get the least used one efficiently you will be probably good with the following non-Linq 'list rotation' solution, which is O(n) effiency and O(1) space unlike most of others:
// keep track of these
List<Sender> senders;
int nSelected = 0; // number of already selected senders
// ...
// solution
int total = senders.Count; // total number of senders
// looking for next non-busy sender
Sender s = null;
for (int i = 0; i < total; i++)
{
int ind = (i + nSelected) % total; // getting the one 'after' previous
if (!senders[ind].IsBusy)
{
s = senders[ind];
++nSelected;
break;
}
}
Of course this adds the must-be-indexable constraint on senders container.
You could easily reorder by a new Guid, like this:
senders.Where(sender => !sender.IsBusy).OrderBy(x => Guid.NewGuid()).FirstOrDefault();
You don't mess with random numbers, you don't have to identify a "range" for these numbers. It just plain works and it's pretty elegant, I think.
Keep a look-up of senders that you have used and the time when they were used.
var recentlyUsed = new Dictionary<Sender, DateTime>();
var sender = senders.FirstOrDefault(sender => !sender.IsBusy && (!recentlyUsed.ContainsKey(sender) || recentlyUsed[sender] < DateTime.Now.AddSeconds(-1)));
if (sender != null)
recentlyUsed[sender] = DateTime.Now;
You could use Skip with a random number less than the total number of non-busy senders.
senders.Where(sender => !sender.IsBusy).Skip(randomNumber).FirstOrDefault();
Identifying a sensible limit for the random number might be a bit tricky though.
Based on algorithm from the "Real world functional programming" book here's the O(n) implementation of extension method for taking random or default value from IEnumearble.
public static class SampleExtensions
{
// The Random class is instantiated as singleton
// because it would give bad random values
// if instantiated on every call to RandomOrDefault method
private static readonly Random RandomGenerator = new Random(unchecked((int)DateTime.Now.Ticks));
public static T RandomOrDefault<T>(this IEnumerable<T> source, Func<T, bool> predicate)
{
IEnumerable<T> filtered = source.Where(predicate);
int count = 0;
T selected = default(T);
foreach (T current in filtered)
{
if (RandomGenerator.Next(0, ++count) == 0)
{
selected = current;
}
}
return selected;
}
public static T RandomOrDefault<T>(this IEnumerable<T> source)
{
return RandomOrDefault(source, element => true);
}
}
Here's the code to ensure that this algorithm really gives the Uniform distribution:
[Test]
public void TestRandom()
{
IEnumerable<int> source = Enumerable.Range(1, 10);
Dictionary<int, int> result = source.ToDictionary(element => element, element => 0);
result[0] = 0;
const int Limit = 1000000;
for (int i = 0; i < Limit; i++)
{
result[source.RandomOrDefault()]++;
}
foreach (var pair in result)
{
Console.WriteLine("{0}: {1:F2}%", pair.Key, pair.Value * 100f / Limit);
}
Console.WriteLine(Enumerable.Empty<int>().RandomOrDefault());
}
The output of TestRandom method is:
1: 9,92%
2: 10,03%
3: 10,04%
4: 9,99%
5: 10,00%
6: 10,01%
7: 9,98%
8: 10,03%
9: 9,97%
10: 10,02%
0: 0,00%
0
