Optimize Nested-if using any alternative DataStructure in Java

Question

How to optimize the nested-if block to have a quick comparison. Below is my code where it compares two different java objects. I have a member variable which has the pattern too which lies in one of the if block.

listOfFilters is a subset of Map<String, List<Filter>>. Below method is invoked with the below signature. This list can be as many as 400~1000.

checkRequest(incomingRequest,map.get(incomingRequest.getFiltersForThis()))

Problem -

public boolean checkRequest(Request incomingRequest, List<Filter> listOfFilters){
for(Filter filter : listOfFilters){
    if(incomingRequest.getName() == filter.getName()){
        if(incomingRequest.getOrigen() == filter.getOrigen()){
            .....
                .....
                    .....
                        filterMatched = true;
                    }
                }
            }
        }
    }
}

I need to compare the incoming request as above with each Filter available in the system. O(n) is the complexity.

Is there any way I can use the data structure to reduce the complexity from O(n) to O(log n).

Performance hits when the number of filters configured is more in the system.

I cannot use hashcode() or equals() because the incomingRequest should still succeed if the corresponding filter field is not available for it. It means the incomingRequest should match all the filter values but, in case if it doesn't have related filter field, it should just pass.

public boolean checkMatchOrigen(){
    return (filter.getOrigen() == null || filter.getOrigen().isEmpty()) || 
    (incomingRequest.getOrigen() != null && 
    incomingRequest.getOrigen().trim().equals(filter.getOrigen()));
}

Answer 1

You could create a structure like a decision tree or a database index. There is the rather complicated task.

For example, you have four filters:

1. Name is n1, origin is o1;
2. Name is n1, origin is o2;
3. Name is n2, origin is o1;
4. Name is n2, origin is o5;

One of possible decision trees is:

or-->nameIs(n1)->and->or-->originIs(o1)
  |                     |->originIs(o2)
  |
  |->nameIs(n2)->and->or-->originIs(o1)
                        |->originIs(o5)

The idea is to check 'n1' only once for both filters included it and so on. Usually, the stronges filters have to be checked first. Again, it's difficult to predict, which filter will reject more requests.

For example, i've build the tree from your data structure:

public class DemoApplication {

    // Group filter list by names, except nulls
    public static Map<String, List<Filter>> mapNameToFilter(List<Filter> filters) {
        return filters
                .stream()
                .filter(filter -> filter.getName() != null)
                .collect(groupingBy(Filter::getName));
    }

    // Create predicate to check name and all chunked origins for all entries
    public static Predicate<Request> createPredicateByNameAndOrigin(Map<String, List<Filter>> nameToFilterMap) {

        return nameToFilterMap
                .keySet()
                .stream()
                .map(name -> {
                    final Predicate<Request> filterByName = request -> name.equals(request.getName());
                    final Map<String, List<Filter>> originToFilterMap =  mapOriginToFilter(nameToFilterMap.get(name));
                    return filterByName.and(createPredicateByOrigin(originToFilterMap));
                })
                .reduce(Predicate::or)
                .orElse(filter -> true);
    }

    // Group filter list by origins, except nulls
    public static Map<String, List<Filter>> mapOriginToFilter(List<Filter> filters) {
        return filters
                .stream()
                .filter(filter -> filter.getOrigin() != null)
                .collect(groupingBy(Filter::getOrigin));
    }

    // Create predicate to check origin for all entries
    public static Predicate<Request> createPredicateByOrigin(Map<String, List<Filter>> originToFilterMap) {

        return originToFilterMap
                .keySet()
                .stream()
                .map(origin -> {
                    final Predicate<Request> filterByOrigin = request -> origin.equals(request.getOrigin());
                    return filterByOrigin; // Or go deeper to create more complex predicate
                })
                .reduce(Predicate::or)
                .orElse(filter -> true);
    }

