java - 使用 Java 中的任何替代 DataStructure 优化 Nested-if

问题描述

如何优化嵌套 if 块以进行快速比较。下面是我的代码，它比较了两个不同的 java 对象。我有一个成员变量，它也具有位于 if 块之一中的模式。

listOfFilters 是的子集Map<String, List<Filter>>。使用以下签名调用以下方法。这个列表可以多达400~1000。

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

问题 -

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

我需要将上述传入请求与系统中可用的每个过滤器进行比较。O(n) 是复杂度。

有什么方法可以使用数据结构将复杂度从 O(n) 降低到 O(log n)。

当系统中配置的过滤器数量更多时，性能会受到影响。

我不能使用 hashcode() 或 equals() 因为如果相应的过滤器字段不可用，incomingRequest 应该仍然成功。这意味着incomingRequest 应该匹配所有过滤器值，但是如果它没有相关的过滤器字段，它应该只是通过。

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

标签： javadata-structures

解决方案

您可以创建像决策树或数据库索引这样的结构。有一个相当复杂的任务。

例如，您有四个过滤器：

名称为n1，原点为o1；
名称为n1，原点为o2；
名称为n2，原点为o1；
名字是n2，起源是o5；

一种可能的决策树是：

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

我们的想法是对包含它的两个过滤器只检查一次“n1”，依此类推。通常，必须首先检查强过滤器。同样，很难预测哪个过滤器会拒绝更多请求。

例如，我已经根据您的数据结构构建了树：

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

我使用了 JDK谓词，它可以以树的形式呈现，操作作为节点。在这个实现中没有正确处理空值，但可以很容易地添加。

请注意，我的树是静态的，每次更改过滤器列表后都需要重建。而且不平衡。所以这不是一个解决方案，只是一个例子。

如果您只需要按相等标准过滤，您可以为每个字段创建地图。同样，检查时的分组想法相同。在这种情况下，您可以动态重建搜索地图：

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

此外，您可以创建具有动态重建和重新平衡的自定义树数据结构。但是使用数据库或搜索引擎会更好吗？

java - 使用 Java 中的任何替代 DataStructure 优化 Nested-if

问题描述

解决方案

推荐阅读