1

I'm trying to solve a rather simple problem where I have a list of items where the probability of finding an item also depends on the item itself (I imagine finding a shovel in a haystack is easier than finding a needle).

I want a method that returns one of these items at random taking in consideration the probability of finding each one of them.

So the items can be listed as such:

A - 100
B - 50
C - 10

Where the number represents how easy it is to find the item, where a higher value makes it easier to find.

Running the below method 10000 times resulted in finding the items in these quantities:

A - 6249  (100 / 160 = 0,625)
B - 3139  (50  / 160 = 0,3125)
C - 612   (10  / 160 = 0,0625)

Which pretty much proves that the below code works.

So now my question is, how can this be improved considering that the list itself can contain many thousands of items. Right now the method will run in the worst case over each item in the list at least once, ie O(n).

Can this be written into a LINQ/LAMBDA statement so the SQL server can deal with it and not lift all the items to C#?

public long GetRandomItem()
{
    var allItems = _db.AllItems
        .Where(x => x.CanBeFound == true)
        .OrderByDescending(x => x.Rarity)
        .Select(x => new
        {
            x.Id,       // id of item
            x.Rarity,   // rarity between 1 and 100
        }).ToList();

    int totalRarity = allItems.Sum(x => x.Rarity);
    var random = new Random(DateTime.Now.Millisecond);

    var randomNumber = random.NextDouble() * totalRarity;

    double totalSoFar = 0;
    long chosenId = -1;
    foreach (var i in allItems)
    {
        totalSoFar += i.Rarity;
        if (totalSoFar > randomNumber)
        {
            chosenId = i.Id;
            break; 
        }
    }

    return chosenId;
}

----- EDIT ------

Remade the LINQ to a version that only makes two queries to the database, and does not require a loop. Not completly sure if this is better yet as this will force the SQL to do more joins and selections of data.

public long GetRandomGamePiece()
{
    int totalRarity = _db.GamePieceTemplates.Sum(x => x.Rarity);
    var randomNumber = 1 + Math.Round(_Random.NextDouble() * (totalRarity - 1)); 

    var randomItem = _db.GamePieceTemplates
        .Where(x => x.CanBeFound == true)
        .OrderBy(x => x.Id)
        .Select((x) => new
        {
            x.Id,       // id of item
            x.Rarity,   // rarity between 1 and 100

            // +1 so that it dosent overlap previous level
            MinRarity = _db.GamePieceTemplates.Where(y => y.Id <= x.Id).Sum(y => y.Rarity) - x.Rarity + 1, 
            MaxRarity = _db.GamePieceTemplates.Where(y => y.Id <= x.Id).Sum(y => y.Rarity)
        })
        .Single(x => x.MinRarity <= randomNumber && x.MaxRarity >= randomNumber);

    long chosenId = -1;
    return  randomItem.Id;
}

This gets converted to this TSQL:

SELECT TOP (2) 
    [Project6].[Rarity] AS [Rarity], 
    [Project6].[Id] AS [Id], 
    [Project6].[C1] AS [C1], 
    [Project6].[C2] AS [C2]
    FROM ( SELECT 
        [Project5].[Id] AS [Id], 
        [Project5].[Rarity] AS [Rarity], 
        ([Project5].[C1] - [Project5].[Rarity]) + 1 AS [C1], 
        [Project5].[C2] AS [C2]
        FROM ( SELECT 
            [Project4].[Id] AS [Id], 
            [Project4].[Rarity] AS [Rarity], 
            [Project4].[C1] AS [C1], 
            (SELECT 
                SUM([Extent5].[Rarity]) AS [A1]
                FROM [dbo].[GamePieceTemplates] AS [Extent5]
                WHERE [Extent5].[Id] <= [Project4].[Id]) AS [C2]
            FROM ( SELECT 
                [Project3].[Id] AS [Id], 
                [Project3].[Rarity] AS [Rarity], 
                (SELECT 
                    SUM([Extent4].[Rarity]) AS [A1]
                    FROM [dbo].[GamePieceTemplates] AS [Extent4]
                    WHERE [Extent4].[Id] <= [Project3].[Id]) AS [C1]
                FROM ( SELECT 
                    [Project2].[Id] AS [Id], 
                    [Project2].[Rarity] AS [Rarity]
                    FROM ( SELECT 
                        [Project1].[Id] AS [Id], 
                        [Project1].[Rarity] AS [Rarity], 
                        [Project1].[C1] AS [C1], 
                        (SELECT 
                            SUM([Extent3].[Rarity]) AS [A1]
                            FROM [dbo].[GamePieceTemplates] AS [Extent3]
                            WHERE [Extent3].[Id] <= [Project1].[Id]) AS [C2]
                        FROM ( SELECT 
                            [Extent1].[Id] AS [Id], 
                            [Extent1].[Rarity] AS [Rarity], 
                            (SELECT 
                                SUM([Extent2].[Rarity]) AS [A1]
                                FROM [dbo].[GamePieceTemplates] AS [Extent2]
                                WHERE [Extent2].[Id] <= [Extent1].[Id]) AS [C1]
                            FROM [dbo].[GamePieceTemplates] AS [Extent1]
                            WHERE 1 = [Extent1].[CanBeFound]
                        )  AS [Project1]
                    )  AS [Project2]
                    WHERE ( CAST( ([Project2].[C1] - [Project2].[Rarity]) + 1 AS float) <= 130) AND ( CAST( [Project2].[C2] AS float) >= 130)
                )  AS [Project3]
            )  AS [Project4]
        )  AS [Project5]
    )  AS [Project6]
    ORDER BY [Project6].[Id] ASC
