5
\$\begingroup\$

Random range with no repeat and efficient for small subset. But still survives if return most or all.

This comes up poker simulation as you typically only deal 1/3 the deck.

The idea is to use Random and HashSet to determine what has gone out. When the first or last goes out then trim the range to reduce the number of Random.Next that have already gone out.

Could remove from HashSet that go outside of range but see little or no value in that. It would reduce size but at a compute cost. I thought Remove was O(n) but just looked it up and it is O(1) so it might be a good practice.

Ran a time and with 1 million return all (where it is weak) it was 4.7 seconds. Just return 1/4 of the million then 0.2 seconds. Tested versus a full Fisher Yates shuffle and the break even point is about 1/4. On the full then shuffle is about 5x faster.

//test
HashSet<int> testRandomSmallSubsetHash = new HashSet<int>();
RandomSmallSubsetHash randomSmallSubsetHash = new RandomSmallSubsetHash();
int randomSmall;
while ((randomSmall = randomSmallSubsetHash.Next()) != -1)
{
    Debug.WriteLine(randomSmall);
    if (!testRandomSmallSubsetHash.Add(randomSmall))
        Debug.WriteLine("ERROR ");
}
Debug.WriteLine("count " + testRandomSmallSubsetHash.Count);
//end test

public class RandomSmallSubsetHash
{
    private Random rand = new Random();
    private int rangeCount;
    private int range;
    private int start;
    private HashSet<int> used = new HashSet<int>();
    public int CountLeft { get { return rangeCount - used.Count; } }
    public bool HasNext { get { return (CountLeft > 0); } }
    public int Next()
    {
        if (!HasNext)
            return -1;

        int next = rand.Next(start, range + start);  //in .NET end is not inclusive
        while (used.Contains(next))
        {
            next = rand.Next(start, range + start);                  
        }
        //Debug.WriteLine(next);
        if (next == start + range - 1)
        {
            //can trim down the top to eliminte bad guesses
            range--;
            while (used.Contains(start + range))
            {
                range--;
            }
        }
        else if (next == start)
        {
            //can trim down bottom to eliminate bad guesses
            range--;
            start++;
            while (used.Contains(start))
            {
                range--;
                start++;
            }
        }
        used.Add(next);
        return next;
    }
    public void Reset (int RangeCount = 100, int Start = 1)
    {
        if (RangeCount< 1)
            throw new IndexOutOfRangeException();
        rangeCount = RangeCount;
        range = RangeCount;
        start = Start;
        used.Clear();
    }
    public void Reset()
    {
        Reset(rangeCount, start);
    }
    public RandomSmallSubsetHash(int RangeCount = 100, int Start = 1)
    {
        Reset(RangeCount, Start);
    }
}
\$\endgroup\$
9
  • \$\begingroup\$ If you actually are going to use this for said poker simulation, there's probably not going to be 1,000,000 values needed. In that case I would have some doubts as to whether a Yates shuffle would still be less efficient. Either way, have you considered a linear congruential generator? \$\endgroup\$
    – kyrill
    Apr 28, 2017 at 23:40
  • \$\begingroup\$ @kyrill Million is the same as 100 x 10,000 \$\endgroup\$
    – paparazzo
    Apr 29, 2017 at 0:52
  • \$\begingroup\$ Then I suppose the numbers 100 and 10,000 are somehow related to poker, right? I don't play poker, but I thought 1,000,000 deals would be quite a lot for a poker game. Or did I just misunderstand how you measured performance? \$\endgroup\$
    – kyrill
    Apr 29, 2017 at 11:04
  • 1
    \$\begingroup\$ No. I would just like to know what do you need this for. If you're not going to deal 1,000,000 cards, then why compare performance against Yates shuffle on 1,000,000 cards? Or am I not understanding the purpose of your code correctly? Do you really need 1,000,000 deals? Please correct me if I'm wrong, because judging from your reactions I feel like I have misunderstood something. \$\endgroup\$
    – kyrill
    Apr 29, 2017 at 11:50
  • 1
    \$\begingroup\$ @kyrill The reason for examining something does not limit its application. Generic design objectives are clearly stated in the first paragraph. \$\endgroup\$
    – paparazzo
    Apr 29, 2017 at 11:59

2 Answers 2

1
\$\begingroup\$

Before I start, let me say that this code looks pretty good. You seem to have tested your algorithm pretty well and I've never read about shuffling algorithms other than the Fisher-Yates, so I won't comment on it.


First, this code seems a little squished together. I would put newlines between my methods to make it a little clearer where one unit of responsibility starts and the previous one stops.

Second, please use your braces. And if you aren't going to use braces, then consistently don't use them:

if (!HasNext)
    return -1;

while (used.Contains(next))
{
    next = rand.Next(start, range + start);                  
}

Third, parameters are named with camelCase by convention in C#:

public void Reset (int RangeCount = 100, int Start = 1)

Fourth, please put spaces around your operators:

if (RangeCount< 1)

In the if/else if block in Next(), you do range-- at the top of each block. You should move this to just above the conditional if it is going to happen either way. However, I'm not quite sure if it is supposed to use the -- operator in each given that the comment for the first says you are trimming the top of the range and the comment for the other says you are trimming the bottom.


//in .NET end is not inclusive

This comment is not really needed, unless you are reminding yourself about it. Robert C. Martin states in Clean Code that every time you use a comment to explain your code, what the comment is really saying is that you failed to write your code so it explains what it does itself. After reading and writing many comments myself, I have to agree with him.


C# 6 would allow you to use the => expression for your one-line calculated properties:

public bool HasNext => CountLeft > 0;

Instead of:

public bool HasNext { get { return (CountLeft > 0); } }
\$\endgroup\$
1
  • \$\begingroup\$ Trim top or bottom the range still goes down. Good feedback. \$\endgroup\$
    – paparazzo
    May 13, 2017 at 0:45
1
\$\begingroup\$
private Random rand = new Random();

There are at least two problems with this:

Firstly, it's not usable in applications which require determinacy, which potentially includes unit testing of methods which use this class.

Secondly, the description mentions poker, and that's an application where linear congruential RNGs are insecure. IMO it's a major design flaw in the C# standard library that there's no common interface between System.Random and System.Security.Cryptography.RandomNumberGenerator, but it is at least possible to wrap a subclass of Random around RandomNumberGenerator. However, to use the wrapper again requires a way to inject the RNG into RandomSmallSubsetHash.

\$\endgroup\$

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.