Mise en œuvre lente et manque d'espace mémoire (même lorsque vm args est défini sur 2g)

Question

J'écris une fonction qui génère tous les chemins dans un arbre comme des instructions xpath et les stocker dans un sac ci-dessous est un naïf (désolé est longue) et en dessous est ma tentative de l'optimiser:

/** 
* 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; 
} 

et maintenant l'optimisation qui est (actuellement) dans une sous-classe:

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

mon problème est que la version optimisée à court de tas d'espace (les arguments vm sont définis à -Xms2g -Xmx2g) et est très lent sur une entrée modérément grande. Quelqu'un peut-il voir un moyen d'améliorer cela?

Answer 1

Votre code mange la RAM de manière exponentielle. Donc, une couche de plus signifie children.size() fois plus de RAM. Essayez d'utiliser un générateur au lieu de matérialiser les résultats: Implémentez un Multiset qui ne calcule pas les résultats au préalable mais parcourt l'arborescence en appelant next() sur l'itérateur de l'ensemble.

Answer 2

Exécutez le code via un profileur. C'est le seul moyen d'obtenir des faits réels sur le code. Tout le reste n'est que conjecture.

Answer 3

« génère tous les chemins dans un arbre comme instructions XPath »

Combien de chemins sont en train de créer vous? Cela peut être non trivial. Le nombre de chemins doit être (n log n), mais l'algorithme pourrait être bien pire selon la représentation qu'ils utilisent pour les enfants d'un parent.

Vous devriez décrire l'énumération simple des chemins sans vous soucier du stockage des sacs.