高效的过滤算法

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(1( 元素，两者都具有 O(n*f( 的最坏情况复杂度(我建议使用 LinkedList 来实现这一点，如有必要，将内容复制到一个(。

实际上，只有利用输入的属性，才能提高这种复杂性。也许您可以将多个过滤器组合成一个(例如，当它们是范围检查时(，或者从列表中获取一个元素也会导致删除其他元素。此外，如果您能猜到哪些过滤器可能会删除更多元素，那么首先运行这些过滤器将得到回报。

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