[jira] [Commented] (MATH-1220) More efficient sample() method for ZipfDistribution

["Otmar Ertl (JIRA)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/MATH-1220?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=14513221#comment-14513221 ] 

Otmar Ertl commented on MATH-1220:
----------------------------------

The patch overrides the sample() method for ZipfDistribution by an implementation that uses rejection sampling. To demonstrate the speed of the new method the (ignored) unit test testPerformance() can be used. Using the default sample() method from AbstractIntegerDistribution instead, the test will not finish in reasonable time. The generation of a single random value consumes at most 2 uniformly distributed random numbers on average, dependent on the parameters of the Zipf distribution (see the output of testPerformance()).

> More efficient sample() method for ZipfDistribution
> ---------------------------------------------------
>
>                 Key: MATH-1220
>                 URL: https://issues.apache.org/jira/browse/MATH-1220
>             Project: Commons Math
>          Issue Type: Improvement
>            Reporter: Otmar Ertl
>         Attachments: patch_v1
>
>
> Currently, sampling from a ZipfDistribution is very inefficient. Random values are generated by inverting the CDF. However, the current implementation uses O(N) power function evaluations to calculate the CDF for some point. (Here N is the number of points of the Zipf distribution.) I propose to use rejection sampling instead, which allows the generation of a single random value in constant time.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)