n元素集的第k个分位数是k-1阶统计量,其将经排序的集合划分为k个相等大小的集合(在1内).给出O(n lg k)时间算法以列出集合的第k个分位数.
直接的解决方案是选择每个k,2k,3k ... ik最小元素,其运行时间为O(kn)(k调用选择O(n)的过程).但这可以优化,比O(kn)更好.在select过程中找到索引'i'的中位数中位数后,我们进行以下递归调用.
如果中位数i的中位数索引> k,则递归调用选择左子阵列A [0 ... i]中的第k个最小元素
如果i <k,则递归地选择右子阵列A [i + 1 ... n]中的第n-i + k个最小元素.
上面的递归调用可以修改如下,这会将因子'k'减少到'log k'吗？
如果中位数i的中值索引> k,则递归地选择左子阵列A [0 ... i]中的第k个最小元素,并递归地选择右子阵列A [i +中的第n个k个最小元素1 ... n].
如果i是<k,则递归地选择右子阵列A [i + 1 ... n]中的第n-i + k个最小元素,并递归地选择左子阵列A中的第k个最小元素[0 ...一世].
主要调用只是选择(A,k,n).
我使用mongodb存储30天的数据,这些数据作为流来到我这里.我正在寻找一种清除机制,通过它我可以丢弃最旧的数据,为新数据创造空间.我以前使用mysql,我使用分区处理这种情况.我保留了30个以日期为基础的分区.我删除了最旧的日期分区并创建了一个新分区来保存新数据.
当我在mongodb中映射相同的东西时,我觉得使用基于日期的"分片".但问题是它使我的数据分发变坏.如果所有新数据都在同一个分片中,那么该分片将会很热,因为有很多人访问它们,并且包含旧数据的分片将减少用户的负载.
我可以有一个基于集合的清除.我可以有30个收藏品,我可以丢弃最旧的收藏品以容纳新数据.但是有几个问题是1)如果我将集合缩小,那么我不能从分片中获益,因为它们是按照每个集合完成的.2)我的查询必须更改为从所有30个集合中查询并进行联合.
请建议我一个很好的清除机制(如果有的话)来处理这种情况.