3
\$\begingroup\$

I have two lists of Person objects. I need to compare the lists to determine if items in list1 exist in list2 and vice versa.

This is not a straight equals() scenario as the objects are not the same, but may have identical field values. It is those values that I need to compare.

Currently, I am using Java 8's Streams API to return either a match or null:

import java.util.ArrayList;
import java.util.List;

public class Main {

    public static void main(String[] args) {

        ArrayList<Person> originalPeople = new ArrayList<>();
        ArrayList<Person> newPeople = new ArrayList<>();

        originalPeople.add(new Person("William", "Tyndale"));
        originalPeople.add(new Person("Jonathan", "Edwards"));
        originalPeople.add(new Person("Martin", "Luther"));

        newPeople.add(new Person("Jonathan", "Edwards"));
        newPeople.add(new Person("James", "Tyndale"));
        newPeople.add(new Person("Roger", "Moore"));

        // Create a list of people that no longer exist in the new list
        for (Person original : originalPeople) {
            if (getPersonInList(
                    newPeople, original.getFirstName(), original.getLastName()) == null) {
                System.out.printf("%s %s is not in the new list!%n",
                        original.getFirstName(), original.getLastName());
            }
        }
    }

    private static Person getPersonInList(
            final List<Person> list, final String firstName, final String lastName) {

        return list.stream()
                .filter(t -> t.getFirstName().equalsIgnoreCase(firstName))
                .filter(t -> t.getLastName().equalsIgnoreCase(lastName))
                .findFirst().orElse(null);
    }
}

class Person {

    private final String firstName;
    private final String lastName;

    Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }
}

In my real-world application, however, both lists have over 30,000 items and this is very time-consuming.

Is there a better way to perform this comparison? I would want this to work both ways as well, so if there are items in newPeople that were not in originalPeople, I would want that list as well.

\$\endgroup\$
6
  • \$\begingroup\$ Did you try this? stackoverflow.com/questions/919387/… \$\endgroup\$
    – Ankit Soni
    Jul 21, 2018 at 7:18
  • \$\begingroup\$ No, because that does not in any way address my original question. I am not trying to simple compare the 2 lists and locate/remove identical objects. \$\endgroup\$
    – Zephyr
    Jul 21, 2018 at 7:20
  • \$\begingroup\$ Is this an MCVE? Because that's SO territory, at Code Review we need to see the real deal or we'll come with suggestions not applicable to your code. Please take a look at the help center. \$\endgroup\$
    – Mast
    Jul 21, 2018 at 11:37
  • 2
    \$\begingroup\$ That's not what I meant. Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site. Please take a look at the help center. \$\endgroup\$
    – Mast
    Jul 21, 2018 at 13:47
  • 1
    \$\begingroup\$ In your example code, the person class consists exactly of the two fields you compare and therefore this is a perfect example for equals() with a generic standard implementation. Thus, your question contradicts your code. As Mast already told you: lacking concrete context. \$\endgroup\$
    – mtj
    Jul 22, 2018 at 5:35

4 Answers 4

3
\$\begingroup\$

The approach, algorithm

To find if an object exists in a list, you need to perform a linear search, potentially visiting every single element, in \$O(n)\$ time. More efficient data structures exist:

  • Use an ordered data structure: if the values are sorted, then you can find if an element exists using binary search, in \$O(\log n)\$ time.

  • Use a hashset: you can find if an element is in the set in constant time, \$O(1)\$

To be to search efficiently, use a hashset instead of a list. However, to be able to use a hashset efficiently, it is required that the objects you put in it have appropriate implementation of hashCode and equals methods.

See the official tutorial on the Object class, especially the sections on the equals and hashCode methods. Note that IDEs like IntelliJ and Eclipse can generate these methods for you easily (they are boring to write by hand, and usually there's little reason to do so).

With correct implementation of the equals and hashCode methods, for example as in the other answer by @Teddy, your main program could be reduced to this:

public static void main(String[] args) {

    Set<Person> originalPeople = new HashSet<>();
    Set<Person> newPeople = new HashSet<>();

    originalPeople.add(new Person("William", "Tyndale"));
    originalPeople.add(new Person("Jonathan", "Edwards"));
    originalPeople.add(new Person("Martin", "Luther"));

    newPeople.add(new Person("Jonathan", "Edwards"));
    newPeople.add(new Person("James", "Tyndale"));
    newPeople.add(new Person("Roger", "Moore"));

    for (Person original : originalPeople) {
        if (!newPeople.contains(original)) {
            System.out.printf("%s %s is not in the new list!%n",
                    original.getFirstName(), original.getLastName());
        }
    }
}
\$\endgroup\$
3
\$\begingroup\$

There are certain reasons I would not prefer your approach. These are:

1) There are multiple method calls which reduces the readability.

