2
\$\begingroup\$

I'm looking for some improvements for my generic Roulette class. More information on how the class works is better described, here: https://en.m.wikipedia.org/wiki/Fitness_proportionate_selection

public class Roulette<T>
{
    public string Name;
    private Dictionary<T, double> _items;


    /// <summary>
    /// Calculates the total remaining probability-space within this Roulette.
    /// </summary>
    public double FreeSpace
    {
        get
        {
            return 1.0 - UsedSpace;
        }
    }

    /// <summary>
    /// Calculates the total used probability-space within this Roulette.
    /// </summary>
    public double UsedSpace
    {
        get
        {
            double total = 0;
            foreach (KeyValuePair<T, double> keyValuePair in _items)
            {
                total += keyValuePair.Value;
            }
            return total;
        }
    }

    /// <summary>
    /// Returns true if the collective probabilities of the Roulette
    /// add up to 1.0 (100%). A table is only valid if all items add
    /// up to 1.0, however, this is intentionally not enforced in the
    /// code due to performance concerns.
    /// </summary>
    public bool IsValid
    {
        get
        {
            return UsedSpace == 1.0;
        }
    }

    public Roulette()
    {
        this._items = new Dictionary<T, double>();
    }

    public Roulette(string name)
    {
        this.Name = name;
        this._items = new Dictionary<T, double>();
    } 

    public Roulette(Dictionary<T,double> items )
    {
        this._items = items;
    }

    /// <summary>
    /// Clears all items from this Roulette.
    /// </summary>
    public void Clear()
    {
        this._items.Clear();
    }

    /// <summary>
    /// Adds the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    /// <param name="probability">The probabilityof this item.</param>
    public void Add(T item, double probability)
    {
        this._items.Add(item,probability);
    }

    /// <summary>
    /// Adds the specified items.
    /// </summary>
    /// <param name="items">The items.</param>
    public void Add(Dictionary<T, double> items)
    {
        foreach (KeyValuePair<T, double> keyValuePair in items)
        {
            Add(keyValuePair.Key,keyValuePair.Value);
        }
    }

    /// <summary>
    /// Edits the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    /// <param name="probability">The probability.</param>
    public void Edit(T item, double probability)
    {
        this._items.Remove(item);
        this._items.Add(item, probability);
    }

    /// <summary>
    /// Checks the probability of the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    /// <returns></returns>
    /// <exception cref="System.Exception">Could not find key \ + item +\</exception>
    public double Inspect(T item)
    {
        if (this._items.ContainsKey(item))
        {
            return this._items[item];
        }
        throw new Exception("Could not find key \"" + item +"\"");
    }

    /// <summary>
    /// Determines whether this Roulette contains the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    /// <returns></returns>
    public bool Contains(T item)
    {
        return this._items.ContainsKey(item);
    }

    /// <summary>
    /// Removes the specified item.
    /// </summary>
    /// <param name="item">The item.</param>
    /// <returns>Indicates if the removal was successful</returns>
    public bool Remove(T item)
    {
        return this._items.Remove(item);
    }

    /// <summary>
    /// Generates the next random item from this Roulette.
    /// </summary>
    /// <param name="random">The random.</param>
    /// <returns></returns>
    public T Next(Random random)
    {
        double probabilitySum = 0;
        for (int i = 0; i < this._items.Count; i++)
        {
            probabilitySum += this._items.Values.ElementAt(i);
        }
        double value = random.NextDouble() * probabilitySum;
        for (int i = 0; i < this._items.Count; i++)
        {
            value -= this._items.Values.ElementAt(i);
            if (value <= 0)
            {
                return this._items.Keys.ElementAt(i);
            }
        }
        return this._items.Keys.ElementAt(this._items.Count - 1);
    }

    /// <summary>
    /// Generates an array of random items from this
    /// Roulette.
    /// </summary>
    /// <param name="random">The random.</param>
    /// <param name="count">The count.</param>
    /// <returns></returns>
    public T[] Next(Random random, int count)
    {
        T[] items = new T[count];
        Next(random, items);
        return items;
    }

    /// <summary>
    /// Generates an array of random items from this 
    /// Roulette and initializes the items into a
    /// prebuilt buffer.
    /// </summary>
    /// <param name="random">The random.</param>
    /// <param name="buffer"></param>
    /// <returns></returns>
    public void Next(Random random, T[] buffer)
    {
        for (int i = 0; i < buffer.Length; i++)
        {
            buffer[i] = Next(random);
        }
    }
}

