2

我正在开发一个服务应用程序。我正在接收一个请求对象，我需要通过一组过滤器传递这个对象并返回响应。我需要大约 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) 改进为更少的东西。

4

1 回答 1

3

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

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

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

于 2012-05-27T20:34:09.037 回答