Эффективный алгоритм фильтрации

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

Можно ли это сделать через hashset? или двоичный поиск?

Или есть эффективный алгоритм. По сути, я хотел бы улучшить O (n) на что-то меньшее.

Answer 1

Если у вас есть п списков и F фильтров есть Bascially только два подхода: итерация по списку и каждый фильтр применяются к каждому отдельному элементу (держать его, если он проходит все из них, удалить его иначе); или делать то, что вы делаете сейчас, и позволять каждому фильтру перебирать весь список. Оба имеют худшую сложность O (n * f), предполагая удаление элемента O (1) (я рекомендую использовать LinkedList для этого, скопируйте содержимое в одно, если необходимо).

Вы можете действительно улучшить эту сложность, используя свойства вашего ввода. Возможно, вы можете объединить несколько фильтров в один (например, когда они проверяют диапазон), или, возможно, взять один элемент из списка, также приведет к удалению других. Кроме того, если вы можете угадать, какие фильтры, вероятно, удалят больше элементов, он будет расплачиваться, чтобы запустить их первым.

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