優化Java差異XML算法

Question

我目前正在研究能夠區分兩個XML文件的算法。但是，當涉及處理長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; 
    } 
} 

非常感謝您的幫助！

Answer 1

很難確切地說你的代碼如此之慢，但快速瀏覽一下，我發現你有許多迭代器;如果您使用迭代器遍歷包含10000個項目的xml文件，而針對另一個包含10,000個項目的xml文件，則需要執行100,000,000個計算。

我最近創建了一個類似的比較程序，但它不適用於XML文件。 我的過程首先將所有項目放到多個HashMap中，並將它們全部包裝到CachedDatabase類中。按照這種方式生成密鑰，以便新舊地圖對於不同的項目具有相同的密鑰，即使該值已更改。我不知道這是否適用於您的情況。

我的建議是找出每個可比項目的最合適的數據結構。 HashMap和HashSet非常棒，因爲查找時間是O（1）的複雜性，這意味着我不必遍歷整個地圖來檢查項目。

我會在一兩個小時後回到這個問題，看看我能否更全面地回答這個問題。

Answer 2

您有兩個嵌套的while循環，其中大多數比較在嵌套邏輯中非常深。你基本上把它寫成O（n * n）或O（n^2）。

此外，你經歷了一些不必要的循環移動發現差異到數據結構積累他們。事實上，這個類的大部分都不能從算法中分離出數據，這意味着每次你想要訪問數據時，它都是一個額外的棧幀來獲取「數據」對象。

因爲XML是區分大小寫的，所以您不斷地調用小寫字母進行比較，這違反了XML的精神，但假設您需要，請在比較之前立即停止。它在堆上構造了太多新的字符串。您可以通過使用String.equalsIgnoreCase(...)獲得小幅提升。

此外，我會避免使用迭代器來減少你的堆壓力。迭代器是將索引包裝在List中的對象，然後該對象被存儲在堆上。這意味着運行時額外的堆棧幀以及更高的內存使用率。重寫爲使用較少對象的三段for循環可能不太乾淨，但可以加快執行速度。

更好的解決方案是首先索引一棵樹，索引的鍵值是使用密鑰散列進行搜索的重要值。然後在走另一棵樹時，可以快速查找預期值是否存在。這將是一個重要的重寫，但您應該能夠將複雜度降至O（n log n）性能配置文件，這將允許您更快地處理較大的文件。當然，這是有限制的，最終O（n log n）可能不夠快。

Answer 3

您的代碼使用DOM解析XML，因此您在解析之前將整個文檔讀入內存。這需要比SAX或StAX方法多得多的時間和內存，這些方法旨在逐個元素地讀取和處理XML。

想象一下，您正在比較兩個巨大的xml文件，它們在第一個標記中有所不同。用DOM的方法，您將首先在內存中讀取它們，然後進行比較。使用SAX/StAX方法，您將通過xml處理器通知某個元素已到達，因此您可以將其值與第二個xml中的相應元素（如果存在）進行比較，這將使您能夠比DOM方法。