5

这是一个面试饼干的问题-

假设您以恒定的速率从仪器接收样本，并且您拥有恒定的存储空间，那么您将如何设计一种存储算法，让我无论何时查看数据都能获得具有代表性的数据读数？换句话说，代表系统迄今为止的行为。

我对此一无所知。所以，我正在寻找想法。

4

2 回答 2

27

假设您有存储k元素的内存。将内存中的第一个k元素存储在数组中。现在，当您收到第 n 个元素（其中n > k）时，生成一个r介于1和之间的随机数n。如果r > k丢弃第nth 个元素。否则将数组中的第rth元素替换为第nth元素。

这种方法将确保在任何阶段您的数组都将包含k从迄今为止收到的输入元素中统一随机选择的元素。

证明我们可以通过归纳证明k，任何阶段的代表元素都是均匀随机分布的。假设在接收到n-1元素后，任何元素都以概率 出现在数组中k/(n-1)。

接收到第 n 个元素后，该元素被插入数组的概率 = k/n.

对于任何其他元素，它在当前迭代中被表示的概率=它在上一次迭代中被表示的概率*它在当前迭代中未被替换的概率

= (k/(n-1)) * (n-1)/n = k/n.
于 2012-10-04T18:29:34.470 回答
2

首先，信用属于它的地方。我将详细说明而不是替换 krjampani 的方法：非常好和清晰。

有一个 - 但不是那么次要的 - 点需要调查，从那里我们将找到一个相关的，有点隐藏的问题点。

首先让我们注意，我们可以重新制定结果，从另一个角度看待它，如果你愿意的话，对于任何给定的时间段，从零到那个时间的时间间隔的点（数据）是（假设：假设是）均匀分布在区间 [1-n] 上，由此得出（所述结果）它们在固定区间 [1-k] 中的相对计数应该是 k/n，可能是具有代表性的最佳方式.

我们应该意识到，所有这些都是“统计的”：我们生成随机点来控制存储中较旧的数据被较新的数据替换。因此，所述结果不是精确结果，而是（统计上的）“预期值”。

然而，统计上的“期望值”当然很少是我们实际得到的：它只是概念上无数次再次尝试相同事物的平均值。来自某个“时间段”的数据在区间 [1-n] 上的实际分布以及它们在 [1-k] 中的相对计数的相关派生值是否可能接近（完美）在这种情况下，期望值取决于我们生成随机数（1 到 n 之间）的方式。如果这真的是随机的，我们将进行蒙特卡洛类型的抽样，从而产生高斯类型的结果分布，即如果我们一遍又一遍地做同样的事情，那么实际的点分布，围绕均匀分布我们的目标是。作为推论，直到我们有非常多的点，

稍加思考就会很明显，在每次添加之后，没有办法总是拥有。完美的均匀分布，无论我们如何决定用新点替换旧点。因此，我们的目标必须是尽可能地增加预期偏差。

重新表述的问题是：给定一个间隔，您需要在该间隔上放置更多无限制的点，以便它们的分布始终“尽可能接近”均匀。这样做的方法是，对每个点相对于前一个点采用固定的“步长”，其中步长相对于间隔长度 - 并且最好是两个大的素数 - 间隔长度。小数字示例：间隔为 11（在某些单位中：“真实”值很可能是实数，而不是整数），步长取 5；这些步骤是 (k*5)mod11: 0, 5, 10, 4, 9, 3, 8, .. 在我们的例子中，我们有额外的复杂性，即间隔的长度正在变化。例如，我们可能需要调整点生成（I' m不确定）通过安排将任何新点放置在原始参数（大小，步长）固定的位置，然后将其位置按实际间隔长度按比例放大：间隔再次11，每次增加1 , 步长 = 5; 点数：0、5*(12/11)、10*(13/11) 等。在我们的例子中，需要整数“槽”来替换（或不替换）存储值，我们将不得不四舍五入到最接近的整数（并且该四舍五入对统计数据的影响可能会导致对点生成器的进一步调整） . 我这里没什么了，还有一些事情要解决。需要整数“槽”来替换（或不替换）存储值，我们将不得不四舍五入到最接近的整数（并且该四舍五入对统计数据的影响可能会导致对点生成器的进一步调整）。我这里没什么了，还有一些事情要解决。需要整数“槽”来替换（或不替换）存储值，我们将不得不四舍五入到最接近的整数（并且该四舍五入对统计数据的影响可能会导致对点生成器的进一步调整）。我这里没什么了，还有一些事情要解决。

我来到最后一个隐藏的问题：在上述所有内容中，我们默认假设均匀采样 - 在一个区间内平均分配点 - 是获得代表性结果的最佳方式。大概我们可以将“代表性结果”解释为 - 比如说，我们正在查看特定的测量值 - 在特定时间段内其值的公平平均值。想象要测量的值随着时间的推移表现为某个函数，我们实际上是在查看该函数在时间间隔内的积分（除以间隔长度）。现在，除非该函数随时间的变化是完全疯狂的，上下跳跃并做各种花哨的事情——在这种情况下，所有的赌注都被取消了，你也可以做任何随机的事情——有（理论上和实践上）确定的方法来说明你应该如何采样一个（“正常行为”）函数在一个区间内获得其积分的“最佳”近似值。随机（蒙特卡洛）确实很糟糕（与样本点数 N 收敛为 1/sqrt(N)）；均匀采样要好得多（1/N）-在某些特殊情况下非常理想-但两者通常都因在特定多项式的零点采样而相形见绌，其中-除非有病案-您通常将精度提高 0.5 到几个 SIGNIFICANT每增加一个点的数字。

以上述观点，我们面临的原始问题如下：我们如何系统地在一个稳定增加的区间上生成点，使得点在区间上的分布在任何时候都尽可能接近于那些特定的零（取决于您对希望采样的函数的了解，但在没有任何特定信息的情况下：Legendre）在该区间内的多项式（归一化为 [-1:1]）。

那么，我的（理论）方法是使用“恒定步长相对素数间隔”方法，其中 - 除了对间隔增加的事实进行调整外，见上文 - 长度的测量沿着区间，为了“计算”步长，由（Legendre）多项式的零点的分布（函数）加权。

于 2012-10-04T23:10:12.217 回答