Create stack with unique random numbers fast-CodePudding

I created a method where I generate a stack of random unique numbers. The code works but I need this to run a lot faster. Does anyone have a suggestion.

Lower is the lowest number for the random number, upper is the highest number for the random number and count is the amount of numbers I need.

I tried searching around for a better solution, but I couldn't make it work.

    public static Stack<int> RandomNumbersGenerator(int lower, int upper, int count)
    {
        Stack<int> stack = new Stack<int>();
        Random rnd = new Random();
        while (count > 0)
        {
            int h = rnd.Next(lower, (upper   1));
            if (!stack.Contains(h))
            {
                stack.Push(h);
                count--;
            }

        }
        return stack;
    }

The answer for anyone wondering:

    public static Stack<int> RandomNumbersGenerator(int lower, int upper, int count)
    {
        Stack<int> stack = new Stack<int>();
        HashSet<int> hset = new HashSet<int>();
        Random rnd = new Random();
        while (1 == 1)
        {
            hset.Add(rnd.Next(lower, (upper   1)));
            if (hset.Count == count)
            {
                stack = new Stack<int>(hset);
                return stack;
            }
        }
    }

CodePudding user response：

This is what my version would like like. Very similar to your final version but more compact and tests only one condition each time through the loop.

public static Stack<int> RandomNumberGenerator(int lower, int upper, int count)
{
    Random rnd = new();
    HashSet<int> set = new();

    while (set.Count < count)
        set.Add(rnd.Next(lower, upper   1));

    return new Stack<int>(set);
}

CodePudding user response：

Well, there are a couple reasons why something like this might be executing slowly. Firstly, Stack<T>.Contains(T) is a linear search. Which means every time you call that method, the entire stack is iterated from beginning to end (or until the matching element is found). If count is large, then the method might take a long time to execute simply because you're iterating the Stack so many times.

You might address this by building a HashSet<int> which should have much faster lookups... O(1) vs O(n).

public static Stack<int> RandomNumbersGenerator(int lower, int upper, int count)
{
    Random rng = new Random();

    // Initialize the HashSet with the count to avoid having to resize it while
    // building it.
    HashSet<int> items = new HashSet<int>(count);

    while (count > 0)
    {
        int next = rng.Next(lower, upper);
        // HashSet<T>.Add will return true if the item was added or false if it
        // was not because it already exists.
        if (items.Add(next))
        {
            count--;
        }
    }

    // Return a Stack<int> using the HashSet<int> to build it.
    return new Stack<int>(items);
}

This might run in to issues as well. Imagine a situation where lower is 0, upper is 12345678 and count is 12345677. In this case, you have to keep iterating until you randomly generate almost every number between 0 and 12345678. In this case, you might be better off generating an int[] with every number between lower and upper, shuffling it, then taking count items to build the resulting Stack<int>.

public static Stack<int> GenerateRandomStack(int lower, int upper, int count)
{
    var rng = new Random();
    var numbers = new int[upper - lower];
    for (int i = 0; i < numbers.Length; i  )
    {
        numbers[i] = lower   i;
    }
    int n = numbers.Length;
    while (n > 1) 
    {
        int k = rng.Next(n--);
        int temp = numbers[n];
        numbers[n] = numbers[k];
        numbers[k] = temp;
    }
    return new Stack<int>(numbers.Take(count));
}

There are probably cases I haven't thought of where neither of these approaches work well.

CodePudding user response：

Will there only be one match for h that you want to add? If so, simply continue to the next iteration of your while loop after finding your match. Something like this:

if (!stack.Contains(h))
                {
                    stack.Push(h);
                    count--;
                    continue;
                }

Depending on how your data is set up this could speed it up quite a bit.