7
  • How often will items be added to this table? Can I assume it will be heavily read from but rarely written to?
    – Jason Boyd
    Aug 21, 2015 at 21:09
  • @JasonBoyd That is correct, the number of write operations will be almost negligible in comparison to read.
    – JensB
    Aug 23, 2015 at 9:51
  • 1
    I understand not wanting to change your model but the solution @31eee384 proposed is a good one. Since writes are rare, instead of replacing your probability column you could simply add a third accumulative probability column that could be updated with a DB trigger. You could even wrap his/her three steps up in a stored procedure. This would give you O(1) runtime without pulling everything back from the DB. Another option you could explore is keeping this particular table in memory and querying the in memory data rather than hitting the database each time.
    – Jason Boyd
    Aug 24, 2015 at 15:43
  • I made some changes that does what 31eee384 suggested, but without having fixed fields for it. Just testing it but as you guys have stated the best way will be to set up the fields in the database, and I will probably do that in the end.
    – JensB
    Aug 25, 2015 at 9:07
  • @JensB I'll be interested to see what the performance of that is. Who knows, maybe it'll be good enough for your application. Another thing about my answer: you could keep the probabilities in a separate table to logically separate it from the rest of your data, if that's why you don't want to add fields.
    – 31eee384
    Aug 27, 2015 at 14:19

3 Answers 3

1

If you can add a new column to your data, you could do this in SQL. This new column would include the sum of "possibilities" so far. Ordering by the column, you would see it like this for your sample values:

Id AccumP
A  100
B  150
C  160

If you maintain that property, you can find a weighted random item by:

  1. Finding the last item, ordered by AccumP.
  2. Select a random number between 0 and the last item's AccumP.
  3. Find the item with an AccumP value greater than the random AccumP but closest to it. This is your weighted random result.

If you index AccumP, this should be quick!

1
  • This is certainly a possibility, but I would prefer not to change the model.
    – JensB
    Aug 21, 2015 at 14:32
1

The way I'd do it would be to do a simple calculation based on the total number of options. No need for loops - the random value itself determines the result.

pseudocode would be:

int maxValueA = 100;
int maxValueB = 50;
int maxValueC = 10;
int total = maxValueA + maxValueB + maxValueC;

int x = random number between zero and total;

if (x <= maxValueA) return A;
else if (x <= maxValueA + maxValueB) return B;
else return C;

So, if you've got an ordered list of results, all you really need to do is choose the item in the resultset that corresponds with the random number.

Practical use of this is to populate an array based on % chance of ID occuring (again, pseudocode):

int[] IDsList = { A, A, A, A, B, B, C }; // ID's populated based on % chance being chosen

x = random int between 0 and IDsList.Count;

return IDsList[x];
2
  • 1
    With 1000 different items this would become quite annoying to code.
    – JensB
    Aug 21, 2015 at 14:31
  • @JensB like I said, only pseudocode - you'd need to use a function to sum the probabilities to get the bounds of the random, then pull back the item the corresponds to the random number. You may need to use a modulo operation as well. Aug 21, 2015 at 14:34
0

Another way - create a list with each number duplicated by the amount of times itself.

10 appears ten times, 50 appears 50 times - then get a random number between 1 and the amount of list items, this gives an index that you then use to grab the list item at that index.

void Main()
{
    var items = new int [] {100,50,10};
    var dict = new Dictionary<int,int>();
    var test = Enumerable.Range(1,10000);
    foreach (var t in test)
    {
        var result = SelectItem(items);
        if (!dict.ContainsKey(result))
        {
            dict.Add(result,0);
        }
        dict[result]++;
    }

    foreach (var d in dict.Keys)
    {
        Console.WriteLine("{0} - {1}",d,dict[d]);
    }


}

private static Random rand = new Random(DateTime.Now.Millisecond);
private int SelectItem(IEnumerable<int> numbers)
{
    var num = rand.Next(1,numbers.Sum());
    var list = numbers.OrderBy(n=>n)
        .SelectMany(n=> Enumerable.Range(1,n).Select(rr=>n)).ToList();
    //list.GroupBy(x=>x).Dump();
    //Console.WriteLine("Rand num = {0}, selected num = {1}",num,ret);
    return  list[num-1];;
}
1
  • I think this would this run in O(n) time as well, and also use more memory (as you are creating a bigger list)?
    – JensB
    Aug 23, 2015 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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