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

More efficient sample() method for ZipfDistribution

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.0, 3.6
    • Labels:
      None
    • Flags:
      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. patch_v3
          20 kB
          Otmar Ertl
        4. Zipf Rejection Inversion Sampling Notes.pdf
          378 kB
          Otmar Ertl

          Activity

            People

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

              Dates

              • Created:
                Updated:
                Resolved: