小编use*_*001的帖子

我在表单中有一个规则列表

L1 - >(A,B,C)

L2 - >(D,E),

L3 - >(F,G,A),

L4 - >(C,A)

.....

此列表包含约30k这样的规则.

我有一个输入形式(X,Y,Z)

这创建了一种方法

List <Rule> matchRules(input)

属于类RuleMatcher

我从一个非常简单明了的天真解决方案开始,为了让框架失效,让事情变得有效.

public RuleMatcher(Collection<Rule> rules) {
   this.rules = rules;
}

public Collection<Rule> matchRules(List<Token> input) {
   List<Rule> matchingRules = new ArrayList<>();
   for(Rule r: this.rules) {
        if(r.matches(input)) {
            matchingRules.add(r);
        }
   }
   return matchingRules; 
}

哪个matches是一个非常简单的函数,它检查长度是否相同,然后将每个标记检查为for循环.

这个matchRules函数被调用了数十亿次.

显然这是一个非常糟糕的实现.根据我的分析器,至少有一半的执行时间是在这个匹配函数中花费的.

我在考虑两种可能的解决方案:

A.某种Trie数据结构,它包含可以匹配的规则链.

B.某种哈希函数.每个符号都有一个唯一的标识符.不幸的是,大约有8千个独特的符号,所以这可能很难.

C.对右侧的大小,规则中的令牌数量进行哈希映射调整.不幸的是,大多数规则大小相同,所以这甚至不值得.

D.一个很棒的解决方案,你们中的一个想出来.

我希望有人可以解释这个问题.

编辑:令牌只是一个具有唯一编号的对象.例如,"NN"是一个令牌."NN"的每个实例都完全相同.

匹配代码:

public boolean rhsMatches(List<Token> tokens) {
   if(tokens.size()!=rhsSize()) return false;
   for(int i = 0;i<rhsSize();i++) {
      if(!rightSide.get(i).equals(tokens.get(i)) { …

我已经阅读过此前的一些帖子.参数是列表更容易使用,更灵活.

我之前的所有经验都向我展示了灵活性是一种成本.

我正在设计的程序大量使用列表.我有映射到列表的列表,这些列表被比较,追加和搜索(哦,我的!).

它很容易附加两个列表.listA.appendAll(数组listB).

它几乎同样容易追加两个数组.只需创建一个两者大小的新数组并复制它们.

现在,当这些操作按照成千上万的顺序完成时,我的直觉告诉我,阵列将是一个相当好的选择.当然,我更倾向于使用列表,但不是以牺牲性能为代价

我的直觉本能是正确的,还是真正像数组一样有效的列表？我理解ArrayLists如何使容量增加一倍来增加平均值~O(N),但我需要最有效的选择.