java - 优化递归算法以查找与特定正则表达式匹配的节点

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，只需要一个集合作为累加器。

重复使用您的匹配器。这可能会有所帮助。

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

看看你的正则表达式，也许它可以优化。考虑使用不同的标准，可能除了正则表达式之外。

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