2) You are using filter twice which decreases the performances. You could do it inside the same filter like I've shown below

3) With this approach you don't have a consolidated List which contains common elements. For that you need another else condition which increases the cyclomatic complexity.

4) A null check which could produce NPE if not handled carefully as you are using findFirst() which returns Optional (Although null can be replaced with default new Person("","") object which is again not recommended).

5) Finally don't use ArrayList<Person> originalPeople = new ArrayList<>();; rather declare as List, to follow programming to interface.

Rather I would use below approach:

private static List<Person> getPersonInList(
            final List<Person> newPeople, List<Person> originalPeople) {
        List<Person> list = new ArrayList<>();

        newPeople.forEach(p ->
                originalPeople.stream()
                              .filter(p1 -> p.getFirstName().equals(p1.getFirstName()) && 
                                      p.getLastName().equals(p1.getLastName()))
                              .forEach(list::add));
        return list;
    }
\$\endgroup\$
2
  • \$\begingroup\$ This is still double iteration right? O(n*n)? \$\endgroup\$
    – Teddy
    Jul 24, 2018 at 18:01
  • \$\begingroup\$ how come this answer has more votes? \$\endgroup\$
    – jbakirov
    Apr 3, 2019 at 17:52
1
\$\begingroup\$

Lists are linear in terms of performance. You are iterating original list, which cannot be avoided. But, for each item in original you are iterating the new list looking for a match. This is bad for performance.

You should just add all the new data to a HashSet. Then iterate the original list and check if the HashSet contains that pair.

To use a HashSet, the main thing is the hash function. If the person class can be made to have a hashCode only relating the firstName and the lastName, then you can go with that option.

If not just use a Pair. Its a standard tuple, and one should be available in some of the collections already in your project classpath.

public class PersonsMain {
    public static void main(String[] args) {
        ArrayList<Person> originalPeople = new ArrayList<>();
        ArrayList<Person> newPeople = new ArrayList<>();

        originalPeople.add(new Person("William", "Tyndale", 30));
        originalPeople.add(new Person("Jonathan", "Edwards", 31));
        originalPeople.add(new Person("Martin", "Luther", 32));

        newPeople.add(new Person("Jonathan", "Edwards", 33));
        newPeople.add(new Person("James", "Tyndale", 34));
        newPeople.add(new Person("Roger", "Moore", 35));

        //Prepare
        HashSet<Person> newGuys = new HashSet<>();
        for(Person newPerson:newPeople) {
            newGuys.add(newPerson);
        }

        //Results
        for(Person originalPerson:originalPeople) {
            if(!newGuys.contains(originalPerson)) {
                System.out.println("This person is not in the new list: " 
                        + originalPerson.getFirstName() + " " 
                        + originalPerson.getLastName() );
            }
        }
    }

    static class Person {

        private final String firstName;
        private final String lastName;
        //Extra field age to remind you that it should not be included in hashCode and equals
        private final int age;

        Person(String firstName, String lastName, int age) {
            this.firstName = firstName;
            this.lastName = lastName;
            this.age = age;
        }

        String getFirstName() {
            return firstName;
        }

        public String getLastName() {
            return lastName;
        }


        public int getAge() {
            return age;
        }

        @Override
        public int hashCode() {
            //Auto-generated by Eclipse.
            //Important that this hash code use only the name fields.

            final int prime = 31;
            int result = 1;
            result = prime * result + ((firstName == null) ? 0 : firstName.hashCode());
            result = prime * result + ((lastName == null) ? 0 : lastName.hashCode());
            return result;
        }

        @Override
        public boolean equals(Object obj) {
            //Auto-generated by Eclipse.
            //Important that this hash code use only the name fields.

            if (this == obj)
                return true;
            if (obj == null)
                return false;
            if (getClass() != obj.getClass())
                return false;
            Person other = (Person) obj;
            if (firstName == null) {
                if (other.firstName != null)
                    return false;
            } else if (!firstName.equals(other.firstName))
                return false;
            if (lastName == null) {
                if (other.lastName != null)
                    return false;
            } else if (!lastName.equals(other.lastName))
                return false;
            return true;
        }

    }
}
\$\endgroup\$
0
0
\$\begingroup\$

If those lists are not immutables then i would perfer to sort the lists and then traverse. Using stream you will always end up with complexicity of

list1.size*list2.size

But if you can sort then it can be done in

sort_complexicity(this should be list_size*log(list_size)) + list_size

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.