java - 高效的过滤算法

Question

我正在开发一个应用程序，它是一项服务。我收到一个请求对象，我需要通过一组过滤器传递这个对象并返回响应。我需要大约 10 个过滤器才能使对象通过。

目前应用程序正在对每个过滤器进行顺序搜索，如下所示:

public List<Element) FilterA(Request request){
  for(Element element in items)
  {
     // compare element to request object elements   
     // there are different field checking per object
  }
}

所以有 FilterB、FilterC 等。它们都以类似的方式完成，在 for 循环中比较不同的字段。

这可以通过哈希集来完成吗？还是二分查找？

或者有没有高效的算法。本质上，我想将 O(n) 改进为更少的东西。

Answer 1

如果你有 n 个列表和 f 个过滤器，基本上只有两种方法:遍历列表并将每个过滤器应用于每个单独的元素(如果通过则保留它所有这些，否则将其删除)；或者做你现在正在做的事情，让每个过滤器遍历整个列表。两者都有 O(n*f) 的最坏情况复杂度，假设 O(1) 元素删除(我建议使用 LinkedList 来实现这一点，必要时将内容复制到一个)。

您实际上只能通过利用输入的属性来改进这种复杂性。也许您可以将多个过滤器合并为一个(例如，当它们进行范围检查时)，或者从列表中取出一个元素也会导致其他元素被删除。此外，如果您能猜出哪些过滤器可能会删除更多元素，那么首先运行这些过滤器将会有返回。

是的，这实际上取决于您要过滤的内容类型以及过滤器的外观。在最一般的情况下，你不会赢得太多(只要你已经在使用列表，你可以在 O(1) 时间内从中删除元素)但如果你考虑到你的输入，你可能会有所收获。