java - Java中用于文本生成的Zipf定律-太慢

嘿，我正在开发一个文本生成器，它将生成数百万种不同的文本。
为了使每个文本的内容都逼真，我使用了齐普夫定律
运行正常，单词分配正确。

但是以下next()函数的执行速度非常慢，并且由于我要生成数百万的文章，因此必须对其进行更改。 (while循环是最慢的部分)

有人可以帮我弄这个吗？

我是这样实现的:

   public int next() {

    int rank;
    double frequency = 0;
    double dice;

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


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

    return rank;
}

编辑:我从:http://diveintodata.org/2009/09/13/zipf-distribution-generator-in-java/获取了代码

最佳答案

您复制的实现...存在一些问题。可能有人会说这显然是错误的，因为它使用的是随机值，并且在进行类似

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

rank的值为0，然后频率为Infinity，并弄乱了一些统计信息。

我试图纠正这些错误，但是让而不是分析了实现，并且让而不是将其与Zipf分布函数的定义进行了比较。因此，如果有人复制了我的代码，他可能会发现它仍然“...有一些问题”。

严格来说，next函数的实现不是“total correct”，因为它不一定要终止。没有什么可以阻止循环永远运行。根据参数，终止之前或多或少会花费一些时间。而且我认为这也是导致您的“性能”问题的主要原因之一:对于某些值，条件(dice < frequency)极不可能发生...。

无论如何，您可以实现的目标可以更一般地表述:您具有一定的概率分布。并且您需要一个“随机”函数，该函数根据此分布返回随机值。

一种简单而通用的方法是使用NavigableMap将(累积的)概率分布映射到目标值。给定java.util.Random实例提供的0.0到1.0之间的随机值，然后可以使用该映射表快速查找目标值。

对于特定情况，可能会有更有效的解决方案，但是再次:这是非常通用和简单的(并且仍然相当有效)。

我在这里为Zipf发行版实现了这一点。同样，我没有详细验证所有内容，并且存在一些+1 / -1奇数(在第一段中提到)，但是它应该显示出这样的想法:FastZipfGenerator填充了包含概率分布的图，并且在next()函数中，执行查找:

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;
    }

}

它打印随机样本结果(基本上是“直方图”)和一些计时结果。计时结果像

duration 6221.835052
duration 304.761282

表明它很有可能会更快(即使这不应被视为“基准” ...)