-1
\$\begingroup\$

I'm looking to create a library for dealing with probability in C#. My current system takes an ordered array of probabilities as an input then generates a random double. It then accumulates each double in the array until the accumulated values are greater than the randomly selected one. Like this (Samples is the array of probabilities and Sample is the random value) :

int i;

for 
(
    (i, double accumulator) = (0, Samples[0].Probability); 
    i < Samples.Length && accumulator > Sample; 
    accumulator += Samples[++i].Probability

);

return i==Samples.Length? null:Samples[i];

Is this the fastest way of doing this? Also are there any good well-known probability libraries out there? Thanks guys :)

Improve this question
\$\endgroup\$
4
  • \$\begingroup\$ The question Can I foreach over an array of structs without copying the elements in C# 8? has an interesting answer showing some benchmark results. Using .AsSpan() can speed up the loop and even using foreach instead of for can do so (which was quite unexpected for me). But every case is different. So, the only way to speed up your code is to do benchmarks with different code variants. Use BenchmarkDotNet for your benchmarks. \$\endgroup\$
    – Olivier Jacot-Descombes
    Sep 20 at 14:46
  • \$\begingroup\$ Ok Thank you I was looking into spans but I read somewhere that there isn't much of a performance increase when iterating over arrays and I would have to resort to SIMD instructions for any noticeable speedups? \$\endgroup\$
    – Henners2002
    Sep 21 at 13:06
  • \$\begingroup\$ Since the order of the evaluation is important (you stop iterating when accumulator > Sample) I do not see a way to do this in parallel. Btw., the condition in the for should be i < Samples.Length && accumulator <= Sample because this is the condition for not stopping. \$\endgroup\$
    – Olivier Jacot-Descombes
    Sep 21 at 13:11
  • \$\begingroup\$ Ohhhhhh ye thank you. \$\endgroup\$
    – Henners2002
    Sep 21 at 13:15

1 Answer 1

Reset to default
1
\$\begingroup\$

Your current approach has a time complexity of O(⁡n)., where n is the length of the Samples array. This is because you're iterating through the array to find the appropriate sample. If you're dealing with a large number of samples, this could become a bottleneck.

Alternative Approaches

  1. Binary Search: If your probabilities are sorted, you could use binary search to find the appropriate sample, reducing the time complexity to O(log n).

  2. Alias Method: This method allows you to sample from a discrete probability distribution in O(1) time after O(n) preprocessing time.

Existing Libraries

  1. MathNet.Numerics: This is a well-known library for numerical computing in .NET, and it includes some probability distribution functions.

  2. Accord.NET: This is another comprehensive framework for scientific computing in .NET, which includes probability and statistical functions.

  3. Meta.Numerics: This library offers advanced mathematical and statistical functions, including some for probability. mark for performance.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ In terms of binary search would that work since I am dealing with a randomly selected doubles. For example if I had two very precise doubles and my binary search algorithm needed to place the randomly selected sample in between them surely a linear search would have better performance? Maybe wanting probability to such accuracy is quite rare so the algorithm would have low average running time. However I will definitely look into the alias method in more depth as this seems best for my needs thank you for your help and including the libraries :) \$\endgroup\$
    – Henners2002
    Sep 21 at 13:12

Your Answer

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

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