增强现实AR>> raku-Random-Choice>> 返回
项目作者： titsuki

项目描述 ：
A Raku alias method implementation
高级语言： Perl 6
项目地址: git://github.com/titsuki/raku-Random-Choice.git
创建时间： 2019-03-03T15:38:46Z
项目社区：https://github.com/titsuki/raku-Random-Choice
开源协议：Artistic License 2.0
下载


Build Status

NAME

Random::Choice - A Raku alias method implementation

SYNOPSIS

  1. use Random::Choice;
  3. say choice(:size(8), :p([0.1, 0.1, 0.1, 0.7])); # (3 1 0 3 3 3 3 3)
  4. say choice(:p([0.1, 0.1, 0.1, 0.7])); # 3

DESCRIPTION

Random::Choice is a Raku alias method implementation. Alias method is an efficient algorithm for sampling from a discrete probability distribution.

METHODS

choice

Defined as:

  1. multi sub choice(:@p! --> Int) is export
  2. multi sub choice(Int :$size!, :@p! --> List)

Returns a sample which is an Int value or a List. Where :@p is the probabilities associated with each index and :$size is the sample size.

FAQ

Is Random::Choice faster than Mix.roll?

The answer is YES when you roll a large biased dice or try to roll a dice many times; but NO when a biased dice is small or try to roll a dice few times.

Why? There are some possible reasons:

  • Random::Choice employs O(N) + O(1) algorithm whereas Mix.roll employs O(N) + O(N) algorithm (rakudo 2018.12).

  • Mix.roll is directly written in nqp. In general, nqp-powered code is faster than naive-Raku-powered code when they take small input.

  • Both algorithms take O(N) initialization cost; however, the actual cost of Mix.roll is slightly less than Random::Choice.

A benchmark result is here (For more info, see example/bench.p6):

A Benchmark Result

benchmark result

The Comparison Table on the Benchmark

  1. $ perl6 example/bench.p6 
  2. Benchmark: 
  3. Timing 1000 iterations of Mix(size=10, @p.elems=10) , Random::Choice(size=10, @p.elems=10)...
  4. Mix(size=10, @p.elems=10) : 0.076 wallclock secs (0.086 usr 0.003 sys 0.089 cpu) @ 13154.606/s (n=1000)
  5. Random::Choice(size=10, @p.elems=10): 0.122 wallclock secs (0.137 usr 0.008 sys 0.145 cpu) @ 8210.383/s (n=1000)
  6. O--------------------------------------O---------O----------------------------O--------------------------------------O
  7. |                                      | Rate    | Mix(size=10, @p.elems=10)  | Random::Choice(size=10, @p.elems=10) |
  8. O======================================O=========O============================O======================================O
  9. | Mix(size=10, @p.elems=10)            | 13155/s | --                         | -42%                                 |
  10. | Random::Choice(size=10, @p.elems=10) | 8210/s  | 73%                        | --                                   |
  11. O--------------------------------------O---------O----------------------------O--------------------------------------O
  12. Benchmark: 
  13. Timing 1000 iterations of Mix(size=1000, @p.elems=10) , Random::Choice(size=1000, @p.elems=10)...
  14. Mix(size=1000, @p.elems=10) : 1.879 wallclock secs (1.892 usr 0.000 sys 1.892 cpu) @ 532.130/s (n=1000)
  15. Random::Choice(size=1000, @p.elems=10): 0.097 wallclock secs (0.099 usr 0.002 sys 0.101 cpu) @ 10361.621/s (n=1000)
  16. O----------------------------------------O---------O------------------------------O----------------------------------------O
  17. |                                        | Rate    | Mix(size=1000, @p.elems=10)  | Random::Choice(size=1000, @p.elems=10) |
  18. O========================================O=========O==============================O========================================O
  19. | Mix(size=1000, @p.elems=10)            | 532/s   | --                           | 2141%                                  |
  20. | Random::Choice(size=1000, @p.elems=10) | 10362/s | -96%                         | --                                     |
  21. O----------------------------------------O---------O------------------------------O----------------------------------------O
  22. Benchmark: 
  23. Timing 1000 iterations of Mix(size=10, @p.elems=1000) , Random::Choice(size=10, @p.elems=1000)...
  24. Mix(size=10, @p.elems=1000) : 2.576 wallclock secs (2.560 usr 0.020 sys 2.580 cpu) @ 388.182/s (n=1000)
  25. Random::Choice(size=10, @p.elems=1000): 6.010 wallclock secs (6.015 usr 0.032 sys 6.047 cpu) @ 166.398/s (n=1000)
  26. O----------------------------------------O-------O------------------------------O----------------------------------------O
  27. |                                        | Rate  | Mix(size=10, @p.elems=1000)  | Random::Choice(size=10, @p.elems=1000) |
  28. O========================================O=======O==============================O========================================O
  29. | Mix(size=10, @p.elems=1000)            | 388/s | --                           | -57%                                   |
  30. | Random::Choice(size=10, @p.elems=1000) | 166/s | 134%                         | --                                     |
  31. O----------------------------------------O-------O------------------------------O----------------------------------------O
  32. Benchmark: 
  33. Timing 1000 iterations of Mix(size=100, @p.elems=100), Random::Choice(size=100, @p.elems=100)...
  34. Mix(size=100, @p.elems=100): 1.505 wallclock secs (1.511 usr 0.000 sys 1.511 cpu) @ 664.420/s (n=1000)
  35. Random::Choice(size=100, @p.elems=100): 0.619 wallclock secs (0.624 usr 0.000 sys 0.624 cpu) @ 1616.535/s (n=1000)
  36. O----------------------------------------O--------O-----------------------------O----------------------------------------O
  37. |                                        | Rate   | Mix(size=100, @p.elems=100) | Random::Choice(size=100, @p.elems=100) |
  38. O========================================O========O=============================O========================================O
  39. | Mix(size=100, @p.elems=100)            | 664/s  | --                          | 146%                                   |
  40. | Random::Choice(size=100, @p.elems=100) | 1617/s | -59%                        | --                                     |
  41. O----------------------------------------O--------O-----------------------------O----------------------------------------O
  42. Benchmark: 
  43. Timing 1000 iterations of Mix(size=1000, @p.elems=1000), Random::Choice(size=1000, @p.elems=1000)...
  44. Mix(size=1000, @p.elems=1000): 135.720 wallclock secs (135.946 usr 0.288 sys 136.234 cpu) @ 7.368/s (n=1000)
  45. Random::Choice(size=1000, @p.elems=1000): 6.022 wallclock secs (6.031 usr 0.028 sys 6.058 cpu) @ 166.058/s (n=1000)
  46. O------------------------------------------O--------O-------------------------------O------------------------------------------O
  47. |                                          | Rate   | Mix(size=1000, @p.elems=1000) | Random::Choice(size=1000, @p.elems=1000) |
  48. O==========================================O========O===============================O==========================================O
  49. | Mix(size=1000, @p.elems=1000)            | 7.37/s | --                            | 2158%                                    |
  50. | Random::Choice(size=1000, @p.elems=1000) | 166/s  | -96%                          | --                                       |
  51. O------------------------------------------O--------O-------------------------------O------------------------------------------O

The Environment on the Benchmark

  • CPU Ryzen7 5800X (8core)

  • OS Debian11 bullseye

AUTHOR

titsuki titsuki@cpan.org

COPYRIGHT AND LICENSE

Copyright 2019 titsuki

This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.

The algorithm is from:

  • Vose, Michael D. “A linear algorithm for generating random numbers with a given distribution.” IEEE Transactions on software engineering 17.9 (1991): 972-975.