主页 / 问题 / 941686
Accepted
Roman
Asked:2020-02-07 02:29:05 +0000 UTC2020-02-07 02:29:05 +0000 UTC

这段代码是如何工作的？（代表性的样本）

  • 772

有一个神奇的代码：

static int samplerSize = 50;
static int[] sampler = new int[50];
static int i;

public static void samplerProces(int value)
{
    if (i < samplerSize)
    {
        sampler[i++]=value;
        return;
    }

    double p = samplerSize/(double)i++;
    if (rand.nextDouble() < p)
    {
        sampler[rand.nextInt(samplerSize)] = value;
    }
}

public static void test()
{
    int[] data = IntStream.range(0, 10000).toArray();
    IntStream.of(data).forEach(e -> {samplerProces(e);});
    System.out.println(IntStream.of(sampler).average());
}

不知何故，平均数接近 5000，这意味着样本有一次机会包含整个数组中的元素。

如何，我无法想象，因为从代码来看，越接近结尾，百分比越低......

java

1 个回答

  1. Best Answer

    这是经典的Reservoir Sampling 算法。在你的情况下，你有 50 个坦克。

    另请参阅
    https://ru.stackoverflow.com/a/760167/182825
    https://ru.stackoverflow.com/a/780834/182825

    考虑一下，例如，对于坦克的情况 1：我们遍历输入数据的序列（事先不知道其长度）并以概率“获取”数据元素1/i，其中i是元素编号（从 1 开始编号）。每当我们决定“采用”一个新元素时，我们都会忘记之前“采用”的那个。

    如您所见，随着我们越来越远，“获取”一个元素的概率越来越小。然而，作为结果，已经到达序列的末尾，我们将有一个等概率选择的元素。这真的没有什么令人惊讶的，即使起初它看起来不直观。

    • 在算法的第一步，我们以概率 1 “取”第一个元素。

    • 在算法的第二步，我们以 1/2 的概率“取”第二个元素。

      结果得到第一个元素的概率等于它在第一步“取”的概率乘以第二步“不取”第二个元素的概率：1 * 1/2 = 1/ 2.

      结果获得第二个元素的概率等于其“取”的概率：1/2。

      如您所见，概率是相等的。

    • 在算法的第三步，我们以 1/3 的概率“取”第三个元素。

      结果得到第一个元素的概率等于它在第一步“接受”的概率乘以第二个步骤“不接受”第二个元素的概率和“不接受”的概率第三步的第三个元素：1 * 1/2 * 2/3 = 1/3。

      结果得到第二个元素的概率等于它在第二步“取”的概率乘以第三步“不取”第三个元素的概率：1/2 * 2/3 = 1/3。

      结果得到第三个元素的概率等于它“取”的概率：1/3。

      如您所见，所有概率再次相等。

    • 在算法的第四步，我们以概率 1/4 取第四个元素。作为每个传递元素的结果获得的概率等于

      1: 1 * 1/2 * 2/3 * 3/4 = 1/4
2: 1/2 * 2/3 * 3/4 = 1/4
3: 1/3 * 3/4 = 1/4
4: 1/4

      所有的概率仍然相等。

    等等。在每i第 i 步之后，通过计算得到每个扫描元素的概率，你会发现它们都是相等1/i的。也就是说，在每个步骤中，支持从序列的已通过部分中等概率地选择一个元素。

    Reservoir Sampling 的通用算法只是这种方法对多重采样情况的推广。

    • 3

相关问题