Как сделать так, чтобы алгоритм поиска дубликатов объектов в Java был более эффективным? - PullRequest
Новая
       14

Как сделать так, чтобы алгоритм поиска дубликатов объектов в Java был более эффективным?

0 голосов
/ 01 ноября 2019

Я объявил объект PersonDetails, который имеет следующие три атрибута: 

long id; 
String residence;

Затем у меня есть ArrayList из PersonDetails объектов, которые все заполнены: 

List<PersonDetails> personDetailsList = new ArrayList<>();

Мне нужно перебрать этот список, чтобы найти дубликат PersonDetails, сопоставив их атрибуты residence. 

Id  |   Residence
 1  |     a       
 2  |     b      
 3  |     a       
 4  |     a       
 5  |     b       
 6  |     c     
 7  |     c      
 8  |     d

Код / алгоритм, который я создал для выполнения этого, приведен ниже и используетвложенный for loop, который действительно неэффективен: 

List<PersonDetails> personDetailsList = new ArrayList<>();
for (int i = 0; i <= personDetailsList.size() - 1; i++) {

    long personId = personDetailsList.get(i)
            .getId();
    String personResidence = personDetailsList.get(i)
            .getResidence();

    for (int j = i + 1; j <= personDetailsList.size() - 1; j++) {
        if (personResidence.equals(personDetailsList.get(j).getResidence())) {
            count++;
        }
    }
}

Может ли кто-нибудь предложить более эффективный способ решения этой проблемы? Я пытаюсь придумать лучший способ оптимизировать это, но очень ценю вторую пару глаз. Вложенный цикл был бы адом для большего набора данных.

Ответы [ 3 ]

6 голосов
/ 01 ноября 2019

Вы можете сделать это за одну итерацию по списку PersonDetails, помня, когда вы впервые встретили residence, используя Map<String, PersonDetails>: 

List<PersonDetails> personDetails = new ArrayList<>();
personDetails.add(new PersonDetails(1, "a"));
personDetails.add(new PersonDetails(2, "b"));
personDetails.add(new PersonDetails(3, "a"));
personDetails.add(new PersonDetails(4, "a"));

Map<String, PersonDetails> encountered = new HashMap<>();
for (PersonDetails pd : personDetails) {
  PersonDetails first = encountered.putIfAbsent(pd.residence, pd);
  if (first != null) {
    pd.isDuplicate = first.id;
    first.isDuplicate = first.id; // mark the first encountered as duplicate
  }
}
0 голосов
/ 01 ноября 2019

Ваше последнее изменение добавило важную деталь к вашим требованиям:

Только значения со счетом> 0 должны иметь значение isDuplicate! = null, то есть либо его собственный идентификатор (первое обнаруженное вхождение) или первое найденное вхождение.

Это означает, что ведение карты первых совпадений для каждого найденного residence включает в себя также возможные обновления этих объектов.

В следующем примере это делается классическим способом Java без каких-либо потоков или функций Java 8: 

public static void main(String[] args) {
    List<PersonDetails> personDetails = new ArrayList<>();
    personDetails.add(new PersonDetails(1, "a", null));
    personDetails.add(new PersonDetails(2, "b", null));
    personDetails.add(new PersonDetails(3, "a", null));
    personDetails.add(new PersonDetails(4, "a", null));
    personDetails.add(new PersonDetails(5, "b", null));
    personDetails.add(new PersonDetails(6, "c", null));
    personDetails.add(new PersonDetails(7, "c", null));
    personDetails.add(new PersonDetails(8, "d", null));

    // data structure that holds the PersonDetails with the first occurrence of a residence
    Map<String, PersonDetails> firstIdFoundPerResidence = new HashMap<>();

    for (PersonDetails pd : personDetails) {
        // check if the current PersonDetails was found before
        if (firstIdFoundPerResidence.containsKey(pd.getResidence())) {
            // if yes, take it
            PersonDetails first = firstIdFoundPerResidence.get(pd.getResidence());
            // mark it as duplicate of the first one found
            pd.setIsDuplicate(String.valueOf(first.getId()));
            // and mark the first one itself as a non-unique residence
            // (by setting its own id, for whatever reason)
            first.setIsDuplicate(String.valueOf(first.getId()));
        } else {
            // otherwise just add the PersonDetails as first occurrence
            firstIdFoundPerResidence.put(pd.getResidence(), pd);
        }
    }

    personDetails.forEach(System.out::println);
}

Результат (с подходящим методом toString() в PersonDetails) таков: 

[1, a, 1]
[2, b, 2]
[3, a, 1]
[4, a, 1]
[5, b, 2]
[6, c, 6]
[7, c, 6]
[8, d, null]

, что почти соответствует желаемому результату, который вы опубликовали, и я подозреваю, что вы сделали опечатку для идентификатора 7: должно иметь значение isDuplicate = 6 вместо 7, поскольку это второе появление "c" но там установлен собственный идентификатор.

0 голосов
/ 01 ноября 2019

Вот быстрая оптимизация на основе вашего кода: 

    for(int i = 0; i <= personDetailsList.size()-2 ; i++ ) {

        PersonDetails personDetail = personDetailsList.get(i);
        long personId = personDetail.getId();
        String isDuplicate = personDetail.getIsDuplicate();

        if(isDuplicate == null) {
            bool matchFound = false; 
            String personResidence = personDetail.getResidence();

            for(int j = i+1 ; j <= personDetailsList.size()-1; j++) {
                if(personDetailsList.get(j).getIsDuplicate() == null && personResidence.equals(personDetailsList.get(j).getResidence())) {
                    personDetailsList.get(j).setIsDuplicate(String.valueOf(personId));
                    matchFound = true;
                }
            }

            if(matchFound){
                personDetail.setIsDuplicate(personId);
            }
        }
    }

Этот код пропускает personDetails, которые уже были помечены как дубликаты. Кроме того, в начальном для мы пропускаем последний элемент, потому что он покрыт вторым для.

...