嘿,我正在研究一个文本生成器,它应该生成数百万种不同的文本。为了使每个文本的内容变得现实我使用了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
显示它很可能会更快(即使这不应被视为“基准”......)
你从https://diveintodata.org/2009/09/13/zipf-distribution-generator-in-java/获得的来源有一些错误。
这是快速修复。 (1)在构造函数ZipfGeneator(int,double)中,确保使用等号计算最大大小。
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));
}
}
(2)更换
rank = rnd.nextInt(size);
同
rank = rnd.nextInt(size)+1;
这是完整的源代码。
import java.util.Random;
//credit: https://diveintodata.org/2009/09/13/zipf-distribution-generator-in-java/ [Online; December 2017]
public class ZipfGenerator {
private Random rnd = new Random(System.currentTimeMillis());
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;
}
public static void main(String[] args) {
if(args.length != 2) {
System.out.println("usage: ./zipf size skew");
System.exit(-1);
}
ZipfGenerator zipf = new ZipfGenerator(Integer.valueOf(args[0]),
Double.valueOf(args[1]));
for(int i= 1;i <= 10; i++) {
System.out.println(i+" "+zipf.getProbability(i));
}
//use size = 10 and skew = 2 for testing below
int hist [] = new int [12];
for(int i=0;i<12;i++) {
hist[i] = 0;
}
System.out.println("Testing the probability distribution:");
int sum = 0;
for(int i= 1;i <= 1000000; i++) {
hist[zipf.next()]++;
}
for(int i=0;i<12;i++)
System.out.println(i+" "+hist[i]/1000000.0);
}
}
结果:
Probability distribution from the formula:
1 0.6452579827864142
2 0.16131449569660355
3 0.07169533142071269
4 0.04032862392415089
5 0.02581031931145657
6 0.017923832855178172
7 0.013168530260947229
8 0.010082155981037722
9 0.007966147935634743
10 0.006452579827864143
Testing the probability distribution from sampling:
0 0.0
1 0.645813
2 0.160766
3 0.071527
4 0.040346
5 0.026039
6 0.01801
7 0.013215
8 0.009953
9 0.007863
10 0.006468
11 0.0
注意,0和11具有预期的0概率。
你在询问速度,所以我提出了一个小优化。首先,摆脱重复的东西,看看它是什么:
public int next() {
while (true) {
int rank = rnd.nextInt(size);
if (rank == 0) return return rank;
double frequency = (1.0d / Math.pow(rank, this.skew)) / this.bottom;
double dice = rnd.nextDouble();
if (dice < frequency) return rank;
}
}
到目前为止它应该完全相同(除非我忽略了一些东西)。我向上移动了rank
的测试,因为如果它为零,下面的计算是无用的。现在有一条线我们可以加速一点
double frequency = Math.pow(rank, -this.skew) * inverseBottom;
实际上,由于四舍五入错误,这可能会略微改变结果,但我怀疑你应该关心。如果rank
是恒定的,你可以将pow
变成exp
以使其更快,但事实并非如此。对于一个小的size
,你可以预先计算一个ln(rank)
表并使用它像
double frequency = Math.exp(ln[rank] * -this.skew) * inverseBottom;
一个更好的算法肯定会给你更多的低级优化。