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

重用您的 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);
    }
}