6
\$\begingroup\$

This is something I am always asked by managers and clients : "make it random". More often than not, this isn't what they want.

Comments like "I had the same element twice in a row !" and "I don't see lement X often enough !" are common, even if they are part of the "true random".

I came up with the following solution using generics. It's basically a Urn with a safeguard so the last item isn't picked after a refill. I'm looking for ways to improve it. Is it readable ? Is it efficient enough ?

using System;
using System.Collections;
using System.Collections.Generic;

namespace Utils
{
    /// <summary>
    /// Implements "iTunes shuffle" that is to say, it's a random where you can't get twice the same value unless you
    /// already got all the values.
    /// 
    /// To avoid having a chance to get twice the same value when refilling the pool, we store the last picked value in
    ///  `_last` and do not put it back when refilling the pool
    /// 
    /// author: ray.hubert@riseup.net
    /// </summary>
    public class Shuffler<T> : IEnumerable
    {
        private readonly List<T> _allItems = new List<T>(); // All items used in the shuffler
        private readonly List<T> _pool = new List<T>(); // Remaining items for current series
        private T _last; //Last object extracted from the pool
        private Random _random = new Random();

        private int PoolCount
        {
            get { return _pool.Count; }
        }

        public Shuffler()
        {
        }

        public Shuffler(ICollection<T> allItems)
        {
            if (allItems.Count == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            _allItems.AddRange(allItems);
            PopulatePool();
        }


        public T GetNext()
        {
            if (IsPoolEmpty())
            {
                PopulatePool();
            }
            return PopRandomElement();
        }

        private T PopRandomElement()
        {
            if (PoolCount == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            int randomIndex = _random.Next(PoolCount);
            T item = _pool[randomIndex];
            _pool.RemoveAt(randomIndex);
            if (IsPoolEmpty()) _last = item;
            return item;
        }

        private void PopulatePool()
        {
            _pool.Clear();
            _pool.AddRange(_allItems);
            if (PoolCount > 1) // If _allItems is size 1 we don't remove from the pool : it would be empty
            {
                RemoveLastFromPool();
            }
        }

        private void RemoveLastFromPool()
        {
            _pool.Remove(_last);
            _last = default(T);
        }

        public List<T> GetAllPossibleValues()
        {
            return new List<T>(_allItems);
        }

        private bool IsPoolEmpty()
        {
            return PoolCount == 0;
        }

        public IEnumerator GetEnumerator()
        {
            while (PoolCount > 0)
            {
                yield return PopRandomElement();
            }
        }

        public void Add(T element)
        {
            _allItems.Add(element);
            PopulatePool();
        }
    }
}

Sample usage #1 :

// Loops on all alements and stop
Shuffler<int> shuffler = new Shuffler<int> {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
foreach (int number in shuffler)
{
    Console.Write("Random element : " + number);
}

Sample usage #2 :

// Loops on all elements for ever
Shuffler<string> shuffler = new Shuffler<string> {"Alice", "Bob", "John", "Bill", "Scrooge"};
bool gameIsPlaying = true;
while (gameIsPlaying)
{
    Console.Write("Random element : " + shuffler.GetNext());
}

Points I'm wanting to improve :

  • The empty constructor seems necessary for the Add() function to work properly (see usage)

  • Throwing an exception in two code path is suboptimal, I'd rather have a single place to throw it

  • Readability, "code-cleanness"

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It took me a while to find, but you may find this interesting labs.spotify.com/2014/02/28/how-to-shuffle-songs \$\endgroup\$
    – RobH
    Jul 19 '17 at 14:20
  • \$\begingroup\$ Without going into detail, but it seems a lot of code for what could be a simple generic Fisher-Yates shuffle. Why reinvent the wheel? \$\endgroup\$
    – oerkelens
    Jul 19 '17 at 17:03
7
\$\begingroup\$
    public class Shuffler<T> : IEnumerable

Why not IEnumerable<T>??!


        private readonly List<T> _allItems = new List<T>(); // All items used in the shuffler

The types in this line raise two red flags in my mind.

  1. Code to the interface, not the implementation. The type of the field per se should be an interface: maybe IList<T>, maybe ICollection<T>, or maybe even something else.
  2. With respect to maybe even something else: should it be ISet<T>? The explanation given for the use case suggests strongly that elements should not be repeated, because if they are repeated it's going to be complicated to avoid playing the same track twice in a row.

        private readonly List<T> _pool = new List<T>(); // Remaining items for current series

Again, code to the interface. Here IList<T> is justified because the ability to select by index is important for performance.


        private T _last; //Last object extracted from the pool

If "last" here means "most recent" then the methods further down seem buggy.


        private int PoolCount
        {
            get { return _pool.Count; }
        }

Are you deliberately avoiding the arrow syntax?

        private int PoolCount => _pool.Count;

is going to become increasingly common.


        public Shuffler(ICollection<T> allItems)
        {
            if (allItems.Count == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            _allItems.AddRange(allItems);
            PopulatePool();
        }

I concur with VisualMelon's observations on this constructor: there's no reason to prohibit empty inputs, there's no need to populate the pool yet, and there's no reason to require ICollection<T> rather than IEnumerable<T>.


        public T GetNext()
        {
            if (IsPoolEmpty())
            {
                PopulatePool();
            }
            return PopRandomElement();
        }

vs

        public IEnumerator GetEnumerator()
        {
            while (PoolCount > 0)
            {
                yield return PopRandomElement();
            }
        }

Firstly, I find this API very confusing. It would make more sense to me if both methods ran forever, repopulating the pool if it runs dry.

Secondly, IsPoolEmpty() vs PoolCount > 0 is inconsistent. IMO factoring out IsPoolEmpty() is overengineering: I would inline it.


        private T PopRandomElement()
        {
            if (PoolCount == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
            int randomIndex = _random.Next(PoolCount);
            T item = _pool[randomIndex];
            _pool.RemoveAt(randomIndex);
            if (IsPoolEmpty()) _last = item;
            return item;
        }

You asked

Is it efficient enough ?

Enough depends on your requirements, but the answer to the question "Is it as efficient as it could be?" is "No". _pool.RemoveAt has to shuffle along every later element in the list. In the worst case the random number generator will return a long string of 0. The standard solution is a swap.

        private T PopRandomElement()
        {
            System.Diagnostics.Debug.Assert(PoolCount > 0);
            int randomIndex = _random.Next(PoolCount);
            _last = _pool[randomIndex];
            _pool[randomIndex] = _pool[PoolCount - 1];
            _pool.RemoveAt(PoolCount - 1);
            return _last;
        }

This now takes constant time rather than linear time in the size of the pool.


        private void PopulatePool()
        {
            _pool.Clear();
            _pool.AddRange(_allItems);
            if (PoolCount > 1) // If _allItems is size 1 we don't remove from the pool : it would be empty
            {
                RemoveLastFromPool();
            }
        }

        private void RemoveLastFromPool()
        {
            _pool.Remove(_last);
            _last = default(T);
        }

Again, a linear removal could be replaced by a swap and a constant time removal.

But I wonder whether this actually meets the spec. Rather than removing _last from the pool entirely, didn't you just want to guarantee that it won't be the first element picked after repopulating the pool?

In fact, I'd be inclined to take this further. Suppose we refactor so that PoolCount is backed by its own field rather than _pool.Count, and that we have an additional field (or field-backed property) DelayCount.

If we replace _pool.RemoveAt(PoolCount - 1); with PoolCount--; then when PoolCount gets to 0, the pool contains the entire play list in reverse order of when they were last played. Now

PoolCount = _pool.Count;
DelayCount = N;
for (int i = 0; i < DelayCount; i++)
{
    var tmp = _pool[i];
    _pool[i] = _pool[PoolCount - DelayCount + i];
    _pool[PoolCount - DelayCount + i] = tmp;
}

swaps the first N elements up to the end. Adjust the PopRandomElement method a bit more:

        private T PopRandomElement()
        {
            System.Diagnostics.Debug.Assert(PoolCount > 0);
            System.Diagnostics.Debug.Assert(PoolCount > DelayCount);

            int randomIndex = _random.Next(PoolCount - DelayCount);
            var tmp = _pool[randomIndex];
            _pool[randomIndex] = _pool[PoolCount - 1];
            _pool[PoolCount - 1] = tmp;

            PoolCount--;
            if (DelayCount > 0) DelayCount--;

            return tmp;
        }

The effect is to guarantee that no track will repeat within N of the previous time it occurred. You can then make N settable with a public property or derive it from _pool.Count according to some hard-coded policy (e.g. a fixed percentage).


        public List<T> GetAllPossibleValues()
        {
            return new List<T>(_allItems);
        }

Why List<T>? In fact, is this method even useful?


        public void Add(T element)
        {
            _allItems.Add(element);
            PopulatePool();
        }

I don't see why it's desirable to populate the pool here. In addition to VisualMelon's observations, by populating the pool before reaching the end you lose the guarantee not to play the same track twice.

\$\endgroup\$
5
  • \$\begingroup\$ Can't believe I missed that obvious misuse of Remove! Delay is a great idea with solid examples. I avoided commenting on the apparent intent of the public methods, but I agree with all of these regarding quirky/nonobvious behaviours; though, I can imagine a use-case for duplicate entries, and am readily frustrated by APIs which enforce uniqueness without some technical (i.e. performance) benefit. Again, the OP needs to make these decisions, and document them! \$\endgroup\$ Jul 19 '17 at 15:52
  • \$\begingroup\$ I am stunned by all the things that I missed. Not only you pointed out my coding mistakes, but went further to fix the algorithm itself. I am going to fix all of it ASAP. A few questions though : - the arrow syntax was deliberatly avoided (C#6.0 feature, and I can't have it yet) - is it ok to edit my original code ? - both answer are great, but yours build on the previous, on what criteria should I decide which one to accept ? \$\endgroup\$
    – monsieur_h
    Jul 19 '17 at 16:00
  • 2
    \$\begingroup\$ @monsieur_h, no, it's not ok to edit your original code. If you try it, your edit will be rolled back. What is ok is to produce a revised version of the code and post a new question, linking back to this one. I suggest that you wait a bit longer to see whether anyone else has comments on this version which you might want to incorporate. \$\endgroup\$ Jul 19 '17 at 16:03
  • \$\begingroup\$ @PeterTaylor thanks. The point of editing the original code is also to provide fixed or improved code for visitors stumbling on this question. I'll post a gist or something once the review is over. \$\endgroup\$
    – monsieur_h
    Jul 19 '17 at 16:05
  • 1
    \$\begingroup\$ As for accepting: it's not that big a deal. I think the general advice would be to accept the answer which you found most helpful, but if that's a tough one to call then it doesn't matter. \$\endgroup\$ Jul 19 '17 at 16:05
6
\$\begingroup\$

I'm not a style person... but here are some comments on implementation and the exposed API:

By Method

GetAllPossibleValues()

It's clear that you've thought about this method, as you clone the list before returning it. From a performance and not-scary API point of view (how does the user know this is cloning?) you could instead return an IReadOnlyList<T> or an IEnumerable<T>, both of which can just be a projection of the list, saving you copying the memory (e.g. use GetEnumerator or the lesser known List<T>.AsReadOnly (it returns a ReadOnlyCollection<T>, which implements IReadOnlyList<T>).

RemoveLastFromPool()

I don't think you should be clearing _last_: if someone calls Add twise, then the second time it will have forgotten the last, and you may end up with it again. Also consider that default(T) can be an intended value for structs, and that you implicitly lose (proper) support for null values (you may consider making this explicit).

Note that List<T>.Remove(T) is an O(n) operation: you might consider changing how you implement this to reduce the cost (since it is only called from PopulatePool, the complexity of that method is unchanged, but I thought it worth pointing out).

PopRandomElement()

Again, List<T>.Remove(T) is relatively expensive (O(N)). From a complexity point of view, it would be better to shuffle the pool when you populate it (still O(N)) and then you can pop elements from it in constant time (e.g. _pool.RemoveAt(_pool.Length - 1)).

I disagree with you about wanting to throw exceptions in few places. I'd prefer my code shout at me as soon as possible, not least so that the stack trace is obvious. The exception here is hidden away in a private method that is making assumptions about the state of the object. Much better to throw a method specific exception in the public methods. The PoolCount == 0 check might be better as a System.Diagnostics.Debug.Assert(), which shouts "the developer is worried about this" rather than "you're using this code incorrectly". An exception in GetNext saying that the list is empty would in my opinion be better.

Add(T)

Given the cost of calling PopulatePool, you may consider deferring doing so. For example, repeated Adds at the moment will be expensive, most of the effort going to waste immediately. It may be better to just clear the Pool when you make a change, and only populate it when you need to access it. In fact, your code is already set up for this: GetNext already checks for an empty pool, so there is no reason to populate it ahead of time! That of course excepting the behaviour of GetEnumerator (below).

GetEnumerator()

This method can't be called more than once, because it never calls PopulatePool: having the same guard term as GetNext() would probably be quite sufficient, and would complement the 'deferred Populate' suggestion above.

If you are happy to shuffle _allItems itself, you could record the 'top' of the pool, and just count it down through _allItems, shuffling and reseting the top when it hits zero. This would half the memory footprint, but may warrent considerable commentary to explain the (albeit few) components. Of course, if you want to preserve that list for whatever reason, then you can't do this.

Shuffler(ICollection<T> allItems)

Why does this throw on an empty list? Note that if you defer the call to PopulatePool (above) that this code will run fine when supplied with an empty list. It's also just a scary thing that should be documented and reduces the useful of the constructor considerably. Shuffler is a fundamentally mutable class, and use case that looks like:

Shuffler<T> shuffler = new Shuffler<T>(itemSource);
foreach (T next in shuffler)
{
}

as in your own examples requires the user to explicitly handle the empty case.

By removing the 'must not be empty' constraint, you can also trivially change the code to accept an IEnumerable instead of an ICollection (no need to call .Count()), which makes it more accessible.

Misc

  • Your current code looks like it should work OK with duplicate elements currently, but keep this in mind when writing tests and such, or if you make any changes.

  • You are currently creating the Random object when you construct the Shuffler. It is common for such types to have a constructor which accepts a Random object, so that a common seed can be used (e.g. for neurotically synced/consistent software (games/simulations)) and to avoid any issues associated with creating many Random objects in a short time frame.

  • It's always a good habit to document your APIs inline with those documenting-comments \\\, even if you are the only person who will be using this: it forces you to know what you code is meant to do (because you have to say it in words), and means you have no doubt when you come back to it what it actually does.

  • You should probably be implementing IEnumerable<T>.

  • Definitely consider defering PopulatePool (as above): it will make everything better, and provide opportunities for other optimisations (shuffle ahead-of-time, etc.). (Essentially, call PopulatePool when it is empty and you try to read from it (GetNext and GetEnumerator), and clear it whenever your modify it (leave it empty in the constructor))

\$\endgroup\$
2
  • \$\begingroup\$ Thank you for this good feedback. I implemented the change on this gist. I did not make the optimization to PopulatePool() yet, because I still have to think of a good way to shuffle the pool. \$\endgroup\$
    – monsieur_h
    Jul 19 '17 at 11:58
  • \$\begingroup\$ @monsieur_h the usual approach is called Fischer-Yates. It's terribly simple, and carried out in-place. \$\endgroup\$ Jul 19 '17 at 15:41
-1
\$\begingroup\$

Add(T element) calls PopulatePool();. That is kind of expensive. How about just add to both List?

You could have an index on _pool and not have to remove.

   int randomIndex = _random.Next(poolIndex);
   T item = _pool[randomIndex];
   _pool[randomIndex] = _pool[poolIndex - 1];
   poolIndex--;

This basically the fisher yates shuffle on the fly

if (IsPoolEmpty()) _last = item; doe not need if (IsPoolEmpty())
In fact you don't want it to cover for Add

This can be done with less moving parts
I may have trimmed too much

public class Shuffler<T> : IEnumerable
{
    private readonly List<T> _pool = new List<T>(); // Remaining items for current series
    private int _poolIndex = -1;
    private Random _random = new Random();

    public Shuffler()
    {
    }
    public Shuffler(ICollection<T> allItems)
    {
        if (allItems.Count == 0) throw new ArgumentException("ERROR: initialization list cannot be empty !");
        _pool.AddRange(allItems);
        _poolIndex = _pool.Count();
    }

    public T GetNext()
    {
        return PopRandomElement();
    }

    private T PopRandomElement()
    {
        int randomIndex = _random.Next(_poolIndex);
        T item = _pool[randomIndex];
        _pool[randomIndex] = _pool[_poolIndex - 1];
        _poolIndex--;
        if (_poolIndex == 0)
        {
            _poolIndex = _pool.Count();  //this is basically the shuffle
            if(item != null && _poolIndex > 1)
            {
                _pool.Remove(item);
                _pool.Add(item);
                _poolIndex--;  //takes it out of rotation
            }
        }
        return item;
    }

    public List<T> GetAllPossibleValues()
    {
        return new List<T>(_pool);
    }

    public IEnumerator GetEnumerator()
    {
        yield return PopRandomElement();
    }

    public void Add(T element)
    {
        _pool.Insert(_poolIndex - 1, element);
        _poolIndex++;
        //immediately goes into the rotation
    }
}
\$\endgroup\$
8
  • \$\begingroup\$ 1. There's an out by one error in your shuffling code. 2. _allItems = allItems would have two problems: firstly, it doesn't type; secondly, storing a reference to a mutable data structure passed to your constructor makes it hard to guarantee that you don't end up in an inconsistent state due to your caller mutating it. \$\endgroup\$ Jul 24 '17 at 15:20
  • \$\begingroup\$ @PeterTaylor Don't agree there is out by one error. Don't follow how a caller could mutate - oh it could be a reference type. \$\endgroup\$
    – paparazzo
    Jul 24 '17 at 15:23
  • 1
    \$\begingroup\$ T item = _pool[randomIndex - 1] should be T item = _pool[randomIndex] \$\endgroup\$ Jul 24 '17 at 15:28
  • \$\begingroup\$ The GetEnumerater in the presented code is not implemented. The empty public constructor allows the object to hold a negative _poolIndex, which will cause a crash when PopRandomElement() is called, or indeed, when Add(T) is called. It is not immediately apparent how this code improves on that in the OP beyond having fewer (more fragile) components. \$\endgroup\$ Jul 24 '17 at 17:10
  • 1
    \$\begingroup\$ I would also argue that you've assumed a lot about the intent of the Add method, and while your implementation is both interesting and efficient for the behaviour you've gone with, it is different to that presented in the OP, and since here we expect working code, different behaviour should be considered wrong. I think this new Add behaviour is worth presenting, but it should be discussed in greater detail, and ideally, a method for the 'correct' behaviour should be provided. \$\endgroup\$ Jul 24 '17 at 17:22

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.