优化递归算法以查找与某个正则匹配的节点

Question

问题

我正在为reddit帖子进行网络刮板工作，我制作了一种有效的算法。事情是，我发现算法的复杂性令人震惊，我想改进它。

我认为将此算法转换为使用尾随递归的东西会加快我的流程，但我似乎真的无法使它起作用。

我正在寻找的

我正在寻找有关如何改善它的指南或建议。当然，这不必是打字的修复程序。只是向正确的方向点头会对我有很大帮助！

高级概述

basecase
    if node.null return emptylist
recursivecase
    childvalues := recursion on all the childs of this node
    is current node a match with regex?
        yes -> return this post and child values in an accumulator
        no  -> return child values in an accumulator

原始代码

private Pattern pattern = Pattern.compile("...someregex...")   
private List<String> traverse(CommentNode node) {
    //base case
    if(node == null || node.isEmpty()) {
        return Collections.emptyList();
    } else {
    //recursive case
        //collect all the child values (this is NOT tail recursion)
        Set<String> childValues = new HashSet<>();
        for (CommentNode child : node.getChildren()) {
            List<String> previous = traverse(child);
            childValues.addAll(previous);
        }
        //check if the current node complies with the regex
        boolean matching;
        if(node.getComment().getBody() == null) {
            matching = false;
        } else {
            Matcher m = pattern.matcher(node.getComment().getBody());
            matching = m.matches();
        }
        //if it is matching, add it to the childvalues so it is
        //properly returned 
        if(matching) {
            if(childValues.isEmpty()) {
                ArrayList<String> temp = new ArrayList<>();
                temp.add(node.getComment().getBody());
                return temp;
            } else {
                childValues.add(node.getComment().getBody());
            }
        }
        //cast the set to an array list
        ArrayList<String> returnList = new ArrayList<>();
        returnList.addAll(childValues);
        //return the values of the children and the current node
        return returnList;
    }
}

Answer 1

正如已经说过的，很可能，您在正则匹配中花费了大部分时间，并且您无法改进。

无论如何，写一个助手方法

private void collectTo(List<String> result, CommentNode node) ...

或可能是助手课程，以避免不必要的复制。忘了尾巴回收，因为它不会给您任何大幅度的加速。如果三个非常深，请使用队列或堆栈模拟递归以避免堆栈溢出。

简化您的代码。您想要Set还是List？如果您放下重复项，然后使用Set作为结果，否则请在各处使用List。

实际上，您不需要childValues，也不需要temp，也不需要returnList，除了单个集合作为累加器。

重用您的Matcher。这可能会有所帮助。

代码对于它的作用太复杂了。

看一下您的正则表达式，也许可以优化。考虑使用不同的标准，可能还包括正则条件。

private void collectTo(List<String> result, CommentNode node, Matcher matcher) {
    if (node == null) return;
    String s = node.getComment().getBody();
    if (s != null && matcher.reset(s).matches()) {
         result.add(s);
    }
    for (CommentNode child : node.getChildren()) {
        collectTo(result, child, matcher);
    }
}