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

Question

问题

我正在为reddit帖子做一个web scraper，我做了一个有效的算法。事情是，我发现算法的复杂性相当令人震惊，我想改进它。

我假设将此算法转换为使用尾递归的方法会加快我的进程，但我似乎无法让它工作。

我正在寻找什么

我正在寻找关于如何改进它的指南或建议。这当然不一定是打字修复。只是向正确的方向点头对我帮助很大！

高级概述

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