Фильтр большой коллекции

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

Без большего контекста невозможно предположить, почему производительность такая низкая. Однако я могу предложить некоторые подсказки. Если вещи замедляются на 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;
}     

Answer 3

Хм.

Я предлагаю вам милый трюк:

Возможно, вы могли бы реализовать .CompareTo (или эквивалент на любом языке; я предполагаю .NET) таким образом, что "более близкие" совпадения находятся на вершине. Затем вы просто используете коллекцию, которая сортируется при вставке, и все это произойдет за вас.

Таким образом, вы можете просто перебрать все элементы, и как только вы найдете тот, который не соответствует, остановитесь, потому что вы знаете все ниже, что не соответствует.

Мне было бы интересно посмотреть, как это сработало. Но, возможно, у кого-то еще будет лучшее предложение (и я готов выглядеть дураком, если по какой-то причине это глупо).