New submission from Raymond Hettinger <raymond.hettin...@gmail.com>:
For n unequal weights and k selections, sample selection with the inverse-cdf method is O(k logâ‚‚ n). Using the alias method, it improves to O(k). The proportionally constants also favor the alias method so that if the set up times were the same, the alias method would always win (even when n=2). However, the set up times are not the same. For the inverse-cdf method, set up is O(1) if cum_weights are given; otherwise, it is O(n) with a fast loop. The setup time for the alias method is also O(n) but is proportionally much slower. So, there would need to be a method selection heuristic based on the best trade-off between setup time and sample selection time. Both methods make k calls to random(). See: https://en.wikipedia.org/wiki/Alias_method Notes on the attached draft implementation: * Needs to add back the error checking code. * Need a better method selection heuristic. * The alias table K defaults to the original index so that there is always a valid selection even if there are small rounding errors. * The condition for the aliasing loop is designed to have an early-out when the remaining blocks all have equal weights. Also, the loop condition makes sure that the pops never fail even if there are small rounding errors when partitioning oversized bins or if the sum of weights isn't exactly 1.0. ---------- assignee: rhettinger components: Library (Lib) files: choices_proposal.py messages: 372441 nosy: mark.dickinson, rhettinger, tim.peters priority: normal severity: normal status: open title: Augment random.choices() with the alias method type: performance versions: Python 3.10 Added file: https://bugs.python.org/file49267/choices_proposal.py _______________________________________ Python tracker <rep...@bugs.python.org> <https://bugs.python.org/issue41131> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
