优化两个列表的比较和合并

Question

我有两个Bill对象列表，其中有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);

但我认为这不是最好的方法。

也许你有什么想法，如何优化这个算法？

p.s.：java 7

Answer 1

由于比尔的getDate()必须是唯一的，我建议使用一个映射，它需要一个唯一的键，并且对密钥具有O(1)访问权。

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

您也可以使用循环

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

这将取代所有具有相同Date的账单。putAll通常是一个O(N)操作，其中N是newBills的大小

您可以从这样的列表构建这些地图。

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

Answer 2

如果Bill有'n‘元素，而oldBill有'm'，则您的算法采用n * m迭代。我是O(n^2)。通过对旧票据(O(n*logn) )进行排序，然后实现对票据(O(logn))中每个元素的二进制搜索，可以对其进行改进。因此，在这种情况下，所花费的总时间将是O(nlog(n))。

Answer 3

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

    }

我不太清楚您在使用“新账单”做什么，但是这将将账单添加到oldBills中，而不会复制记录，而不需要强制执行，并且具有^2算法。