hal*_*bra 5 algorithm optimization
这是一个面试饼干的问题 -
鉴于您正在以恒定速率从仪器接收样本,并且您有恒定的存储空间,您将如何设计一种存储算法,使我能够获得有代表性的数据读取,无论何时查看它？换句话说,代表了迄今为止系统的行为.
我无法理解它.所以,我正在寻找想法.
krj*_*ani 27
假设您有内存来存储k元素.将第一个k元素存储在内存中的数组中.现在当你收到第n个元素(where 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.
| 归档时间： |
|
| 查看次数： |
2114 次 |
| 最近记录： |