筛选大型集合

Question

我有一个MyClass对象集合，我需要通过17个文件的组合来过滤它。

我实现了一个对象MyClassFilter，其中包含17个可能的字段和每个字段的条件，以及一个方法：

bool PassFilter(MyClass ObjectToEvaluate)
{
  return PassFilterVal(this.Workstream, ObjectToEvaluate.WorkStream)
    && PassFilterVal(this.AssignedTo, ObjectToEvaluate.AssignedTo)
    && PassFilterVal(this.ProcessingGroup, ObjectToEvaluate.ProcessingGroup)
    && PassFilterVal(this.ScheduledStart, ObjectToEvaluate.ScheduledStart)
    && PassFilterVal(this.EntityName, ObjectToEvaluate.EntityName)
    && PassFilterVal(this.TaskIDs, ObjectToEvaluate.TaskID)
    && PassFilterVal(this.ElementIDs, ObjectToEvaluate.EntityID)
    && PassFilterVal(this.MappingIDs, ObjectToEvaluate.MappingID)
    && PassFilterVal(this.EntityStatus, ObjectToEvaluate.EntityStatus)
    && PassFilterVal(this.EntityType, ObjectToEvaluate.EntityType)
    && PassFilterVal(this.NumberOfSteps, ObjectToEvaluate.ListOfSteps.Count)
    && PassFilterVal(this.NumberOfDependancies, ObjectToEvaluate.ListOfParentDependancies.Count)
    && PassFilterVal(this.NumberOfOpenIssues, ObjectToEvaluate.ListOfAllIssues.CountOpen)
    && PassFilterVal(this.NumberOfRequirementsLinked, ObjectToEvaluate.RequierementsLinked)
    ;
}

我的集合有一个方法

ListOfMyClass FilterList(MyClassFilter Filter){
    ListOfMyClass FilteredList = new ListOfMyClass();
    foreach (MyClass Task in this)
    {
      if (Filter.TaskPassFilter(Task))
        FilteredList.Add(Task);
    }
    return FilteredList;
}

只要集合很小，它就会工作得很好，但当我有500个对象时，它就会变得非常慢。我已经搜索了网络，但所有的示例都是在集合中一个对象接一个对象地进行，并按字段询问它是否通过。

对于如何提高性能有什么建议吗？

谢谢

Answer 1

这不应该很慢，除非你的比较很慢。

扫描500个对象应该是非常快的(当然你没有提到什么是“慢”，或者你的努力，但即使如此……)。

你的PassFilterVal将会因为方法调用而比比较更“昂贵”，但是由于它们都是一样的，我想我们只能使用我们所拥有的了。

您可以对参数进行排序，以便最先选择最具选择性的参数。

这里的目标是利用AND的短路来尽可能快地转储，从而限制实际比较的数量。

您可以做的另一件事是首先针对“最常见的查询”对其进行优化。

是否总是使用所有的标准？如果不是，则应将比较限制为实际正在使用的比较。在这种情况下，相等实际上是昂贵的(17个方法调用和17个“未知”复杂性的比较)。如果您有某种类型的通配符或“无关”值，您可以尝试跳过这些值，根本不进行比较。

另一个想法是根据所有17个标准对元素进行排序。然后，对匹配所有17个字段的元素使用二进制搜索，最后迭代剩余的元素，直到它们不再与您的条件匹配。当然，您需要始终保持列表的正确排序，但一旦排序，它是一个二进制插入，这将是相当快的。如果你阅读的内容比添加到列表中的内容多得多，这应该是一种净收益。

Answer 2

嗯。

我给你提个小把戏：

也许您可以以这样一种方式实现.CompareTo (或任何语言中的等效语言；我假设是.NET)，即“更接近”的匹配项位于顶部。然后，您只需使用一个在插入时进行排序的集合，这一切都将为您实现。

这样，你就可以遍历所有的项目，一旦找到一个不匹配的项目，就停止，因为你知道下面所有不匹配的项目。

我很有兴趣看看这是如何实现的。但也许其他人会有更好的建议(如果出于某种原因这是愚蠢的，我准备看起来像个傻子)。

Answer 3

如果没有更多的上下文，实际上不可能提出性能如此缓慢的原因。然而，我可以提供一些线索。如果在大约500个项目时速度变慢，可能在某个地方潜伏着O(N^2)算法(或者更糟)。我猜测，在每次比较期间，您的一个或多个属性正在遍历大量数据。

对于C#中的属性，很难知道它们是如何实现的，例如，像NumberOfDependancies这样无害的东西每次被调用时都会遍历一个非常大的图。或者它可能正在生成一个列表来计算依赖项。如果可能，我会计算一次这些值，并将它们存储在类中(如果可能)。然而，当我看到它使用的上下文时，我看到了另一个问题：

PassFilterVal(this.NumberOfDependancies, ObjectToEvaluate.ListOfParentDependancies.Count

如果"ListOfParentDependancies“是一个IEnumerable<>，那么每次调用它时，您都将遍历所有依赖项的列表，以计算其数量。

你的过滤器功能，就性能而言是很好的。为了优雅，以及可能的性能提升，我将按如下方式实现它

IEnumerable<MyClass> FilterList(MyClass filter) {
    foreach (MyClass task in this)
       if (filter.TaskPassFilter(task))
         yield return task;
}