这是个采访饼干的问题-
假设您正在以恒定的速率接收来自某个仪器的样本,并且您有恒定的存储空间,那么您将如何设计一个存储算法,让我能够获得有代表性的数据读出,而不管我什么时候看它--?换句话说,代表系统迄今为止的行为。
我对此一无所知。所以,我在寻找想法。
发布于 2012-10-04 23:10:12
第一,信用属于它的地方。我将详细阐述,而不是取代krjampani的方法:非常好和清晰。
有一点--但不是那么小--需要调查,然后我们将从这个问题中得出一个相关的,有点隐藏的观点。
让我们首先注意,我们可以重新表述结果,从另一个角度来看,如果你愿意的话,对于任何给定的时间周期,从零到那个时间间隔的点(数据)都是(假设:假设)均匀分布在区间1-n上,由此得出(声明的结果),它们在固定区间1-k中的相对计数应该是k/n,大概是最佳的表示方式。
我们应该认识到,所有这些都是“统计”的:我们生成随机点来控制存储中更新的数据对旧数据的替换。因此,所述结果不是确切的结果,而是(统计上的)“预期值”。
然而,一个统计的“期望值”,当然很少是我们实际得到的:它仅仅是一个概念上的无限次再次尝试相同事物的平均值。在这种情况下,区间1-n上的某个“时间周期”数据的实际分布及其相对计数的相关导出值是否接近(完全)期望值,取决于我们生成随机数(介于1和n之间)的方式。如果这是真正的随机,我们将进行蒙特卡罗型抽样,结果会产生高斯型分布,也就是说,如果我们一次又一次地做同样的事情,围绕我们的目标均匀分布。作为推论,除非我们有很多点,统计上的利差将保持相当大,这意味着,尽管我们的点分布的“期望值”是完美的(即我们所针对的),但在一次现实中,我们实际上有一些接近于这种分布的东西的相似之处并不那么大。
一个小小的思考就会清楚地表明,在每次添加之后,没有办法总是这样。一个完美的均匀分布,无论我们如何决定用更新的点代替旧的。因此,我们的目标必须是尽可能增加预期的偏离。
问题,重新制定,是:给定的间隔,你需要放置点,更无限制,在该间隔,以便他们的分布在任何时候都是“尽可能接近”是一致的。这样做的方法是,对相对于前一个点的每一个点采用一个固定的“步长”,其中步长相对于前一个点是素数,最好是两个大素数。用小数表示的例子:区间为11 (在某个单位:‘实’值很可能是reals,而不是整数),步长为5;步骤为(k*5)mod11: 0、5、10、4、9、3、8。在我们的例子中,我们还有一个额外的复杂问题,那就是间隔的长度在变化。我们可能需要调整点生成,例如(我不确定),将任何新的点放置在原来的参数(大小、步长)固定的地方,然后按照实际的间隔长度进行缩放:间隔再次11,每次增加1,和step=5;点数: 0,5*(12/11),10*(13/11)等等。在我们的情况下,需要整数“槽”来替换(或不)存储的值,我们将不得不舍入到最近的整数(统计数据的舍入的结果可能会导致对点生成器的进一步调整)。我这里没有更多的东西了,还有一些事情要解决。
我谈到了最后一个隐藏的问题:在上述所有问题中,我们都默认了一个统一的抽样--在一个区间内平均分配点--是获得具有代表性的结果的最好方法。据推测,我们可以把“代表性结果”解释为--比如说,我们在看一个特定的度量--价值--一个在特定时期内它的值的公平平均值。想象被测量的值随着时间的推移表现为一个特定的函数,我们实际上是在观察这个函数在时间间隔上的积分(除以区间长度)。现在,除非这个函数随时间的变化是完全疯狂的,跳上跳下,做各种花哨的事情--在这种情况下,所有的赌注都是断掉的,你也可以随意地做任何事情--有(理论上和实践上)关于如何在一个区间上对一个(“通常行为的”)函数进行采样,以得到它的积分的“最佳”近似的方法。随机(Monte)确实很糟糕(收敛为1/sqrt(N)与样本点N的数目);均匀采样(1/N)要好得多--在某些特殊情况下,这两者都比在特定多项式的零点处采样相形见绌--在这种情况下--如果不加病的话--通常每加一个点就能提高0.5到几个重要数字的精度。
以上述观点为视点,我们面临的原始问题如下:我们如何系统地在一个稳定增长的区间上生成点,这样,在任何时候,点在区间上的分布都尽可能接近于那些特定的零点的分布(取决于您对函数的了解程度)-样本,但在没有任何具体信息的情况下,该区间上的多项式(归一化为-1:1)。
那么,我的(理论)方法将是使用'constant-step-over-relatively-prime-interval‘方法,其中除了对区间增加的事实进行调整外,还可以看到沿区间长度的测量,用于“计算”步长,用(Legendre)多项式的零点的分布(函数)来加权。
https://stackoverflow.com/questions/12732982
复制相似问题