Example Usages:

    Roulette<int> roulette = new Roulette<int>();
    roulette.Add(31,0.05);
    roulette.Add(55, 0.25);
    roulette.Add(338,0.40);
    roulette.Add(28338,0.30);
    Random random = new Random();
    Console.WriteLine(roulette.Next(random));

    Roulette<string> roulette = new Roulette<string>();
    roulette.Add("Cats",0.05);
    roulette.Add("Dogs", 0.25);
    roulette.Add("Squirrels",0.40);
    roulette.Add("Ferrets",0.30);
    Random random = new Random();
    Console.WriteLine(roulette.Next(random));

    Roulette<Size> roulette = new Roulette<Size>();
    roulette.Add(new Size(22,44), 0.05);
    roulette.Add(new Size(55, 45643), 0.25);
    roulette.Add(new Size(4445, 345635), 0.40);
    roulette.Add(new Size(30, 80), 0.30);
    Random random = new Random();
    Console.WriteLine(roulette.Next(random));
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Can you give more descriptive detail on what the class aims to achieve in the question body. \$\endgroup\$ – Tolani Jul 20 '16 at 1:16
  • \$\begingroup\$ @TolaniJaiye-Tikolo Added a link to the wikipedia page, because I'm no longer at home to edit this question correctly. \$\endgroup\$ – Krythic Jul 20 '16 at 1:24
5
\$\begingroup\$
  • Roulette<T>.UsedSpace can be simplified down to _items.Sum(x => x.Value);
  • Roulette<T>.Next(Random) can also be improved :

    public T Next(Random random)
    {
        // I believed you added the IsValid property for a reason, so why not double check it on Next()?
        if (!IsValid) throw new InvalidDataException("The probabilities does not add up to 100%.");
    
        // This sum is simply UsedSpace
        // double probabilitySum = 0;
        // for (int i = 0; i < this._items.Count; i++)
        // {
               // ElementAt is also a horrible way of accessing an item by index
               // when the collection does not implements IList
        //     probabilitySum += this._items.Values.ElementAt(i);
        // }
    
        //double value = random.NextDouble() * probabilitySum;
        var value = random.NextDouble() * UsedSpace;
    
        // the dictionary is iterated twice per for-loop
        // for (int i = 0; i < this._items.Count; i++)
        // {
        //     value -= this._items.Values.ElementAt(i);
        //     if (value <= 0)
        //     {
        //         return this._items.Keys.ElementAt(i);
        //     }
        // }
        foreach(var pair in this._items)
        {
            value != pair.Value;
            if (value <= 0)
            {
                return pair.Key;
            }
        }
    
        // Just visually more appealing, not performance gain
        //return this._items.Keys.ElementAt(this._items.Count - 1);
        return this.Select(x => x.Key).LastOrDefault();
    }
    

If you have access to C# 6.0, you can also take advantage of the few syntax sugars :

  • Dictionary Initializer : You can also derived Roulette<T> from Dictionary<T, double>. By doing so, allows you to define the contents with less typing :

    // old syntax for comparison
    var values = new Roulette<int>()
    values.Add(31, 0.05);
    values.Add(55, 0.25);
    
    // new syntax
    var values = new Roulette2<int>()
    {
        [31] = 0.05,
        [55] = 0.25,
        /* ... */
    };
    
    // In order to use that, you will have to change the Roulette it to the following : 
    public class Roulette2<T> : Dictionary<T, double>
    
    // Note that it will also expose your internal state, and lots of methods to your class
    // But, we can still take advantage of that, while making some compromise with your 2nd ctor(Dictionary) :
    var values = new Roulette<int>(new Dictionary<int, double>
    {
        [31] = 0.05,
        [55] = 0.25,
        /* ... */
    });
    
  • Lambda-bodied property : This could can also be used on methods as well.

    public double FreeSpace => 1.0 - UsedSpace;
    public double UsedSpace => _items.Sum(x => x.Value);
    public bool IsValid => UsedSpace == 1.0;
    
\$\endgroup\$
3
\$\begingroup\$

I focused on simplifying the implementation rather than the actual algorithm:

Many of the method exposed by your Roulette are just proxies for the Dictionary so you could just inherit from the Dictionary.

You could simplify some the Edit by using ConcurrentDictionary, but I don't think you really need it concurrent anyway; your choice.

If you have C# 6 you can make the code less verbose.

LINQ can simplify most of the implementation, hopefully didn't make the code unclear; but usually it's even more understandable in a functional fashion.

I removed some duplication in the constructors as they can call each other.

The equals operator between floats can easily fail for the precision so, as my ReSharper suggested I changed it to have a tolerance which you can set.

The default of KeyValuePair shouldn't cause any issue unless you have a default of both values in the dictionary. Maybe worth a runtime check.

Don't remember if I made other changes, too.

public class Roulette<T> : Dictionary<T, double>
{
    public string Name;

    public double FreeSpace => 1.0 - UsedSpace;

    public double UsedSpace => Values.Sum();

    public bool IsValid => Math.Abs(UsedSpace - 1.0) < 0.1;

