优化Java差异XML算法

-2

我目前正在研究能够区分两个XML文件的算法。但是，当涉及处理长XML文件时，这种算法变得非常慢。你有什么想法如何优化它？优化Java差异XML算法

package comparison; 

import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.HashSet; 
import java.util.Iterator; 
import java.util.List; 
import java.util.Map; 
import java.util.Set; 

import org.jdom2.Document; 
import org.jdom2.Element; 

public class XmlDiff { 
    private ArrayList<String> differences; 
    private Document oldXml; 
    private Document newXml; 
    private Document configuration; 
    private ArrayList<String> idDefinitions; 

    public XmlDiff(Document oldXml, Document newXml, Document configuration) { 
     this.differences = new ArrayList<String>(); 
     this.oldXml = oldXml; 
     this.newXml = newXml; 
     this.configuration = configuration; 
     this.idDefinitions = new ArrayList<String>(); 
     for (int i = 0; i < this.configuration.getRootElement().getChild("Definition_id").getChildren().size(); i++) { 
      idDefinitions.add(this.configuration.getRootElement().getChild("Definition_id").getChildren().get(i).getAttributeValue("Id_def")); 
     } 
    } 

    public Document getOldXml() { 
     return this.oldXml; 
    } 

    public Document getNewXml() { 
     return this.newXml; 
    } 

    public Document getConfiguration() { 
     return this.configuration; 
    } 

    public ArrayList<String> getDifferences() { 
     return differences; 
    } 

    public ArrayList<String> getIdDefinitions() { 
     return this.idDefinitions; 
    } 

    public boolean diffNodeName(Node oldNode, Node newNode) { 
     if (oldNode.getNodeName().toLowerCase() == null && newNode.getNodeName().toLowerCase() == null) { 
      return false; 
     } 

     if (oldNode.getNodeName().toLowerCase() == null && newNode.getNodeName().toLowerCase() != null) { 
      return true; 
     } 

     if (oldNode.getNodeName().toLowerCase() != null && newNode.getNodeName().toLowerCase() == null) { 
      return true; 
     } 

     if (!oldNode.getNodeName().toLowerCase().equals(newNode.getNodeName().toLowerCase())) { 
      return true; 
     } 
     return false; 
    } 

    public boolean diffNodeAttributes(Node oldNode, Node newNode) { 
     HashMap<String, String> oldAttributesHashMap = oldNode.buildHashMapFromAttributes(); 
     HashMap<String, String> newAttributesHashMap = newNode.buildHashMapFromAttributes(); 

     Set oldEntrySet = oldAttributesHashMap.entrySet(); 
     Iterator oldIter = oldEntrySet.iterator(); 

     while (oldIter.hasNext()) { 
      Map.Entry oldMe = (Map.Entry) oldIter.next(); 
      if (newAttributesHashMap.get(oldMe.getKey()) != null && oldAttributesHashMap.get(oldMe.getKey()).toLowerCase().equals(newAttributesHashMap.get(oldMe.getKey()).toLowerCase())) { 
       oldIter.remove(); 
       oldAttributesHashMap.remove(oldMe.getKey()); 
       newAttributesHashMap.remove(oldMe.getKey()); 
      } 
     } 
     return !(oldAttributesHashMap.isEmpty() && newAttributesHashMap.isEmpty()); 
    } 

    public void diffNodeValue(Node oldNode, String oldPath, Node newNode, String newPath) { 
     if (oldNode.getValue() == null && newNode.getValue() != null) { 
      this.getDifferences().add("value modified : " + oldPath + " } " + newPath + " : " + oldNode.getValue() + " changed to " + newNode.getValue()); 
     } 

     if (oldNode.getValue() != null && newNode.getValue() == null) { 
      this.getDifferences().add("value modified : " + oldPath + " } " + newPath + " : " + oldNode.getValue() + " changed to " + newNode.getValue()); 
     } 

     if (!oldNode.getValue().equals(newNode.getValue())) { 
      this.getDifferences().add("value modified : " + oldPath + " } " + newPath + " : " + oldNode.getValue() + " changed to " + newNode.getValue()); 
     } 
    } 

