ndsvw / fluent-random-picker

Fluent Random Picker is a nice, performant, fluent way to pick random values. Probabilities can be specified, values can be weighted.

Hi 👋, I'm Alex

A passionate software developer from 🇩🇪

• 👯 I’m looking to collaborate on Open Source projects written in C#

• 🤝 I’m looking for help with Published Date (JS) and Fluent Random Picker (C#)

• 👨‍💻 All of my projects are available at https://github.com/ndsvw

• 💬 Ask me about C#, asymptotic computational complexity or Docker

• 📫 How to reach me: @ndsvw:yatrix.org

• 🗣️ Fluent in German, English and C#

• 🤝 With special thanks to Alan Turing for making this possible

• ⚡ Fun fact C# = (C++)++

• ✨ Successful pull request in the .Net runtime repository: dotnet/runtime#96573

Connect with me:

Languages and Tools:

 

The profile template was generated with GitHub Profile README Generator

fluent-random-picker's Issues

Plan how to name the fluency interfaces consistently.

The interface names for fluency (e.g. ICanHaveValuePriorityAndNeed1MoreValue) are not good.
They should follow a pattern.

How can I give a small pool of reference types and pick a large number of items?

Version: 3.4.0

I am trying to use the following code to randomly generate some drops for a game:

private static IEnumerable<DropEntity> GenerateDrops(QuestDropInfo questDropInfo)
{
    int totalQuantity = (int)Math.Round(questDropInfo.Drops.Sum(x => x.Quantity));

    IPick<DropEntity> randomBuilder = Out.Of()
        .PrioritizedElements(questDropInfo.Drops)
        .WithWeightSelector(x => x.Weight);

    return randomBuilder.Pick(totalQuantity);
}

questDropInfo is a drop table with the following example JSON representation. The Weight property is the rounded value of Quantity * 100.

[
   {
      "_Id": 201009001,
      "_Quantity": 50
   },
   {
      "_Id": 40050045,
      "_Quantity": 0.1
   },
   {
      "_Id": 103001003,
      "_Quantity": 10
   }
]

I'm using totalQuantity as I want the items to be weighted in such a way that increasing the average quantity for one item does not make the other items less common.

When I run this code, FluentRandomPicker throws NotEnoughValuesToPickException presumably because I am trying to get 60 drops from a list with 3 values. I wanted to evenly distribute the drops based on the above weighting and generate many more items than I pass in.

The docs show an example where 5 values are picked from a picker with 4 values, but is this case different because I'm working with reference types which can't easily be cloned?

Weights using long

Hey,

Is it possible to extend weights to support long, lookg like at the moment they only support int?

❤️

Improve documentation in code

Descriptions for classes/methods/... are intended to give the user of the library additional/useful information.

Create implementation of `IRandomNumberGenerator` that is cryptographically secure

Currently FRP is using only Random() which is cryptographically unsecure. It is going to be flagged as major flaw by a lot of static code analyzers (i.e veracode). Adding new interface to handle random number generation in more secure way would be great.
Also there should be a way to exchange currently used random number generator.

Get rid of multiple enumerations of IEnumerables

There are multiple enumerations of IEnumerables in the code.

Count() is probably also calculated more often than necessary.

FluentRandomPicker should work with Collections/Lists internally. The IEnumerable that the user passes to FluentRandomPicker needs to be fully enumerated, anyway:

• To pick 1 or more non-prioritized element(s), the number of all elements needs to be known.
• To pick 1 or more prioritized element(s), all of them need to be enumerated, too.

Improve performance with parallelization

Some steps can probably be parallelized.

Try improving implementation of StochasticAcceptanceBasedWeightedLeftShuffle

Question: How to pick values with different priorities prioritized?

The current implementation works with stochastic acceptance and runs in linear time on average (see StochasticAcceptanceBasedWeightedLeftShuffle.cs)

Problem: The max probability value is calculated once in the beginning. If there is one high probability (e.g. weight 10.000) and all the other values are low (e.g. weight 1), the while(true) loop for the stochastic acceptance is iterated very often for no reason.

But: Updating the max potentially n times makes the algorithm run in O(n^2).

Sorting the values in the beginning to have "all max values" for every step makes it O(n*log(n)), what's maybe not the best solution.

Possibly, there is a different approach that runs in O(n) and does not require max-tracking. Or maybe there is a good approach to realize max-tracking without too much additional complexity.

Support Span, ReadonlySpan, Memory, ReadOnlyMemory, ...

Out.Of().Values(Span / ReadonlySpan / Memory / ReadOnlyMemory)

Consider extension methods

• How much effort is it?
• is it worth it?
• does the project name "Fluent-Random-Picker" still make sense?
  • Can extension methods for all this be built without fluent syntax?
  • Does the extension method syntax still look like the code that already exists?

Extension methods could exist for IEnumerable:

new List<int>{ 1, 2, 3}.PickOne(); // but where can you set the RNG?
new List<int>{ 1, 2, 3}.PickOne().WithSettings(rng).Evaluate(); // but then, the PickOne() logic is different to the PickOne() from the normal syntax

Weight doesn't influence random values correctly.

Running this code 100.000.000 times returns almost improbably often 'a' and 'b', but 'c' is almost improbably rare.

var value = Out.Of()
    .Value('a').WithWeight(7)
    .AndValue('b').WithWeight(2)
    .AndValue('c').WithWeight(1)
    .AndValue('d').WithWeight(0)
    .PickOne();

a: a lot > than 700.000.000
b: a lot > than 200.000.000
c: ~ 9.000.000 instead of 10.000.000

NotEnoughValuesToPickException when only one value is passed

Having another issue with my drops code 😔

If my enemy list (which is data driven) happens to only contain one element, it throws NotEnoughValuesToPickException when initializing the picker.

I am initializing an IPick<DropEntity> as follows

IPick<AtgenEnemy> randomBuilder = Out.Of()
    .PrioritizedElements(enemyList)
    .WithWeightSelector(x =>x.Weight);

and the stack trace is

FluentRandomPicker.Exceptions.NotEnoughValuesToPickException: Exception of type 'FluentRandomPicker.Exceptions.NotEnoughValuesToPickException' was thrown.
   at FluentRandomPicker.SelectorBasedRandomPicker`1.PrioritizedElements(IEnumerable`1 elements)
   at FluentRandomPicker.NonGenericOf.PrioritizedElements[T](IEnumerable`1 ts)
   at DragaliaAPI.Features.Dungeon.QuestEnemyService.GetEnemyPicker(AtgenEnemy[] enemyList)

It would be helpful for me if this was fixed, but I can see why it would be intended. I recognize that initializing a random picker with one element is a bit weird, but there's nothing technically stopping it from always returning the same value. Let me know your thoughts 🙂

PrioritizedElements.Pick(n) returns the same value n times

Version: 3.5.0

Reproduction example, slightly modified from the PrioritizedElements example in the docs:

using FluentRandomPicker;

var items = new Item[]
{
    new Item { Name = "Stone", Rarity = 1 }, // common
    new Item { Name = "Silver helmet", Rarity = 1 }, // uncommon
    new Item { Name = "Gold sword", Rarity = 1 }, // rare
};

IEnumerable<string> pickedItems = Out.Of()
    .PrioritizedElements(items)
    .WithValueSelector(x => x.Name)
    .AndWeightSelector(x => x.Rarity)
    .Pick(10);

foreach (string name in pickedItems)
{
    Console.WriteLine(name);
}
    
class Item {
    public int Rarity { get; set; }
    public string Name { get; set; }
}

When I run this the same name is always printed 10 times. I know this is theoretically possible but I am assuming that if it has happened 5+ times in a row for me then there is probably a bug 😉

This seems to also affect pickers using percentages instead of weightings.

Allow chaining Values(...).AndValues(...) ?

What's possible in this case:

• Out.Of().Values(...).AndValues(...).AndValues(...)...
• Out.Of().Values(...).WithWeigts(...).AndValues(...).WithWeigts(...)...

What's not possible in this case:

• Out.Of().Values(...).WithWeigts(...).AndValues(...).Pick(...);
• Out.Of().Values(...).AndValues(...).WithWeigts(...).Pick(...);

What about percentages?

Do all of them sum of to 100 or each of the .Values(...).WithPercentages(...) blocks?

Percentages less than 1

At the moment the lowest you can have is 1% but if I want a value to be returned 0.0001% of the time I cannot do it.

Priorities don't matter in rare cases

SortingBasedWeightedLeftShuffle can't handle a combination of large priorities and large random doubles:

Math.Pow(0.9999, 1/(double)int.MaxValue) // = 0.99999999999995348165526820594095624983310699462891
Math.Pow(0.9999, 1/(double)long.MaxValue) // = 1.00000000000000000000000000000000000000000000000000
Math.Pow(0.9999, 1/((double)long.MaxValue/10)) // = 1.00000000000000000000000000000000000000000000000000
Math.Pow(0.9999, 1/((double)long.MaxValue/1_000_000)) // = 1.00000000000000000000000000000000000000000000000000
Math.Pow(0.9999, 1/((double)long.MaxValue/10_000_000)); // = 0.99999999999999988897769753748434595763683319091797

So, maybe, there needs to be a fallback like Math.Pow(0.9999, 10_000_000/(double)n); for larger numbers.
Maybe, a fallback should already be there for ints, because for ~0,000001% of the weights (higher if we would allow long weights), it does not even make a difference, whether they are int.MaxValue or int.MaxValue / 10 (edge case):

Math.Pow(0.99999999, 1/(double)int.MaxValue) // = 1.00000000000000000000000000000000000000000000000000
Math.Pow(0.99999999, 1/((double)int.MaxValue / 10)) // = 1.00000000000000000000000000000000000000000000000000
Math.Pow(0.99999999, 1/((double)int.MaxValue / 100))  // = 0.9999999999999996

This gets worse when allowing to specify priorities as longs (see #14)

---

Furthermore: Random.NextDouble being exactly 0 could also be problematic as the result is always 0...

---

(from #14)

OverflowException in SecureRandomNumberGenerator.NextInt()

Failed NextInt_NoArgument_ReturnsEquallyDistributedValues [613 ms]
Error Message:
Test method FluentRandomPicker.Tests.Random.SecureRandomNumberGeneratorTests.NextInt_NoArgument_ReturnsEquallyDistributedValues threw exception:
System.OverflowException: Negating the minimum value of a twos complement number is invalid.
Stack Trace:
at FluentRandomPicker.Random.SecureRandomNumberGenerator.NextInt() in /home/alex/SynologyDrive/Projects/Fluent-Random-Picker/FluentRandomPicker/Random/SecureRandomNumberGenerator.cs:line 31
at FluentRandomPicker.Tests.Random.SecureRandomNumberGeneratorTests.NextInt_NoArgument_ReturnsEquallyDistributedValues() in /home/alex/SynologyDrive/Projects/Fluent-Random-Picker/FluentRandomPicker.Tests/Random/SecureRandomNumberGeneratorTests.cs:line 59
at System.RuntimeMethodHandle.InvokeMethod(Object target, Void** arguments, Signature sig, Boolean isConstructor)
at System.Reflection.MethodInvoker.Invoke(Object obj, IntPtr* args, BindingFlags invokeAttr)

Allow specifying values + priorities in one step

(Based on issue 10 - 3rd comment and issue 10 - 4th comment by phillip-haydon)

Idea: Something like this:

var options = Out.Of().WeightedValues(lootable.Select(x => new WeightedValue(x, x.Weight));

var drop = options.PickOne();

Advantage:

• No mistakes with order (order of values and percentages/weights) need to match when using Out.Of().Values(...).AndWeights(...) syntax
• Easy way if the values and percentages/weights are already combined in an object.

Use Reservoir sampling when 1 element (equal priorities) has to be picked

https://en.wikipedia.org/wiki/Reservoir_sampling#Optimal:_Algorithm_L

https://www.geeksforgeeks.org/select-a-random-number-from-stream-with-o1-space/?ref=lbp
https://www.geeksforgeeks.org/reservoir-sampling/