0

我正在编写一个函数，它将树中的所有路径生成为 xpath 语句并将它们存储在下面的包中是一个天真的（对不起，这很长），下面是我优化它的尝试：

/**
 * Create the structural fingerprint of a tree. Defined as the multiset of
 * all paths and their multiplicities
 */
protected Multiset<String> createSF(AbstractTree<String> t,
        List<AbstractTree<String>> allSiblings) {
    /*
     * difference between unordered and ordered trees is that the
     * next-sibling axis must also be used
     * 
     * this means that each node's children are liable to be generated more
     * than once and so are memo-ised and reused
     */

    Multiset<String> res = new Multiset<String>();

     // so, we return a set containing:
     // 1. the node name itself, prepended by root symbol

    res.add("/" + t.getNodeName());
    List<AbstractTree<String>> children = t.getChildren();

    // all of the childrens' sets prepended by this one

    if (children != null) {

        for (AbstractTree<String> child : children) {

            Multiset<String> sub = createSF(child, children);

            for (String nextOne : sub) {
                if (nextOne.indexOf("//") == 0) {
                    res.add(nextOne);
                } else {
                    res.add("/" + nextOne);
                    res.add("/" + t.getNodeName() + nextOne);
                }
            }
        }
    }

    // 2. all of the following siblings' sets, prepended by this one

    if (allSiblings != null) {

         // node is neither original root nor leaf 
         // first, find current node

        int currentNodePos = 0;
        int ptrPos = 0;

        for (AbstractTree<String> node : allSiblings) {
            if (node == t) {
                currentNodePos = ptrPos;
            }
            ptrPos++;
        }

         // 3. then add all paths deriving from (all) following siblings 

        for (int i = currentNodePos + 1; i < allSiblings.size(); i++) {
            AbstractTree<String> sibling = allSiblings.get(i);

            Multiset<String> sub = createSF(sibling, allSiblings);

            for (String nextOne : sub) {
                if (nextOne.indexOf("//") == 0) {
                    res.add(nextOne);
                } else {
                    res.add("/" + nextOne);
                    res.add("/" + t.getNodeName() + nextOne);
                }
            }
        }
    }
    return res;
}

现在（当前）在子类中的优化：

private Map<AbstractTree<String>, Multiset<String>> lookupTable = new HashMap<AbstractTree<String>, Multiset<String>>();

public Multiset<String> createSF(AbstractTree<String> t,
        List<AbstractTree<String>> allSiblings) {

    Multiset<String> lookup = lookupTable.get(t);
    if (lookup != null) {
        return lookup;
    } else {

        Multiset<String> res = super.createSF(t, allSiblings);

        lookupTable.put(t, res);
        return res;
    }
}

我的问题是优化版本用完了堆空间（vm args 设置为 -Xms2g -Xmx2g）并且在中等大的输入上非常慢。任何人都可以看到改善这一点的方法吗？

4

3 回答 3

1

通过探查器运行代码。这是获得有关代码的真实事实的唯一方法。其他一切都只是猜测。

于 2009-08-13T11:54:30.307 回答
1

“将树中的所有路径生成为 xpath 语句”

您正在创建多少条路径？这可能很重要。路径的数量应该是O ( n log n )，但算法可能会更糟，具体取决于它们对父母的孩子使用的表示形式。

您应该对路径的简单枚举进行概要分析，而不必担心包存储。

于 2009-08-13T12:04:28.397 回答
0

您的代码以指数方式消耗 RAM。因此，多一层意味着children.size()更多的 RAM。

尝试使用生成器而不是具体化结果：实现一个 Multiset，它不会预先计算结果，而是在调用next()集合的迭代器时遍历树结构。

于 2009-08-13T12:49:11.833 回答