    public void compare(Node oldRoot, String oldPath, Node newRoot, String newPath) { 
     if (oldRoot.hasChildren() && newRoot.hasChildren()) { 
      String memoryOldPath = oldPath; 
      String memoryNewPath = newPath; 
      HashMap<Integer, Node> oldChildren = oldRoot.buildHashMapFromChildren(); 
      HashMap<Integer, Node> newChildren = newRoot.buildHashMapFromChildren(); 

      Set oldEntrySet = oldChildren.entrySet(); 
      Iterator oldIter = oldEntrySet.iterator(); 

      while (oldIter.hasNext()) { 
       Map.Entry oldMe = (Map.Entry) oldIter.next(); 
       int actualIndex = 0; 
       Set newEntrySet = newChildren.entrySet(); 
       Iterator newIter = newEntrySet.iterator(); 
       Node actualOldChild = oldChildren.get(oldMe.getKey()); 
       boolean matched = false; 
       boolean valueChanged = false; 
       boolean attributesChanged = false; 

       while (!matched && newIter.hasNext()) { 
        Map.Entry newMe = (Map.Entry) newIter.next(); 
        Node actualNewChild = newChildren.get(newMe.getKey()); 
        if (actualOldChild.getNodeName().toLowerCase().equals(actualNewChild.getNodeName().toLowerCase())) { 
         if (actualOldChild.getHasSimilarSiblings() || actualNewChild.getHasSimilarSiblings()) { 
          if (actualOldChild.hasAttributes() || actualNewChild.hasAttributes()) { 
           if (!this.diffNodeAttributes(actualOldChild, actualNewChild)) { 
            if (actualOldChild.hasChildren() && actualNewChild.hasChildren()) { 
             int oldResult = this.findIdChild(actualOldChild.getElement().getChildren()); 
             if (oldResult != -1) { 
              matched = actualOldChild.getElement().getChildren().get(oldResult).getValue().toLowerCase().equals(actualNewChild.getElement().getChildren().get(oldResult).getValue().toLowerCase()); 
             } 
             else { 
              matched = true; 
             } 
            } else { 
             matched = true; 
            } 
           } 
           else { 
            attributesChanged = true; 
           } 
          } else { 
           if (actualOldChild.hasChildren() && actualNewChild.hasChildren()) { 
            int oldResult = this.findIdChild(actualOldChild.getElement().getChildren()); 
            if (oldResult != -1) { 
             matched = actualOldChild.getElement().getChildren().get(oldResult).getValue().toLowerCase().equals(actualNewChild.getElement().getChildren().get(oldResult).getValue().toLowerCase()); 
            } 
            else { 
             matched = true; 
            } 
           } 
           else { 
            matched = ((actualOldChild.getValue().toLowerCase() != null && actualNewChild.getValue().toLowerCase() != null&& actualOldChild.getValue().toLowerCase().equals(actualNewChild.getValue().toLowerCase()))|| (actualOldChild.getValue().toLowerCase() == null&& actualNewChild.getValue().toLowerCase() == null)); 
            valueChanged = ((actualOldChild.getValue().toLowerCase() != null && actualNewChild.getValue().toLowerCase() != null && !actualOldChild.getValue().toLowerCase().equals(actualNewChild.getValue().toLowerCase())) || (actualOldChild.getValue().toLowerCase() != null && actualNewChild.getValue().toLowerCase() == null) || (actualOldChild.getValue().toLowerCase() == null && actualNewChild.getValue().toLowerCase() != null)); 
           } 
          } 
         } 
         else { 
          if (actualOldChild.hasAttributes()) { 
           if (!this.diffNodeAttributes(actualOldChild, actualNewChild)) { 
            matched = true; 
           } 
           else { 
            attributesChanged = true; 
           } 
          } 
          else { 
           matched = true; 
          } 
         } 
        } 
        actualIndex = (Integer) newMe.getKey(); 
       } 

       if (matched || valueChanged || attributesChanged) { 
        oldRoot = actualOldChild; 
        newRoot = newChildren.get(actualIndex); 
        oldPath = oldPath + "/" + oldRoot.getNodeName() + "-" + oldMe.getKey(); 
        newPath = newPath + "/" + newRoot.getNodeName() + "-" + actualIndex; 
        oldIter.remove(); 
        newIter.remove(); 
        oldChildren.remove(oldMe.getKey()); 
        newChildren.remove(actualIndex); 
        if (matched) { 
         this.compare(oldRoot, oldPath, newRoot, newPath); 
        } else if (valueChanged) { 
         this.differences.add("value modified : " + oldPath + " } " + newPath + " : " + oldRoot.getValue() + " changed to " + newRoot.getValue()); 
        } 
        else if(attributesChanged) { 
         this.differences.add("attributes changed : " + oldPath + " } " + newPath); 
        } 
        this.compare(oldRoot, oldPath, newRoot, newPath); 
        oldPath = memoryOldPath; 
        newPath = memoryNewPath; 
       } 
      } 

      for (int i : oldChildren.keySet()) { 
       this.getDifferences().add("deleted : " + oldPath + "/" + oldChildren.get(i).getNodeName() + "-" + i + " } " + newPath); 
      } 

      for (int j : newChildren.keySet()) { 
       this.getDifferences().add("added : " + oldPath + " } " + newPath + "/" + newChildren.get(j).getNodeName() + "-" + j); 
      } 
     } 

     else if ((!oldRoot.hasChildren() && newRoot.hasChildren()) || (oldRoot.hasChildren() && !newRoot.hasChildren())) { 
      this.getDifferences().add("structure modified : " + oldPath + " } " + newPath); 
     } 

     else if (!oldRoot.hasChildren() && !newRoot.hasChildren()) { 
      this.diffNodeValue(oldRoot, oldPath, newRoot, newPath); 
     } 
    } 

