2つのリストの比較とマージを最適化

Question

Billの2つのリストがあり、請求書を作成した月を表すdateフィールドがあります。 billsリストからoldBillsにオブジェクトを追加する必要があります。 oldBillsリストに同じデータの請求書がない場合は、請求書を追加する必要があります。

私はそれをこのように実装：

outer: 
for (Bill bill : bills) { 
    Date billDate = bill.getDate(); 
    for (Bill bill1 : oldBills) { 
    Date bill1Date = bill1.getDate(); 
    if (Objects.equals(billDate, bill1Date)) { 
     continue outer; 
    } 
    } 
    newBills.add(bill); 
} 
oldBills.addAll(newBills); 

を私はこれが最善の方法ではないと思われます。

このアルゴリズムを最適化する方法はありますか？

PS：Javaの7

Answer 1

ビルのgetDate（）はユニークでなければならないので、ユニークなキーが必要なマップを使用し、キーにはO（1）アクセス権があります。

Map<Date, Bill> oldBills = new HashMap<>(); 
oldBills.putAll(newBills); 

また、これは同じDateを持っている全ての紙幣を交換します

for(Bill bill : newBills) 
    oldBills.putIfAbsent(bill.getDate(), bill); 

ループを使用することができます。 putAllは、通常O(N)操作です。ここでNはサイズです。newBills

このようなリストからこれらのマップを作成できます。

// requires Java 8. 
Map<Date, Bill> billByDate = bills.stream().collect(Collectors.groupingBy(Bill::getDate)); 

Answer 2

for(Bill bill:bills) 
    { 
     if(!oldBills.contains(bill)) 
     { 
      oldBills.add(bill); 
     } 

    } 

私はあなたが「新しい法案」でやっているが、これはそれを強制的にブルートせずにレコードを複製しなくても、oldBillsに手形を追加するかを正確にわからないんだけど^ 2アルゴリズム。

Answer 3

ハッシュマップを使用して最適化することができます。このためには、Billオブジェクトに対して一意のキーを定義する必要があります。例えば、日付、誰のために代わりにループを通過するの

public class Bill{ 
     ... 
     public String getKey(){ 
      return date.toString()+payedTo; 
     } 
} 

HahsMap<String,Bill> oldBills = ... 
for (Bill bill : bills){ 

    if (! oldBills.containsKey(bill.getKey()){ 
      oldBill.put(bill.getKey(),bill) 
    } 
} 

Answer 4

に払った、それはboolean型を返すjava.util.ArrayList.contains（オブジェクトo）を使用するのに十分です。

Answer 5

Billに「n」要素があり、oldBillに「m」がある場合、アルゴリズムにはn * m回の反復が必要です。それはO(n^2)です。 oldbill (O(n*logn))をソートしてから、請求書(O(logn))の各要素のバイナリ検索を実装することで改善できます。したがって、この場合、合計時間はO(nlog(n))となります。