YCSB的zipfian分布生成原理出自这篇论文:Quickly Generating Billion-Record Synthetic Databases
但是里面似乎并没有给出推导。我最开始是尝试从定义出发推导出论文里的形式,但是失败了。后来我尝试从论文里的形式出发逆向推导出原始式子,才成功了。为了方便理解,这里从我逆向推导出的原始公式出发,正向推导出论文里的最终形式。
假如随机变量
那么
Riemann zeta function的原本定义是:
这样
分布函数
现在,我们从0到1的均匀分布中取一个数
但是
论文里预计算了前2项:
如果 
否则,取
接下来我们使用跟
我们定义一个反向的分布函数
其中,
我们假设
那么
接下来,我们只需要求出
令
定义
定义
由于
这就是论文里的公式。
¶ 评估
我们估计的
为了减小浮点误差造成的影响,这里将
#include <cstdio>
#include <cmath>
constexpr size_t n = 20000000;
constexpr double theta = 0.99;
double zeta[n + 1];
double G(size_t i) {
	return (zeta[n] - zeta[i - 1]) / (zeta[n] - zeta[2]);
}
double G_tilde(double i) {
	//return (1 - pow((i - 1) / n, 1 - theta)) / (1 - pow(2 / n, 1 - theta));
	return (pow(n, 1 - theta) - pow(i - 1, 1 - theta)) /
		(pow(n, 1 - theta) - pow(2, 1 - theta));
}
void space(size_t num) {
	while (num) {
		num -= 1;
		putchar(' ');
	}
}
int main() {
	zeta[0] = 0;
	for (size_t i = 1; i <= n; ++i) {
		zeta[i] = zeta[i - 1] + pow((double)i, -theta);
	}
	size_t v[] = {3, 4, 5, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
	printf("i\t\tG(i)\t\tG_tilde(i)\n");
	for (size_t i : v) {
		size_t ret = printf("%zu", i);
		space(16 - ret);
		ret = printf("%f", G(i));
		space(16 - ret);
		ret = printf("%f", G_tilde(i));
		putchar('\n');
	}
	return 0;
}i               G(i)            G_tilde(i)
3               1.000000        1.000000
4               0.980609        0.976770
5               0.966024        0.960231
10              0.922307        0.913352
100             0.782473        0.772490
1000            0.641863        0.633459
10000           0.498228        0.491684
100000          0.351273        0.346658
1000000         0.200898        0.198258
10000000        0.047020        0.046402可以看到误差其实并不大。
为了进一步验证估计的准确性,我们接下来直接验证
当
接下来我们对比
#include <cstdio>
#include <cmath>
constexpr size_t n = 20000000;
constexpr double theta = 0.99;
double zeta[n + 1];
double F(size_t i) {
	return zeta[i] / zeta[n];
}
double F_tilde(double i) {
	return 1 - (pow(n, 1 - theta) - pow(i, 1 - theta)) /
		(pow(n, 1 - theta) - pow(2, 1 - theta)) *
		(1 - zeta[2] / zeta[n]);
}
void space(size_t num) {
	while (num) {
		num -= 1;
		putchar(' ');
	}
}
int main() {
	zeta[0] = 0;
	for (size_t i = 1; i <= n; ++i) {
		zeta[i] = zeta[i - 1] + pow((double)i, -theta);
	}
	size_t v[] = {3, 4, 5, 10, 100, 1000, 10000, 100000, 1000000, 10000000};
	printf("i\t\tF(i)\t\tF_tilde(i)\n");
	for (size_t i : v) {
		size_t ret = printf("%zu", i);
		space(16 - ret);
		ret = printf("%f", F(i));
		space(16 - ret);
		ret = printf("%f", F_tilde(i));
		putchar('\n');
	}
	return 0;
}i               F(i)            F_tilde(i)
3               0.097466        0.100999
4               0.110890        0.116222
5               0.121653        0.128059
10              0.156545        0.164999
100             0.280381        0.289565
1000            0.409298        0.417032
10000           0.541446        0.547469
100000          0.676695        0.680943
1000000         0.815097        0.817527
10000000        0.956724        0.957292误差也很小。
¶ 使用
#include <iostream>
#include <cmath>
#include <random>
#include <cassert>
class ZipfianGenerator {
public:
	ZipfianGenerator(
		size_t n, double theta
	) : n_(n),
		alpha_(1 / (1 - theta)),
		zeta2_(1 + pow(2.0, -theta))
	{
		assert(n > 2);
		zetan_ = zeta2_;
		for (size_t i = 3; i <= n; ++i) {
			zetan_ += pow((double)i, -theta);
		}
		eta_ = (1 - pow(2.0 / n, 1 - theta)) / (1 - zeta2_ / zetan_);
	}
	template <typename E>
	size_t operator()(E &e) {
		std::uniform_real_distribution<> dis(0.0, 1.0);
		double u = dis(e);
		double uz = u * zetan_;
		if (uz < 1)
			return 1;
		if (uz < zeta2_)
			return 2;
		return 1 + (size_t)(n_ * pow(eta_ * u - eta_ + 1, alpha_));
	}
private:
	size_t n_;
	double alpha_;
	double zeta2_;
	double zetan_;
	double eta_;
};
int main() {
	std::random_device rd;
	std::mt19937 e(rd());
	size_t n = 20000000;
	ZipfianGenerator g(n, 0.99);
	for (size_t i = 0; i < n; ++i) {
		std::cout << g(e) << std::endl;
	}
	return 0;
}¶ 注意事项
YCSB里的zipfian似乎默认是scrambled zipfian,它的item count被指定为了1e10,导致它生成的分布跟zipfian的理论分布不一致。建议不要用YCSB生成zipfian,而是用它的公式自己写一个。