    public int findIdChild(List<Element> children) { 
     int result = -1; 
     for (int i = 0; i < this.getIdDefinitions().size(); i++) { 
      String name = this.getIdDefinitions().get(i); 
      for (int k = 0; k < children.size(); k++) { 
       if (children.get(k).getName().equals(name)) { 
        result = k; 
        break; 
       } 
      } 
      if (result != -1) { 
       break; 
      } 
     } 
     return result; 
    } 
}

非常感谢您的帮助！

来源

2017-04-21 Alice

你是否介绍了它？这显示了什么？瓶颈在哪里？ – Robert

另外，你是否必须自己写？ https://superuser.com/questions/79920/how-can-i-diff-two-xml-files – Robert

很难确切地说你的代码如此之慢，但快速浏览一下，我发现你有许多迭代器;如果您使用迭代器遍历包含10000个项目的xml文件，而针对另一个包含10,000个项目的xml文件，则需要执行100,000,000个计算。

我最近创建了一个类似的比较程序，但它不适用于XML文件。我的过程首先将所有项目放到多个HashMap中，并将它们全部包装到CachedDatabase类中。按照这种方式生成密钥，以便新旧地图对于不同的项目具有相同的密钥，即使该值已更改。我不知道这是否适用于您的情况。

我的建议是找出每个可比项目的最合适的数据结构。 HashMap和HashSet非常棒，因为查找时间是O（1）的复杂性，这意味着我不必遍历整个地图来检查项目。

我会在一两个小时后回到这个问题，看看我能否更全面地回答这个问题。

来源

2017-04-21 16:11:36 DCON

您有两个嵌套的while循环，其中大多数比较在嵌套逻辑中非常深。你基本上把它写成O（n * n）或O（n^2）。

此外，你经历了一些不必要的循环移动发现差异到数据结构积累他们。事实上，这个类的大部分都不能从算法中分离出数据，这意味着每次你想要访问数据时，它都是一个额外的栈帧来获取“数据”对象。

因为XML是区分大小写的，所以您不断地调用小写字母进行比较，这违反了XML的精神，但假设您需要，请在比较之前立即停止。它在堆上构造了太多新的字符串。您可以通过使用String.equalsIgnoreCase(...)获得小幅提升。

此外，我会避免使用迭代器来减少你的堆压力。迭代器是将索引包装在List中的对象，然后该对象被存储在堆上。这意味着运行时额外的堆栈帧以及更高的内存使用率。重写为使用较少对象的三段for循环可能不太干净，但可以加快执行速度。

更好的解决方案是首先索引一棵树，索引的键值是使用密钥散列进行搜索的重要值。然后在走另一棵树时，可以快速查找预期值是否存在。这将是一个重要的重写，但您应该能够将复杂度降至O（n log n）性能配置文件，这将允许您更快地处理较大的文件。当然，这是有限制的，最终O（n log n）可能不够快。

来源

2017-04-21 16:19:28

您的代码使用DOM解析XML，因此您在解析之前将整个文档读入内存。这需要比SAX或StAX方法多得多的时间和内存，这些方法旨在逐个元素地读取和处理XML。

想象一下，您正在比较两个巨大的xml文件，它们在第一个标记中有所不同。用DOM的方法，您将首先在内存中读取它们，然后进行比较。使用SAX/StAX方法，您将通过xml处理器通知某个元素已到达，因此您可以将其值与第二个xml中的相应元素（如果存在）进行比较，这将使您能够比DOM方法。

来源

2017-04-21 16:22:19

如果没有所有元素，那么做比较很难。我同意DOM会给性能带来内存压力，但是这段代码已经将文档处理并存储在RAM中。如您所描述的，StAX方法非常适合查找不同的节点，但如果您的目标是找到所有不同的节点，那么您将对每个节点进行StAX处理，这是不理想的。 –

优化Java差异XML算法

回答

相关问题