Javaで2つのリストを比較する効率的な方法は何ですか？

Question

私は、dbからjavaオブジェクトのリストを取得し、それを既に検索された古いリストと比較し、その中のdelta（difference）要素を見つけて返すプログラムを持っています。 SetメソッドUnion（）、Intersection（）などを使用するだけでなく、メモリ不足を回避するよりも、これを行う最良の方法があるのだろうかと思いますか？ リストのサイズは200kにすることができます。 私のプロジェクトでSpring 3.2.8.RELEASEのバージョンを使用しています。

public class Tester { 

    private List<AddressInfo> oldListOfAddresses; 

    @Scheduled(cron="0 1 6 * * ?") // 6 AM everyday 
    public Map<String, AddressInfo> getCompany() { 
     try { 
      Map<String, AddressInfo> companyMap = new HashMap<>(); 
      String sql = "Some sql query which return Address Info."; 
      List<AddressInfo> newListOfAddresses = jdbcTemplate.query(sql, new Object[0], 
        new FacilityNewMapper()); 
      if (newListOfAddresses == null || newListOfAddresses.size() = 0) { 
       throw new FacilityLookUpException("List of clinic Info from facilities is empty..."); 
      } else { 

       // I have to find the delta of new list and old list here. 
       // I need an efficient (Space and Time) way of finding delta. 
       List<AddressInfo> deltaList = newListOfAddresses - oldListOfAddresses; //Something like this 

       for (AddressInfo comp : deltaList) { 
        if (comp != null) { 
         companyMap.put(comp.getLocationId(), comp); 
        } 
       } 
       oldListOfAddresses = newListOfAddresses; 
      } 
      return companyMap; 
     } catch (Exception e) { 
      throw new CompanyLookUpException(
        "List of company addresses is empty..." + e.getMessage()); 
     } 
    } 
} 

AddressInfo bean。

public class AddressInfo{ 

    private String locationId; 
    private String streetName; 
    private String city; 
    private String state; 
    private String country; 

    public String getLocationId() { 
     return locationId; 
    } 
    public void setLocationId(String locationId) { 
     this.locationId = locationId; 
    } 
    public String getStreetName() { 
     return streetName; 
    } 
    public void setStreetName(String streetName) { 
     this.streetName = streetName; 
    } 
    public String getCity() { 
     return city; 
    } 
    public void setCity(String city) { 
     this.city = city; 
    } 
    public String getState() { 
     return state; 
    } 
    public void setState(String state) { 
     this.state = state; 
    } 
    public String getCountry() { 
     return country; 
    } 
    public void setCountry(String country) { 
     this.country = country; 
    } 
    @Override 
    public int hashCode() { 
     final int prime = 31; 
     int result = 1; 
     result = prime * result + ((city == null) ? 0 : city.hashCode()); 
     result = prime * result + ((country == null) ? 0 : country.hashCode()); 
     result = prime * result + ((locationId == null) ? 0 : locationId.hashCode()); 
     result = prime * result + ((state == null) ? 0 : state.hashCode()); 
     result = prime * result + ((streetName == null) ? 0 : streetName.hashCode()); 
     return result; 
    } 
    @Override 
    public boolean equals(Object obj) { 
     if (this == obj) 
      return true; 
     if (obj == null) 
      return false; 
     if (getClass() != obj.getClass()) 
      return false; 
     AddressInfo other = (AddressInfo) obj; 
     if (city == null) { 
      if (other.city != null) 
       return false; 
     } else if (!city.equals(other.city)) 
      return false; 
     if (country == null) { 
      if (other.country != null) 
       return false; 
     } else if (!country.equals(other.country)) 
      return false; 
     if (locationId == null) { 
      if (other.locationId != null) 
       return false; 
     } else if (!locationId.equals(other.locationId)) 
      return false; 
     if (state == null) { 
      if (other.state != null) 
       return false; 
     } else if (!state.equals(other.state)) 
      return false; 
     if (streetName == null) { 
      if (other.streetName != null) 
       return false; 
     } else if (!streetName.equals(other.streetName)) 
      return false; 
     return true; 
    } 

} 

Answer 1

実際には、最良の方法はセット操作です。古いリストをセットに追加すると、新しいリストを反復することができ、各アイテムについて、作成されたセットに含まれているかどうかを確認します。これにより、ブルートフォースアプローチのO(n^2)とは対照的に、実行時間がO(n*log(n))になります。

Answer 2

私はそうは思わない（注：リストの順序は重要ではないと思う）。たとえば、セットを使用せずにこれを実行する最も速い方法は、O（nlogn）のコストがかかるリストを両方ともソートし、各要素を比較してペアを持たないものを保存することです。 Setの場合、基本的には各要素を繰り返し処理し、2番目の集合でそれを探し、繰り返しがO（n）、検索がO（1）になるようにします。最後に、我々は、O（nlogn）> O（n）のセットがAddressInfoがequalsとhashCodeを適切に実装しており、各リストの項目が一意であると仮定すると、

Answer 3

を獲得し、次の関数は、線形時間でデルタを見つけることができます：

Answer 4

これは、2つのリストの違いを作成するために正常に動作するはずです。

ここでは、セットを作成して、newListのすべての要素を追加しています。 次に、古いリストのいずれかの要素が削除されます。

Set<AddressInfo> findDiffOfTwoList(List<AddressInfo> newList, List<AddressInfo> oldList) { 
    Set<AddressInfo> set = new HashSet<>(); 
    set.addAll(newList); 
    for(AddressInfo address:oldList){ 
     set.remove(address); 
    } 
    return set; 
}