java - 根据帕累托原则从列表中随机选择

Question

我有一个 List<T>并尝试根据Pareto Principle随机挑选元素，因此前 20% 的项目将被挑选 80% 次，其余 80% 的项目将被挑选 20% 次。到目前为止，我有一个简单的实现:

static <T> T pickPareto(List<T> list) {
    int n = list.size();
    int first = n * 0.2;
    return rnd.nextFloat() < 0.8            
           ? list.get(rnd.nextInt(first))                // pick one of first 20%
           : list.get(first + rnd.nextInt(n - first));   // pick one of remaining 80%
}

它运行良好，但根据阶梯函数的分布来挑选项目。

有谁知道如何根据 平滑函数 的分布选择项目(也许不完全是帕累托，但持有 20/80 属性)？

Answer 1

经过一段时间的研究，我发现这个问题可以简化为寻找函数的问题，它适用于产生均匀随机分布的函数(例如.nextFloat()) , 结果期望分布。

这样的函数f(x)必须满足以下所有条件:

1. f(0) = 0

2. f(x) → 1 对于 x → 1

3. 在区间 [0, 1)

上是非递减的，最好是严格递增的

4. 在区间 [0, 1)

上保持平滑

5. f(0.8) = 0.2 -- 80/20 帕累托原则的条件，或者，通常，f(p) = 1 - p

终于，我成功实现了这样的功能。它可以是:

f(x) = (x^a + 1 – (1 – x)^1/a)/2,
a = log_p(1 – p)

这里的参数 p ∈ (0, 1) 的意思与它在条件 5 中的含义完全相同:它是一个调整参数，显示结果分布与均匀分布有何不同。例如，如果 p = 0.8，则 f(0.8) = 0.2。如果 p = 0.5，则 a = 1 所以函数折叠为 f(x) = x。

p = 0.8 的图表:

因此从列表中选择的方法如下所示:

public static <T> T pickRandomly(List<T> list, float p) {
    if (p <= 0 || p >= 1.0)
        throw new IllegalArgumentException();
    double a = Math.log(1.0 - p) / Math.log(p);
    double x = rnd.nextDouble();
    double y = (Math.pow(x, a) + 1.0 - Math.pow(1.0 - x, 1.0 / a)) / 2.0;
    return list.get((int) (list.size() * y));
}

---

例如，从 10 个整数列表中选取 1000 次，p = 0.8:

0: 646
1: 153  // 0 or 1 occured 799 times
2: 60
3: 57
4: 32
5: 26
6: 18
7: 7
8: 1
9: 0