Zipf's law in Java for generating text - too slow

The implementation you copied ... has some problems. One could probably say that this is clearly wrong, because it uses random values, and when in a calculation like

rank = rnd.nextInt(size);
friquency = (1.0d / Math.pow(rank, this.skew)) / this.bottom;

      

        
        
        
      

    

Meaning rank

0

, then the frequency Infinity

will spoil some statistics.

I tried to fix the erros, but not analyzed the implementation and are not compared it with the definition of Zipf distribution function. So if someone copies my code, they might find out that they still "... have some problems".

The implementation of the function is next

, strictly speaking, not " total correct " in the sense that it does not necessarily end. There is nothing stopping the loop from running forever. Depending on the parameters, it may be more or less likely that it will take some time until it stops. And I think this is also one of the main reasons for the "performance" problem: for some values, the condition is (dice < frequency)

just unlikely to happen ....

Regardless, the goal you want to achieve can be formulated more generally: you have a definite probability distribution. And you want a "random" function that returns random values ​​based on that distribution.

One simple and general way to achieve this is to map the (cumulative) probability distribution to the target values ​​using NavigableMap

. This map can then be used to quickly find the target value given a random value between 0.0 and 1.0 that is supplied by the instance java.util.Random

.

In some cases, there may be better solutions, but again: this is very general and simple (and still quite effective).

I have implemented this here for Zipf distribution. Again, I haven't checked everything in detail, and there are some +1

/ -1

oddities (mentioned in the first paragraph), but it should show the idea: FastZipfGenerator

fills in the map containing the probability distribution and in a function next()

, just does a search:

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.NavigableMap;
import java.util.Random;
import java.util.TreeMap;

public class ZipfGeneratorTest
{
    public static void main(String[] args) {

        int size = 10;
        double skew = 2.0;

        ZipfGenerator z0 = new ZipfGenerator(size, skew);
        FastZipfGenerator z1 = new FastZipfGenerator(size, skew);

        long before = 0;
        long after = 0;

        int n = 5000000;

        before = System.nanoTime();
        Map<Integer, Integer> counts0 = computeCounts(z0, size, n);
        after = System.nanoTime();
        System.out.println(counts0+", duration "+(after-before)/1e6);

        before = System.nanoTime();
        Map<Integer, Integer> counts1 = computeCounts(z1, size, n);
        after = System.nanoTime();
        System.out.println(counts1+", duration "+(after-before)/1e6);
    }

    private static Map<Integer, Integer> computeCounts(
        ZipfGenerator z, int size, int n)
    {
        Map<Integer, Integer> counts = new LinkedHashMap<Integer, Integer>();
        for (int i=1; i<=size; i++)
        {
            counts.put(i, 0);
        }
        for (int i=1; i<=n; i++)
        {
            int k = z.next();
            counts.put(k, counts.get(k)+1);
        }
        return counts;
    }

    private static Map<Integer, Integer> computeCounts(
        FastZipfGenerator z, int size, int n)
    {
        Map<Integer, Integer> counts = new LinkedHashMap<Integer, Integer>();
        for (int i=1; i<=size; i++)
        {
            counts.put(i, 0);
        }
        for (int i=1; i<=n; i++)
        {
            int k = z.next();
            counts.put(k, counts.get(k)+1);
        }
        return counts;
    }

}

// Based on http://diveintodata.org/tag/zipf/
class ZipfGenerator {
    private Random rnd = new Random(0);
    private int size;
    private double skew;
    private double bottom = 0;

    public ZipfGenerator(int size, double skew) {
        this.size = size;
        this.skew = skew;

        for(int i=1;i <=size; i++) {
            this.bottom += (1/Math.pow(i, this.skew));
        }
    }

    // the next() method returns an random rank id.
    // The frequency of returned rank ids are follows Zipf distribution.
    public int next() {
        int rank;
        double friquency = 0;
        double dice;

        rank = rnd.nextInt(size)+1;
        friquency = (1.0d / Math.pow(rank, this.skew)) / this.bottom;
        dice = rnd.nextDouble();

        while(!(dice < friquency)) {
            rank = rnd.nextInt(size)+1;
            friquency = (1.0d / Math.pow(rank, this.skew)) / this.bottom;
            dice = rnd.nextDouble();
        }

        return rank;
    }


    // This method returns a probability that the given rank occurs.
    public double getProbability(int rank) {
        return (1.0d / Math.pow(rank, this.skew)) / this.bottom;
    }
}



class FastZipfGenerator
{
    private Random random = new Random(0);
    private NavigableMap<Double, Integer> map;

    FastZipfGenerator(int size, double skew)
    {
        map = computeMap(size, skew);
    }

    private static NavigableMap<Double, Integer> computeMap(
        int size, double skew)
    {
        NavigableMap<Double, Integer> map = 
            new TreeMap<Double, Integer>();

        double div = 0;
        for (int i = 1; i <= size; i++)
        {
            div += (1 / Math.pow(i, skew));
        }

        double sum = 0;
        for(int i=1; i<=size; i++)
        {
            double p = (1.0d / Math.pow(i, skew)) / div;
            sum += p;
            map.put(sum,  i-1);
        }
        return map;
    }

    public int next()
    {
        double value = random.nextDouble();
        return map.ceilingEntry(value).getValue()+1;
    }

}

      

        
        
        
      

    

It prints the result of a random sample (basically a "histogram") and some synchronization results. The sync results are something like

duration 6221.835052
duration 304.761282

      

        
        
        
      

    

showing that it will most likely be faster (although this should not be considered a "benchmark" ...)