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

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 объектов, она начинает очень медленно. Я искал сеть, но все примеры собираются объектом по объекту в коллекции и запрашивают поле, если оно прошло или нет.

Любые предложения по улучшению производительности?

Thanks

Answer 1

Хмм.

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

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

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

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

Answer 2

Это не должно быть медленным, если ваши сравнения не медленны.

Сканирование 500 объектов должно быть очень быстрым (конечно, вы не указываете, что такое «медленный», или ваш жесткий, но даже еще ...).

Ваш PassFilterVal будет «более дорогим» из-за вызова метода, чем сравнение в строке, но, поскольку он одинаковый для всех из них, я думаю, мы застряли с тем, что у нас есть.

Вы можете заказать параметры, так что наиболее избирательными являются первые.

Целью здесь является использование короткого замыкания AND для сброса как можно быстрее, что ограничивает количество фактических сравнений.

Другое, что вы можете сделать, это оптимизировать его для «наиболее распространенных запросов».

ВСЕ Критерии всегда используются? Если нет, вы должны ограничить сравнение с теми, которые на самом деле используются. Равенство в этом случае действительно дорого (17 вызовов метода и 17 сравнений «неизвестной» сложности). Если у вас есть какой-то подстановочный знак или значение «не заботясь», вы можете попробовать и пропустить их от сравнения вообще.

Другой идеей является сортировка элементов по 17 критериям. Затем вы используете двоичный поиск для элемента, который соответствует всем 17 полям, и, наконец, итерации для остальных элементов, пока они не STOP соответствуют вашим критериям. Конечно, вам нужно всегда правильно сортировать список, но после его сортировки это двоичная вставка, которая будет довольно быстрой.Если вы читаете намного больше, чем добавляете в список, это должно быть чистая прибыль.

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; 
}