Оптимизация сравнения и слияния двух списков

У меня есть два списка объектов 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);

, но я думаю, что это не самый лучший способ.

Может быть, у вас есть идеи, как оптимизировать этот алгоритм?

пс: Java 7

источник

2016-03-22 Kirill

Что делает счет уникальным? –

дата может быть представлена объектом даты, что означает, что даты могут быть разными для миллисекунд ... это нормально для вас –

Если вы пытаетесь посмотреть на столкновений в календарную дату, используйте объекты ['LocalDate'] (https://docs.oracle.com/javase/8/docs/api/java/time/LocalDate.html) класс java.time framework, встроенный в Java 8 и более поздние версии, а не старый 'java.util.Date' класс. Если вы сравниваете по календарному месяцу, как упоминалось, используйте класс ['YearMonth'] (https://docs.oracle.com/javase/8/docs/api/java/time/YearMonth.html). –

Поскольку 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));

источник

2016-03-22 15:50:36

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

    }

Я не совсем уверен, что вы делаете с «новые счета», но это добавит счета в oldBills без дублирования записи без перебирая его и имея^2.

источник

2016-03-22 15:49:27

Я думаю, что это то же самое, что и моя версия, потому что внутренний цикл - это факт, что функция 'содержит' – Kirill

Твоя не то же самое. Вы повторяете оба цикла (n^2), тогда как это проходит через один, заставляя компьютер выполнять меньше операций, но получая тот же результат. –

Вы можете оптимизировать его, используя HashMap. Для этого вам нужно определить для своих объектов Билл уникальный ключ. Например, дата и который был оплачено в

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) 
    } 
}

источник

2016-03-22 15:51:10

Вместо того чтобы идти через петлю, достаточно использовать java.util.ArrayList.contains (Object о), которые возвращают логическое значение.

источник

2016-03-22 15:51:42 codex

Если у Билла есть 'n' элементы, а oldBill имеет 'm', ваш алгоритм принимает n * m итерацию. это O(n^2). Его можно улучшить, сортируя oldbill (O(n*logn)), а затем реализуя двоичный поиск для каждого элемента счета (O(logn)). Таким образом, в этом случае общее время будет O(nlog(n)).

источник

2016-03-22 15:52:32 learner

isnt n * logn + logn эквивалентно n * logn? –

@huseyintugrulbuyukisik Спасибо, что указали это. Это была опечатка. – learner

Оптимизация сравнения и слияния двух списков

ответ

Смежные вопросы