Is there a more efficent way to randomise a set of LINQ results?

Question

I've produced a function to get back a random set of submissions depending on the amount passed to it, but I worry that even though it works now with a small amount of data when the large amount is passed through, it would become efficent and cause problems.

Is there a more efficent way of doing the following?

    public List<Submission> GetRandomWinners(int id)
    {
        List<Submission> submissions = new List<Submission>();
        int amount = (DbContext().Competitions
                     .Where(s => s.CompetitionId == id).FirstOrDefault()).NumberWinners;

        for (int i = 1 ; i <= amount; i++)
        {
            bool added = false;
            while (!added)
            {
                bool found = false;

                var randSubmissions = DbContext().Submissions
                    .Where(s => s.CompetitionId == id && s.CorrectAnswer).ToList();

                int count = randSubmissions.Count();
                int index = new Random().Next(count);

                foreach (var sub in submissions)
                {
                    if (sub == randSubmissions.Skip(index).FirstOrDefault())
                        found = true;
                }

                if (!found)
                {
                    submissions.Add(randSubmissions.Skip(index).FirstOrDefault());
                    added = true;
                }
            }
        }
        return submissions;
    }

As I say, I have this fully working and bringing back the wanted result. It is just that I'm not liking the foreach and while checks in there and my head has just turned to mush now trying to come up with the above solution.

Answer 1

(Please read all the way through, as there are different aspects of efficiency to consider.)

There are definitely simpler ways of doing this - and in particular, you really don't need to perform the query for correct answers repeatedly. Why are you fetching randSubmissions inside the loop? You should also look at ElementAt to avoid the Skip and FirstOrDefault - and bear in mind that as randSubmissions is a list, you can use normal list operations, like the Count property and the indexer!

The option which comes to mind first is to perform a partial shuffle. There are loads of examples on Stack Overflow of a modified Fisher-Yates shuffle. You can modify that code very easily to avoid shuffling the whole list - just shuffle it until you've got as many random elements as you need. In fact, these days I'd probably implement that shuffle slightly differently to you could just call:

return correctSubmissions.Shuffle(random).Take(amount).ToList();

For example:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    for (int i = 0; i < elements.Length; i++)
    {
        // Find an item we haven't returned yet
        int swapIndex = i + rng.Next(elements.Length - i);
        T tmp = elements[i];
        yield return elements[swapIndex];
        elements[swapIndex] = tmp;
        // Note that we don't need to copy the value into elements[i],
        // as we'll never use that value again.
    }
}

Given the above method, your GetRandomWinners method would look like this:

public List<Submission> GetRandomWinners(int competitionId, Random rng)
{
    List<Submission> submissions = new List<Submission>();
    int winnerCount = DbContext().Competitions
                                 .Single(s => s.CompetitionId == competitionId)
                                 .NumberWinners;

    var correctEntries = DbContext().Submissions
                                    .Where(s => s.CompetitionId == id && 
                                                s.CorrectAnswer)
                                    .ToList();

    return correctEntries.Shuffle(rng).Take(winnerCount).ToList();
}

I would advise against creating a new instance of Random in your method. I have an article on preferred ways of using Random which you may find useful.

One alternative you may want to consider is working out the count of the correct entries without fetching them all, then work out winning entries by computing a random selection of "row IDs" and then using ElementAt repeatedly (with a consistent order). Alternatively, instead of pulling the complete submissions, pull just their IDs. Shuffle the IDs to pick n random ones (which you put into a List<T>, then use something like:

return DbContext().Submissions
                  .Where(s => winningIds.Contains(s.Id))
                  .ToList();

I believe this will use an "IN" clause in the SQL, although there are limits as to how many entries can be retrieved like this.

That way even if you have 100,000 correct entries and 3 winners, you'll only fetch 100,000 IDs, but 3 complete records. Hope that makes sense!