Java差分XMLアルゴリズムの最適化

Question

現在、2つの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

あなたのコードを非常に遅くするものを正確に言うのは難しいですが、一見したところでは、たくさんのイテレータがあることがわかります。イテレーターを使用して10,000個のアイテムを含むxmlファイルを通過する場合、10,000個のアイテムを含む別のXMLファイルを処理する場合、実行する計算量は100,000,000です。

私は最近類似の比較プログラムを作成しましたが、XMLファイルではありませんでした。 私のプロセスは、まず、すべてのアイテムを複数のHashMapsに入れ、すべてをCachedDatabaseクラスにラップします。キーは、値が変更されたとしても、古いマップと新しいマップの両方が異なるアイテムに対して同じキーを持つように生成されました。これがあなたのシナリオに当てはまるかどうかわかりません。

私のアドバイスは、各比較可能なアイテムの最も適切なデータ構造を把握することです。ルックアップ時間がO（1）の複雑さなので、HashMapsとHashSetは素晴らしいです。これは、アイテムをチェックするためにマップ全体を走査する必要がないことを意味します。

私はこの質問に1〜2時間で戻り、私があなたにもっと完全に答えることができるかどうかを見ていきます。

Answer 2

あなたは2つのネストされたwhileループを持っています。ネストされたロジックでは、ほとんどの比較がかなり深いです。あなたは基本的にこれをO（n * n）またはO（n^2）と書いています。

また、発見された相違点をいくつかの不必要なループを経て、それらを蓄積するデータ構造に移動します。実際、このクラスのほとんどは、アルゴリズムからデータを分離するためのものではありません。つまり、データにアクセスするたびに、「データ」オブジェクトを取得する余分なスタックフレームです。

XMLの精神に違反しているため、比較のために小文字を使用することを常に求めていますが、XMLでは大文字と小文字が区別されるため、ヒープ上に新しい文字列が多すぎます。 String.equalsIgnoreCase(...)を使用すると、少しのブーストが得られるかもしれません。

また、ヒープの負担を軽減するためにイテレータを使用しないでください。反復子は、List内のインデックスをラップし、そのオブジェクトがヒープに格納されるオブジェクトです。これは、実行時の余分なスタックフレームと、より大きなRAM使用量を意味します。オブジェクト指向の少ない3つのループを使用してループを再作成すると、読みにくくなる可能性がありますが、実行速度は少し向上します。

より良い解決策は、最初に1つのツリーにインデックスを付けることです。インデックスのキーは、キーのハッシュを使用して検索するのは簡単なものです。次に、他のツリーを歩いているときに、期待値が存在するかどうかを素早く調べることができます。これは大きな書き換えになりますが、複雑さをO（n log n）のパフォーマンスプロファイルにすることができます。これにより、より大きなファイルをより高速に処理できるようになります。もちろん、限界があり、最終的にO（n log n）が十分に速くない可能性があります。

Answer 3

あなたのコードは、XMLを解析するためにDOMを使用しているため、解析する前にドキュメント全体をメモリに読み込んでいます。これは、要素ごとにXML要素を読み取り処理するために、SAXまたはStAXアプローチよりもはるかに多くの時間とメモリを必要とします。

巨大なxmlの2つを比較しているとします。 DOMのアプローチでは、まずメモリ内でそれらを読み込んで比較します。 SAX/StAXアプローチではxmlプロセッサーからいくつかの要素に到達したことを通知されるので、その値を対応する要素（存在する場合）と比較することができます。xmlで、より速く差異を検出できますDOMアプローチ。