找到最后一个项目，但没有储存n个项目的流中的N为

假设有一个数据流到达D（0），D（1），D（2），......当D（i ）来了，我想知道D（i - N）。最简单的方法是存储最近的N个项目，并在新数据到来时不断更新它们。但问题是N可能很大，因此没有足够的内存来存储它们。无论如何，通过存储比N更少的物品来实现这一点？一个常数M的空间是优选的吗？提前致谢。找到最后一个项目，但没有储存n个项目的流中的N为

来源

2011-05-11 sinoTrinity

'N'完全是随机的？ – Tomalak 2011-05-11 21:24:50

N是固定给定的应用程序。但与可用内存相比，它相对较大。具体来说，我需要N约1000. – sinoTrinity 2011-05-11 21:54:19

据我所知，除非您可以利用的数据中存在一些规律性。如果数据是完全随机的（从而没有元素可以从其他元素推断出来），那么选择不保存元素将使得不可能在迭代k + N中再现该元素。

相反，考虑：

可以减少ñ？
您可以将信息存储在磁盘上，或者（如果您处于嵌入式环境中）以较慢，更便宜的内存形式存储信息？
数据中是否存在某种模式？如果有例如一个重复的模式，你可以利用它，或者如果数字之间存在某种数学关系，也许某种公式可以帮助重建其他数字。即使没有可察觉的模式，也许你可以使用一些压缩算法来减少数据大小？
数据是否存在一些限制，例如：每个数字在0到255之间？如果是这样，你可以减少存储需求。

（这样做有什么应用，顺便？）

来源

2011-05-11 21:34:34

我用[P2算法]估计传感器网络中e2e延迟的分位数（http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.74。 2672＆代表= REP1＆类型= PDF）。由于我只关心最近N个项目的e2e延迟，因此我将移动一个大小为N的窗口，因为e2e延迟采样会继续到来。当样本D（i）出现时，我把它放在窗口中并驱逐D（i-N），两者都是逻辑上的，因为我无法保存整个样本窗口。 – sinoTrinity 2011-05-11 21:48:05

@sinoTrinity：嗯 - 我不擅长统计，但是这篇文章的重点并不在于它们描述的算法，只需要存储一些值，而不是全部_N_？（您只需存储少量值的价格是您只能得到分位数的近似值 - 我的说法是您需要存储所有值，假设您想要一个确切的结果，这取决于所有_N_值。） – 2011-05-11 22:38:21

是的，这都是估计。 P2估计到目前为止所有样本的分位数。它包含了所有的历史。但是我想估计最近N个样本的分位数，只是因为很久以前发生的事情可能根本就没有意义。 – sinoTrinity 2011-05-11 22:50:03

找到最后一个项目，但没有储存n个项目的流中的N为

回答

相关问题