    public static void main(String[] args) {
        List<Filter> list = new ArrayList<>();
        list.add(new Filter("n1", "o1"));
        list.add(new Filter("n1", "o2"));
        list.add(new Filter("n2", "o1"));
        list.add(new Filter("n2", "o5"));

        list.add(new Filter(null, "o10"));
        list.add(new Filter(null, "o20"));

        Predicate<Request> p = createPredicateByNameAndOrigin(mapNameToFilter(list));

        System.out.println(p.test(new RequestImpl("n1", "2")));
        System.out.println(p.test(new RequestImpl("n1", "1")));

        System.out.println(p.test(new RequestImpl("n2", "1")));
        System.out.println(p.test(new RequestImpl("n10", "3")));
    }
}

I've used JDK Predicates which can be presented as a tree with operations as nodes. There is no correct processing with null values in this realization, but it can be easy added.

Note, that my tree is static and need to be rebuilded after each change of the filter list. And it's not balanced. So it's not a solution, just an example.

If you need only filter by equality critera, you could create map for each field. Again, the same grouping idea when checking. In this case, you can dynamically rebuild searching maps:

public class DemoApplication {

    public static List<Filter> filters = new ArrayList<>();

    public static Map<String, Set<Filter>> nameToFiltersMap = new HashMap<>();

    public static Map<String, Set<Filter>> originToFiltersMap = new HashMap<>();

    public static void addFilter(Filter filter) {
        filters.add(filter);

        // Rebuild name index
        Set<Filter> nameFilters = nameToFiltersMap.getOrDefault(filter.getName(), new HashSet<>());
        nameFilters.add(filter);

        nameToFiltersMap.put(filter.getName(), nameFilters);

        // Rebuild origin index
        Set<Filter> originFilters = originToFiltersMap.getOrDefault(filter.getOrigin(), new HashSet<>());
        originFilters.add(filter);

        originToFiltersMap.put(filter.getOrigin(), originFilters);
    }

    public static boolean test(Request request) {
        // Get all filters matched by name
        Set<Filter> nameFilters = nameToFiltersMap.get(request.getName());

        if (nameFilters != null) {
            // Get all filters matched by origin
            Set<Filter> originFilters = originToFiltersMap.get(request.getOrigin());

            for (Filter nameFilter: nameFilters) {
                if (originFilters != null && originFilters.contains(nameFilter)) {
                    return true; //filter matches
                }
            }
        }

        return false;
    }

    public static void main(String[] args){

        addFilter(new Filter("n1", "o1"));
        addFilter(new Filter("n1", "o2"));
        addFilter(new Filter("n2", "o1"));
        addFilter(new Filter("n2", "o5"));
        addFilter(new Filter(null, "o7"));
        addFilter(new Filter(null, "o8"));

        System.out.println(test(new RequestImpl(null, "o7")));
        System.out.println(test(new RequestImpl(null, "o9")));

        System.out.println(test(new RequestImpl("n1", "o1")));
        System.out.println(test(new RequestImpl("n1", "o3")));

        System.out.println(test(new RequestImpl("n2", "o5")));
        System.out.println(test(new RequestImpl("n3", "o3")));
    }
}

Also, you can create a custom tree data structure with dynamic rebuilding and rebalancing. But may be better to use database or searching engine?

Answer 2

First, you should not use Object as the type of the request. At least for this question, use an interface having the appropriate methods, so that your code has a chance to compile.

interface Request { ... }

Then, if you have really many filters, you can group these filters by name.

Map<String, List<Filter>> filtersByName = ...;

After that, your filtering code becomes:

String reqName = blankToNull(request.getName());
if (reqName != null) {
    List<Filter> nameFilters = filtersByName.get(reqName);
    if (anyFilterMatches(nameFilters, request)) {
        return Decision.REJECT;
    }
}

If any of these filters rejects the request, you're done. Otherwise proceed with the next field.

This pattern will be more efficient if the names of the filters differ a lot.