Алгоритм для слияния двух объектов наиболее эффективно

Question

У меня есть класс Level1, который содержит String и список Level2 объектов. Объекты Level2 содержат String и список Level3 объектов. Каждый объект Level3 содержит 2 строковых атрибута, attribute1 и attribute2. (Это похоже на дерево 3 уровня)

Сейчас у меня есть два объекта класса Level1: objectA и objectB.

objectB входит в состав objectA. Все ветви внутри B будут иметь совпадение в A).

objectA У листьев будет attribute1. objectB будет иметь attribute2.

Я хочу наиболее эффективный способ объединить objectA в objectB. По объему я имею в виду, что новый объект будет иметь все ветви и атрибуты objectA и атрибуты objectB, где соответствующие. Все узлы уникальны.

Акустический алгоритм имел бы сложность O(n^2), что плохо для моей цели. Из-за дерева я надеюсь, что есть O(n log n), но я не могу найти его

Спасибо!

Класс для Level1:

public class Level1 { 

    private String level1string; 

    private List<Level2> level2List; 

    public String getLevel1string() { 
     return level1string; 
    } 

    public void setLevel1string(String level1string) { 
     this.level1string = level1string; 
    } 

    public List<Level2> getLevel2List() { 
     return level2List; 
    } 

    public void setLevel2List(List<Level2> level2List) { 
     this.level2List = level2List; 
    } 
} 

Класс для Level2:

public class Level2 { 
    private String level2string; 

    private List<Level3> level3List; 

    public String getLevel2string() { 
     return level2string; 
    } 

    public void setLevel2string(String level2string) { 
     this.level2string = level2string; 
    } 

    public List<Level3> getLevel3List() { 
     return level3List; 
    } 

    public void setLevel3List(List<Level3> level3List) { 
     this.level3List = level3List; 
    } 
} 

Класс для Level3:

public class Level3 { 

    private String attribute1; 

    public String getAttribute1() { 
     return attribute1; 
    } 

    public void setAttribute1(String attribute1) { 
     this.attribute1 = attribute1; 
    } 

    public String getAttribute2() { 
     return attribute2; 
    } 

    public void setAttribute2(String attribute2) { 
     this.attribute2 = attribute2; 
    } 

    private String attribute2; 
} 

Вот два примера элементов level1_A и level1_B

public class constructobjects { 

    private Level3 level3_A1 = new Level3(); 
    private Level3 level3_A2 = new Level3(); 
    private Level3 level3_A3 = new Level3(); 
    private Level3 level3_A4 = new Level3(); 
    private Level3 level3_A5 = new Level3(); 
    private Level3 level3_A6 = new Level3(); 
    private Level3 level3_A7 = new Level3(); 
    private Level3 level3_A8 = new Level3(); 

    private Level2 level2_A1 = new Level2(); 
    private Level2 level2_A2 = new Level2(); 
    private Level2 level2_A3 = new Level2(); 

    private Level1 level1_A = new Level1(); 

    public void constructObjectA(){ 
     level3_A1.setAttribute1("sampleAttribute1"); 
     level3_A2.setAttribute1("sampleAttribute2"); 
     level3_A3.setAttribute1("sampleAttribute3"); 
     level3_A4.setAttribute1("sampleAttribute4"); 
     level3_A5.setAttribute1("sampleAttribute5"); 
     level3_A6.setAttribute1("sampleAttribute6"); 
     level3_A7.setAttribute1("sampleAttribute7"); 
     level3_A8.setAttribute1("sampleAttribute8"); 

     List<Level3> level3List_A1 = new ArrayList<>(); 
     List<Level3> level3List_A2 = new ArrayList<>(); 
     List<Level3> level3List_A3 = new ArrayList<>(); 

     level3List_A1.add(level3_A1); 
     level3List_A1.add(level3_A2); 
     level3List_A1.add(level3_A3); 

     level3List_A2.add(level3_A4); 
     level3List_A2.add(level3_A5); 
     level3List_A2.add(level3_A6); 

     level3List_A3.add(level3_A7); 
     level3List_A3.add(level3_A8); 

     level2_A1.setLevel3List(level3List_A1); 
     level2_A2.setLevel3List(level3List_A2); 
     level2_A3.setLevel3List(level3List_A3); 

     level2_A1.setLevel2string("sampleLevel2String_foo"); 
     level2_A2.setLevel2string("sampleLevel2String_bar"); 
     level2_A3.setLevel2string("sampleLevel2String_chi"); 

     List<Level2> level2List_A1 = new ArrayList<>(); 

     level2List_A1.add(level2_A1); 
     level2List_A1.add(level2_A2); 
     level2List_A1.add(level2_A3); 

     level1_A.setLevel2List(level2List_A1); 
     level1_A.setLevel1string("root"); 


    } 



    private Level3 level3_B1 = new Level3(); 

    private Level3 level3_B3 = new Level3(); 

    private Level3 level3_B8 = new Level3(); 

    private Level2 level2_B1 = new Level2(); 
    private Level2 level2_B3 = new Level2(); 

    private Level1 level1_B = new Level1(); 

    public void constructObjectB(){ 
     level3_B1.setAttribute2("otherAttribute1"); 
     level3_B3.setAttribute2("otherAttribute3"); 
     level3_B8.setAttribute2("otherAttribute8"); 

     List<Level3> level3List_B1 = new ArrayList<>(); 
     List<Level3> level3List_B3 = new ArrayList<>(); 

     level3List_B1.add(level3_B1); 
     level3List_B1.add(level3_B3); 
     level3List_B3.add(level3_B8); 

     level2_B1.setLevel3List(level3List_B1); 
     level2_B3.setLevel3List(level3List_B3); 

     level2_B1.setLevel2string("sampleLevel2String_foo"); 
     level2_B3.setLevel2string("sampleLevel2String_chi"); 

     List<Level2> level2List_B1 = new ArrayList<>(); 

     level2List_B1.add(level2_B1); 
     level2List_B1.add(level2_B3); 

     level1_B.setLevel2List(level2List_B1); 
     level1_B.setLevel1string("root"); 


    } 

} 

Answer 1

Я не знаю, если это именно то, что вы хотите, но, насколько я знаю, я бы использовал хеш-карты вместо списков массивов. Для экземпляров LevelX, которые можно использовать в HashMap, вам необходимо переопределить методы hashCode и equals.

Например, в Level1:

Map<String,Level2> children = new HashMap<>(); 
final String name; 

public Level1(String name) { 
    // add to the pool or use the existing reference to 
    // avoid duplicating information 
    this.name = name.intern(); 
} 

@Override 
public boolean equals(Object o) { 
    if (o == null) return false; 
    if (this == o) return true; 
    if (getClass() != o.getClass()) return false; 
    Level1 other = (Level1) o; 
    // assuming name is never null 
    return other.name.equals(name); 
} 

@Override 
public int hashCode() { 
    return level1String.hashCode(); 
} 

Затем, метод слияния бы просто объединить hashsets и сложность будет O (N + M), где п (соответственно м.) Является количество узлов в A (соответственно B).

// I assume other is "contained" in this 
public Level1 merge(Level1 other) { 
    Level1 result = new Level1("root"); 
    for (Level2 child : other.children) { 
     // cannot be null if other is contained in this 
     Level2 corresponding = children.get(child.name); 
     corresponding.children.putAll(child.children); 
    } 
}