优化简单规则匹配逻辑

问题描述 投票：0回答：1

我有一个简单的规则匹配逻辑算法，想看看是否有办法优化它。

问题如下 - 我有一组规则，我需要为每个传入记录确定哪个规则（如果有）与该记录匹配。该记录本质上是字符串属性到字符串值的映射。该规则由一个整数 id 和一个条件列表组成。每个条件都有一个属性、一个运算符（IN 或 NOT_IN）和一组字符串值。

因此示例规则可能如下所示：

{
    id: "1",
    conditions: [
        {
            attribute: "firstname",
            operator: "IN",
            values: ["Jon", "Fred"]
        },{
            attribute: "surname",
            operator: "NOT_IN",
            values: ["Smith"]
        }
    ]
}

上述规则将匹配 record.get("firstname") 为“Jon”或“Fred”且 record.get("surname") 为 null 或非“Smith”的任何记录。

应用于单条记录时的规则匹配逻辑如下：

  1. 迭代每条规则：
    1. 迭代规则的每个条件：
      1. 从记录属性映射中查找条件属性。
      2. 如果条件运算符为 IN，则应用以下检查：
        1. 如果地图包含该属性并且查找值位于条件值列表中，则条件通过，否则失败。
      3. 否则，如果条件运算符为 NOT_IN，则应用以下检查：
        1. 如果地图不包含该属性，或者查找值不在条件值列表中，则条件通过，否则失败。
    2. 如果所有条件都通过，则规则匹配，不再考虑其他规则。

如果不清楚，列表中规则的顺序很重要，因为将选择第一个匹配的规则。

我在下面包含了一些实现规则数据模型和上述算法的 Java 代码。

上面的逻辑实现起来比较简单，但是涉及到对每条记录的规则进行迭代。我的问题是是否有更有效的算法。

更多数据点：

  1. 规则本质上是静态的。
  2. 大约有 20 亿条记录需要处理。
  3. 记录将以不同大小的批次到达，但通常为 100,000 - 1,000,000。
  4. 属性是预先已知的 - 总共大约有 500 个，但是规则仅使用相对较小的子集 - 概率不超过 20。
  5. 属性值一般不会提前知道。
  6. 每个条件通常包含少量值 - 通常不超过 6 个。
  7. 组成规则的条件将各自使用不同的属性 - 即，您永远不会得到具有两个或多个使用相同属性的条件的规则。
  8. 组成规则的条件数量通常很少 - 通常不超过 4 个。

为了优化算法，我研究了将规则预编译到数据结构中的方法，以加快规则处理速度。起初，我认为决策树结构可能更优化，但目前还不清楚如何构建决策树结构，因为每个规则可能正在测试不同的属性集。我考虑的另一种方法是将每个规则编码为数字，也许是位图或哈希码。

import java.util.*;

public class RulesTest {
    
    // Data model.

    enum Operator {IN, NOT_IN}

    record Condition(String attribute, Operator operator, Set<String> values) {}

    record Rule(int id, List<Condition> conditions) {}

    // Test data.
    
    private static final List<Rule> TEST_RULES = List.of(
            new Rule(
                    1,
                    List.of(
                            new Condition("B", Operator.IN, Set.of("b1", "b2")),
                            new Condition("C", Operator.IN, Set.of("c2", "c4"))
                    )
            ), new Rule(
                    2,
                    List.of(
                            new Condition("A", Operator.IN, Set.of("a1", "a3")),
                            new Condition("C", Operator.NOT_IN, Set.of("c1", "c4")),
                            new Condition("D", Operator.IN, Set.of("d1", "d2", "d3"))
                    )
            ), new Rule(
                    3,
                    List.of(
                            new Condition("B", Operator.NOT_IN, Set.of("b1", "b4")),
                            new Condition("D", Operator.NOT_IN, Set.of("d1", "d2")),
                            new Condition("E", Operator.IN, Set.of("e1"))
                    )
            )
    );

    // Matching logic.
    private static OptionalInt match(List<Rule> rules, Map<String, String> attrValues) {
        for (Rule rule : rules) {
            final boolean pass = rule.conditions
                    .stream()
                    .allMatch(condition -> {
                        final String attrValue = attrValues.get(condition.attribute);
                        return (attrValue != null && condition.values().contains(attrValue))
                                == (condition.operator == Operator.IN);
                    });
            if (pass) {
                return OptionalInt.of(rule.id);
            }
        }

        return OptionalInt.empty();
    }

    private static void test(List<Rule> rules, Map<String, String> attrValues) {
        final OptionalInt optRuleId = match(rules, attrValues);

        System.out.println(attrValues + " -> " + optRuleId);
    }

    public static void main(String[] args) {
        {
            final Map<String, String> attrValues = Map.of(
                    "A", "a1",
                    "B", "b1",
                    "C", "c1"
            );

            test(TEST_RULES, attrValues);
        }

        {
            final Map<String, String> attrValues = Map.of(
                    "B", "b2",
                    "C", "c2"
            );

            test(TEST_RULES, attrValues);
        }

        {
            final Map<String, String> attrValues = Map.of(
                    "A", "a3",
                    "C", "c3",
                    "D", "d3"
            );

            test(TEST_RULES, attrValues);
        }
    }
}
java match rule-engine
1个回答
0
投票

我们可以迭代属性并仅运行那些检查特定属性的规则，而不是迭代规则。

如果您为可应用于属性的规则构建映射（

attributeRuleMap
），您可以稍微提高性能。

类似下面的内容

class Rule {
    int id;
    Map<String, Condition> conditionsMap = new HashMap<>();

    public Rule(int id, List<Condition> conditions) {
        this.id = id;
        conditions.forEach(condition -> {
            attributeRuleMap.computeIfAbsent(condition.attribute, x -> new ArrayList<>()).add(id);
            conditionsMap.put(condition.attribute, condition);
        });
        ruleMap.put(id, this);
    }
}


conditionsMap
用于仅访问我们正在检查规则的特定属性的条件。

那么你的匹配函数可以像下面这样

private static List<Integer> match(Map<String, String> attrValues) {
    List<Integer> rules = new ArrayList<>();
    attrValues.forEach((key, value) ->
                           attributeRuleMap.get(key)
                                           .forEach(rule -> {
                                                        Condition condition = ruleMap.get(rule).conditionsMap.get(key);
                                                        if (condition.values.contains(value) && condition.operator == Operator.IN) {
                                                            rules.add(rule);
                                                        }
                                                    }
                                           ));
    return rules;

}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.