有限排序/过滤算法

Question

我有一个相当大的元素列表(成千上万).

我有一个可以接受或不接受元素的过滤器.

我想要满足过滤器的前100个元素.

到目前为止,我已经对结果进行了排序,然后进入了满足过滤器的前100名.这背后的基本原理是过滤器并不完全快.

但是现在,排序步骤比过滤步骤要长,所以我想以某种方式将它们组合起来.

是否有一种算法可以结合排序/过滤的关注点来获得满足过滤器的前100个结果,而不会产生排序所有元素的成本？

Answer 1

我的直觉是从列表中选择前100个元素(比排序便宜得多,使用您最喜欢的QuickSelect变体).通过过滤器运行它们,产生n成功和100-n失败.如果n < 100然后通过100-n从列表的其余部分的顶部选择元素来重复:

k = 100
while (k > 0):
    select top k from list and remove them
    filter them, yielding n successes
    k = k - n

一切顺利,其运行时间与列表长度成正比,因为每个选择步骤都在该时间内运行,所需的选择步骤数取决于过滤器的成功率,而不是直接取决于列表的大小.

不过,我预计这会有一些不好的情况.如果几乎所有元素都没有通过过滤器,那么它比排序所有内容要慢得多,因为你最终会选择数千次.因此,如果它看起来很糟糕,你可能需要一些标准来挽救,然后再回到整个列表的排序.

它还存在这样的问题:它可能会在最后进行大量的小选择,因为如果过滤条件与排序标准无关,我们预计k会以指数方式衰减.所以你可以通过在每一步选择多于k个元素来改进它.比如说,k除以滤波器的预期成功率加上一个小常数.如果没有可用于预测它的领域知识,则基于过去表现的期望,以及通过实验选择的小常量来避免繁琐的大量步骤来找到最后几个元素.如果您在任何步骤中结束了更多通过过滤器的项目而不是您仍在寻找的项目(即n> k),那么从当前成功的一批中选择前k,您就完成了.

由于QuickSelect为您提供了顶级k而没有对这些k进行排序,因此如果您需要按顺序排在前100位,则需要进行最终的100个元素.