有限的排序/筛选算法

Question

我有一个非常庞大的元素列表（数十万）。

我有一个过滤器，可以接受或者拒绝元素。

我想要获得符合过滤器条件的前100个元素。

目前，我的做法是先对结果进行排序，然后再取前100个符合条件的元素。 这样做的原因是过滤器不是完全快速的。

但现在，排序步骤比筛选步骤花费更长时间，所以我想以某种方式将它们结合起来。

是否有一种算法可以将排序/过滤的考虑因素结合起来，以获取前100个符合过滤器条件的结果，而不需要排序所有元素的成本呢？

- Kevin Dolan

---

如果不排序，你会如何定义“top”？ - dlev

@dlev：你仍然需要排序...但如果你知道你只需要一些“最高”的值，你就不必对整个集合进行排序。 - StriplingWarrior

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进行排序，因此如果需要有序的top 100，则需要对100个元素进行最终排序。

- Steve Jessop

---

+1 这正是我要写的内容。为了完整起见，预期运行时间为O(np + k log k)，并且需要进行O(np)次过滤应用，其中p是任何元素通过过滤器的概率。顺便说一句，你不需要随着窗口大小呈指数增长 - 如果假设元素独立地以概率p通过过滤器，则概率会呈指数下降。 - templatetypedef

是的，我的噩梦场景“几乎所有元素都无法通过筛选器”只有在列表变得更长时才可能成为现实，如果筛选器不独立于列表长度和元素的排序顺序，而实际上在问题更大的版本中变得更加挑剔。处理任何这样的相互关系有点超出了简单复杂性分析的范围，我认为。因此，我对您假设的独立性感到满意，并且完全假设可以避免担心那个致命案例。 - Steve Jessop

实际上，你评论中的 p 不是表示元素通过过滤器的概率吗？也就是说，如果过滤器接受大部分元素，则我们应该要求更少的过滤器运用，而不是更多。 - Steve Jessop

我喜欢这个解决方案，尽管我同意你不应该在每一步选择k，因为如果你得到99个通过第一次命中的噩梦，而下一个通过的恰好得分最低，那么你基本上就会遇到n^2的情况。 我可能会将其分成固定大小的块，因为过滤器的成功概率在很大程度上取决于用户执行搜索。 - Kevin Dolan

此外，如果我们预计会有一定比例的失败率，那么将初始选择设为大于k可能是有意义的。 我将尝试各种分块方法并报告结果。 - Kevin Dolan

Answer 2

我曾通过使用二叉树进行排序，并在插入过程中保持当前节点左侧元素的计数来解决这个确切的问题。有关详细信息，请参见http://pub.uni-bielefeld.de/publication/2305936（图4.4等）。

- thiton

Answer 3

如果我理解正确，你有两个选择：

• 选择100个元素-进行N次过滤检查操作，然后进行100(lg 100)次排序。

• 排序然后选择100个元素-至少需要N(lg N)次排序，然后再进行选择。

第一种方法听起来似乎比先排序再选择更短。

- Nicholas

---

虽然过滤整个列表的渐进时间更快，但实际的过滤操作有与之相关的非平凡成本。在某一关键点上，先进行过滤比先排序更快，但对于大多数情况，先排序更快。 我认为所接受的解决方案相当优雅地解决了这两个问题。 - Kevin Dolan

Answer 4

我会先进行筛选，然后将筛选结果插入到优先队列中。跟踪优先队列中的项目数量，在插入之后，如果它大于你想保留的数量（在你的情况下是100个），则弹出最小的项目并丢弃它。

- Jerry Coffin

Answer 5

史蒂夫建议使用快速排序是一个好主意。

1 读取前1000个元素。
2 对它们进行排序并选择第100个最大的元素。
3 在整个文件上运行一次快速排序，以步骤2中的元素作为枢轴。
4 选择快速排序通过结果的上半部分进行进一步处理。

您保证在单次快速排序的上半部分至少有100个元素。假设前1000个元素相当代表整个文件，则在步骤4中应该得到原始元素的约十分之一。

- rossum

---

我建议使用Quickselect算法（http://en.wikipedia.org/wiki/Quickselect#Partition-based_general_selection_algorithm），而不是Quicksort算法。虽然分割元素的步骤相同，但Quickselect算法仅使用它来查找前k个元素，而不是对数据进行排序。 - Steve Jessop

我的错误。抱歉。这就是我试图用“一遍快速排序”这个短语表达的相同观点。 - rossum