Uploaded image for project: 'Commons Math'
  1. Commons Math
  2. MATH-1220

More efficient sample() method for ZipfDistribution

    XMLWordPrintableJSON

Details

    • Improvement
    • Status: Closed
    • Major
    • Resolution: Fixed
    • None
    • 4.0, 3.6
    • None
    • None
    • Patch

    Description

      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.

      Attachments

        1. patch_v1
          16 kB
          Otmar Ertl
        2. patch_v2
          17 kB
          Otmar Ertl
        3. Zipf Rejection Inversion Sampling Notes.pdf
          378 kB
          Otmar Ertl
        4. patch_v3
          20 kB
          Otmar Ertl

        Activity

          People

            Otmar Ertl Otmar Ertl
            Otmar Ertl Otmar Ertl
            Votes:
            0 Vote for this issue
            Watchers:
            3 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved: