问题：如何选择使每个插值段中任何点的最大误差保持在指定范围内的插值点？
目标是根据 Zipf 定律使用逆变换采样来塑造随机分布。我在这里找到了 Zipf 归一化因子的一个很好的近似值：
https://arxiv.org/abs/1511.01480（Maurizio Naldi 的“截断 Zeta 分布和 Zipf 定律的近似”）
我现在正在做的是创建 CDF 值与等级的样条曲线，并尝试设置一个错误界限，这样对于没有等级的插值值偏离其值的一定百分比以上（相对误差）。如果我有太多样条点，那会浪费内存。如果我的分数太少，那会增加错误。我试图找到样条点的最佳位置以平衡这两者。
我目前的方法（失败）是遍历所有等级并查看连续等级之间 PDF 值的差异。这种差异是一阶导数的代理。我跟踪差异的 MIN 和 MAX 值，当它们与 CDF 的比例差异太大时，我假设曲线弯曲太多，我添加一个新的插值点并开始跟踪所有差异。该算法产生的插值点太少，因为错误的累积速度比我预期的要快。
我有另一个想法：保持两个指针，一个在增长段的末尾，一个在前进一半的中点。当中点的误差变得太大时，添加一个新的插值点。但是，我不确定最严重的错误是否一定在范围的中间。
我可以存储所有等级的 CDF 值（使用大量内存 - 我当前的应用程序的最大等级为 50 万）。然后我可以详尽地测试建议段的每个内插值，并在错误变得太大时停止。我可以过冲并进行二进制搜索以找到最佳段长度 - 更快，但仍然需要大量内存。我希望有一个内存开销适中的单通道或双通道在线算法。
顺便说一句，对于每个样条线段，我尝试了以下插值函数：
线性 - 结果不佳。
二次 - 更好，但仍然很差。
双曲线 - 在分段上的工作时间是二次曲线的两倍，但仍然不够好。（如果我找到更好的方法来选择插值点，这可能就足够了。）
注意：双曲线的效果比预期的要好，因为高斯分布像大多数其他分布一样为 CDF 生成 S 曲线，而 Zipf PDF 在开始时有峰值，因此它的 CDF 看起来像一条带有渐近线的双曲线。
更新：
我采纳了我的一个想法。我跟踪样条线段的中点，因为它随着第二个指针的增长而增长，当中点处的误差变得太大时，我结束该段并开始另一个。正如预期的那样，中点不是误差最大的地方，所以我将我的理想误差除以七，如果中点误差超过我开始一个新的段。
以上还不够。我发现由于最后一段保证在 CDF = 1 处结束，所以最后一段实际上到达了渐近线。我的双曲线曲线拟合公式不希望在秩达到无穷大之前达到渐近线，因此这会引入错误。因此，对于 CDF = 1 附近的最后几个段，我回退到使用抛物线拟合。
上述方法对 CDF 错误产生了良好的结果，但有时会导致往返计算的结果不佳。如果我要求给定排名的 CDF，然后在反向查找中使用该 CDF 来查找排名，结果排名并不总是与原始排名匹配。我仍在研究如何纠正此往返错误。