実装が遅くなり、ヒープスペースがなくなりました（vm引数が2gに設定されている場合でも）

Question

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引数は-Xms2g -Xmx2gに設定されています）、適度に大きな入力では非常に遅いです。誰もこれを改善する方法を見ることができますか？

Answer 1

コードはRAMを指数関数的に使用します。したがって、1つのレイヤーは、RAMのほうが多いことを意味します（children.size()倍）。

結果をマテリアライズする代わりに、ジェネレータを使用してください。事前に結果を計算しないで、ツリー構造を反復処理して、セットのイテレータにnext()を呼び出します。

Answer 2

プロファイラでコードを実行します。これがコードに関する実際の事実を得る唯一の方法です。他のすべてはちょうど推測です。

Answer 3

は、あなたがどのように多くのパスを作成している

を「XPathステートメントとして、ツリー内のすべてのパスを生成しますか」？これは自明ではありません。パスの数はO（nログn）である必要がありますが、アルゴリズムは親の子にどのような表現を使用するかによってはるかに悪くなる可能性があります。

袋の保管について心配することなく、パスの単純な列挙をプロファイルする必要があります。