设计的存储算法 [英] design a storage algorithm

问题描述

下面是采访饼干的问题 -

Here's a question for interview crackers-

• 既然你是从仪器以恒定的速率接收样品，你必须不断的存储空间，你会怎么设计的存储算法，让我得到的数据进行重新presentative读出，无论什么时候我看着它？该系统的迄今为止的行为的，换句话说，再presentative。

• Given that you are receiving samples from an instrument at a constant rate, and you have constant storage space, how would you design a storage algorithm that would allow me to get a representative readout of data, no matter when I looked at it? In other words, representative of the behavior of the system to date.

我找不到它的任何想法。所以，我在找的想法。谢谢你。

I couldn't get any idea of it. So, I am looking for ideas. Thank you.

推荐答案

假设你有内存来存储 K 元素。存储第一 K 在数组中的存储元件。现在，当您收到的第n个元素（其中 N'GT; k ），生成之间的随机数研究 1 和 N 。如果 R＆GT;氏/ code>放弃 N 日元素。否则，替换研究 日元素与 N 数组中的第元素。

Assume that you have the memory to store k elements. Store the first k elements in the memory in an array. Now when you receive the nth element (where n > k), generate a random number r between 1 and n. If r > k discard the n^th element. Otherwise replace the r^th element in the array with the n^th element.

此方法将确保在任何阶段阵列将包含 K 的均匀随机输入元素选定的元素收到为止。

This approach will ensure that at any stage your array would contain k elements that are uniformly randomly selected from the input elements received so far.

证明我们可以通过归纳表明， K 在任何阶段重新presentative元素分布均匀随机的方式。假定接收后 N-1 元素，任何元素为present的概率数组中的 K /（N-1）。

Proof We can show by induction that the k representative elements at any stage are distributed in a uniformly random way. Assume that after receiving n-1 elements, any element is present in the array with probability k/(n-1).

接收的第n个元件，该元件将被插入到该阵列= K / N 的概率之后。

After receiving the nth element, the probability that the element will be inserted into the array = k/n.

有关的任​​何其他元素，它是psented在当前迭代=概率，它是重新psented在previous迭代$ P $重新$ P $概率*概率，它不是在当前迭代置换

For any other element, the probability that it is represented in the current iteration = probability that it is represented in the previous iteration * probability that it is not replaced in the current iteration

= (k/(n-1)) * (n-1)/n = k/n.

这篇关于设计的存储算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！