    public Roulette() { }

    public Roulette(string name) : this()
    {
        this.Name = name;
    }

    public Roulette(Dictionary<T, double> items)
    {
        AddFromDictionary(items);
    }

    public void AddFromDictionary(Dictionary<T, double> items)
    {
        foreach (var keyValuePair in items)
            Add(keyValuePair.Key, keyValuePair.Value);
    }

    public void Edit(T item, double probability)
    {
        if (ContainsKey(item))
            this[item] = probability;
        else
            Add(item, probability);
    }

    public double Inspect(T item)
    {
        if (ContainsKey(item))
            return this[item];

        throw new KeyNotFoundException($"Could not find key \"{item}\"");
    }

    public bool Contains(T item) => ContainsKey(item);

    public T Next(Random random)
    {
        // Or, as suggested: var value = random.NextDouble() * UsedSpace;
        var value = random.NextDouble() * Values.Sum();

        var valuePair = this.FirstOrDefault(pair => (value -= pair.Value) <= 0);

        return valuePair.Equals(default(KeyValuePair<T, double>)) ? Keys.Last() : valuePair.Key;
    }

    public T[] Next(Random random, int count) => Enumerable.Range(0, count)
                                                           .Select(i => Next(random))
                                                           .ToArray();

EDIT: I just saw a discussion in another answer: I was assuming random was generated somewhere else and had some variable seed. If you just need a random class with a static seed, I would inject it as it has been suggested.

\$\endgroup\$
9
  • \$\begingroup\$ The threshold is irrelevant, because it needs to be exactly 1.0 \$\endgroup\$ – Krythic Jul 20 '16 at 13:21
  • 1
    \$\begingroup\$ @Krythic You can't expect a double to be exactly a number. If this is your requirement then you should use decimal. Have a look at this SO answer: stackoverflow.com/questions/1398753/… and this: stackoverflow.com/questions/6598179/… You might be lucky that with your machine/environment it matches 1, but that's not a safe statement. \$\endgroup\$ – Stefano d'Antonio Jul 20 '16 at 16:55
  • \$\begingroup\$ I just looked again at the code, IsValid it's likely never to return true as you are doing arithmetic operations with an unexpected precision. \$\endgroup\$ – Stefano d'Antonio Jul 20 '16 at 16:59
  • \$\begingroup\$ Storing any value less than 0.01 is unintended behavior. So this "problem" is non existent as long as the class is being used correctly. \$\endgroup\$ – Krythic Jul 20 '16 at 19:29
  • \$\begingroup\$ Good point on floating point comparison. However, I believe your tolerant of 0.1 is waaaay too high for a percentage value, as it would consider 90% as valid which shouldn't be. \$\endgroup\$ – Xiaoy312 Jul 20 '16 at 19:56
0
\$\begingroup\$

Additional few remarks
1. Use Decimal instead of double in this case. Why is explained here
2. There is not validation in Add method that probability summary is greater than 1.
3.You forced the user of your class to generate Random class . Do it yourself ! Make the life of person who will use your code more simple !

public T Next()
    {
        var random = new Random();
        double probabilitySum = 0;
        for (int i = 0; i < this._items.Count; i++)
        {
            probabilitySum += this._items.Values.ElementAt(i);
        }
        double value = random.NextDouble() * probabilitySum;
        for (int i = 0; i < this._items.Count; i++)
        {
            value -= this._items.Values.ElementAt(i);
            if (value <= 0)
            {
                return this._items.Keys.ElementAt(i);
            }
        }
        return this._items.Keys.ElementAt(this._items.Count - 1);
    }
\$\endgroup\$
10
  • 1
    \$\begingroup\$ The only reason I downvoted your answer was because of your suggestion to hardcode a Random. This ideology has so many flaws that I cannot even list them here. \$\endgroup\$ – Krythic Jul 20 '16 at 10:59
  • \$\begingroup\$ @krythic That's rather cryptic! What about passing the Random to the constructor? \$\endgroup\$ – Ben Aaronson Jul 20 '16 at 11:46
  • \$\begingroup\$ I agree that random should be a part of Roulette's internal state and should not be a part of its API. As @Krythic said, it definitely should not be recreated every time Next is called. However, initializing single Random instance in Roulette constructor (or injecting it), and then reusing this instance is a solid advice, IMHO. \$\endgroup\$ – Nikita B Jul 20 '16 at 11:53
  • 1
    \$\begingroup\$ @Krythic Could you explain please ? Because i don't understand the idea. My point was that Roulette class has to generate random numbers itself inside Next method. It's strange that this is client responsibility. \$\endgroup\$ – Disappointed Jul 20 '16 at 12:13
  • \$\begingroup\$ @NikitaB Injecting it would be an ok design choice. \$\endgroup\$ – Krythic Jul 20 '16 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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