same - string distinct java




필드를 무시한 목록에서 중복 찾기 (3)

저는 Person of List 를 가지고 있고 중복 된 엔트리를 찾고 id 제외한 모든 필드를 포함하고 싶습니다. 그래서 equals() -method (그리고 결과적으로 List.contains() )를 사용한다. 왜냐하면 그들은 id 를 고려하기 때문이다.

public class Person {
    private String firstname, lastname;
    private int age;
    private long id;
}

id 필드를 무시하도록 equals()hashCode() -method를 수정하는 것은 코드의 다른 부분이 이에 의존하기 때문에 옵션이 아닙니다.

id 필드를 무시하려면 중복을 분류하는 가장 효율적인 Java의 방법은 무엇입니까?


Comparator<Person> 을 작성하여 자연어 순서를 구현 한 다음 이진 검색 기반 중복 제거를 사용하십시오. TreeSet 은 당신에게이 기능을 제공합니다.

Comparator<T>.compare(a, b) 일반적인 반 대칭성, 전이 성, 일관성 및 반사 요구 사항을 충족해야하며 그렇지 않으면 이진 검색 순서가 실패합니다. 또한 null을 인식하도록해야합니다 (예 : 하나의 firstname 필드, other 또는 both가 null 인 경우).

Person 클래스의 간단한 자연 비교 자 (natural-key comparator)는 다음과 같습니다 (각 필드에 접근자를 가지고있는 경우 표시되지 않은 것처럼 정적 멤버 클래스입니다).

public class Person {
    public static class NkComparator implements Comparator<Person>
    {
        public int compare(Person p1, Person p2)
        {
            if (p1 == null || p2 == null) throw new NullPointerException();
            if (p1 == p2) return 0;
            int i = nullSafeCompareTo(p1.firstname, p2.firstname);
            if (i != 0) return i;
            i = nullSafeCompareTo(p1.lastname, p2.lastname);
            if (i != 0) return i;
            return p1.age - p2.age;
        }
        private static int nullSafeCompareTo(String s1, String s2)
        {
            return (s1 == null)
                    ? (s2 == null) ? 0 : -1
                    : (s2 == null) ? 1 : s1.compareTo(s2);
        }
    }
    private String firstname, lastname;
    private int age;
    private long id;
}

그런 다음이를 사용하여 고유 한 목록을 생성 할 수 있습니다. 요소가 세트에 존재하지 않은 경우에만 true 를 리턴하는 add 메소드를 사용하십시오.

List<Person> newList = new ArrayList<Person>();
TreeSet<Person> nkIndex = new TreeSet<Person>(new Person.NkComparator());
for (Person p : originalList)
    if (nkIndex.add(p)) newList.add(p); // to generate a unique list

또는이 행의 최종 행을 스왑하여 대신 출력을 출력하십시오

    if (nkIndex.add(p)) newList.add(p); 

당신이 무엇을 하든지 열거하는 동안 원래 목록에서 remove 를 사용하지 마십시오. 따라서이 방법이 고유 한 요소를 새 목록에 추가합니다.

고유 목록에 관심이 있고 가능한 한 적은 수의 줄만 사용하려면 :

TreeSet<Person> set = new TreeSet<Person>(new Person.NkComparator());
set.addAll(originalList);
List<Person> newList = new ArrayList<Person>(set);

<K,V> 쌍을 사용하여 Java HashMap 을 사용할 수 있습니다. Map<K,V> map = new HashMap<K,V>() 입니다. 또한, 어떤 형태의 Comparator 구현도 함께 제공됩니다. containsKey 또는 containsValue 메서드를 사용하여 이미 무언가를 찾았 으면 (즉, 복제본을 추가하려고하면 원래 목록에 유지하고 그렇지 않으면 팝 아웃합니다.)이 방법으로 목록이 완성됩니다. 원래 목록에 중복 된 요소 TreeSet <,>이 또 다른 옵션이지만 아직 사용하지 않았으므로 조언을 제공 할 수 없습니다.


@ LuiggiMendoza 가 의견에서 제안한대로 :

두 개의 Person 객체를 비교하여 해당 ID를 무시하고 동일한지 Comparator 하는 사용자 정의 Comparator 클래스를 만들 수 있습니다.

class PersonComparator implements Comparator<Person> {

    // wraps the compareTo method to compare two Strings but also accounts for NPE
    int compareStrings(String a, String b) {
        if(a == b) {           // both strings are the same string or are null
          return 0;
        } else if(a == null) { // first string is null, result is negative
            return -1;
        } else if(b == null){  // second string is null, result is positive
            return 1;
        } else {               // no strings are null, return the result of compareTo
            return a.compareTo(b);
        }
    }

    @Override
    public int compare(Person p1, Person p2) {

        // comparisons on Person objects themselves
        if(p1 == p2) {                 // Person 1 and Person 2 are the same Person object
            return 0;
        }
        if(p1 == null && p2 != null) { // Person 1 is null and Person 2 is not, result is negative
            return -1;
        }
        if(p1 != null && p2 == null) { // Person 1 is not null and Person 2 is, result is positive
            return 1;
        }

        int result = 0;

        // comparisons on the attributes of the Persons objects
        result = compareStrings(p1.firstname, p2.firstname);
        if(result != 0) {   // Persons differ in first names, we can return the result
            return result;
        }
        result = compareStrings(p1.lastname, p2.lastname);
        if(result != 0) {  // Persons differ in last names, we can return the result
            return result;
        }

        return Integer.compare(p1.age, p2.age); // if both first name and last names are equal, the comparison difference is in their age
    }
}

이제이 사용자 정의 Comparator 와 함께 TreeSet 구조를 사용할 수 있습니다. 예를 들어 중복 값을 제거하는 간단한 메서드를 만들 수 있습니다.

List<Person> getListWithoutDups(List<Person> list) {
    List<Person> newList = new ArrayList<Person>();
    TreeSet<Person> set = new TreeSet<Person>(new PersonComparator()); // use custom Comparator here

    // foreach Person in the list
    for(Person person : list) {
        // if the person isn't already in the set (meaning it's not a duplicate)
        // add it to the set and the new list
        if(!set.contains(person)) {
            set.add(person);
            newList.add(person);
        }
        // otherwise it's a duplicate so we don't do anything
    }

    return newList;
}

문서가 말한 것처럼 , TreeSetcontains 연산은 "보증 된 log (n) 시간 비용"을 제공 합니다.

위에서 제안한 방법은 각 목록 요소에 대해 contains 연산을 수행하기 때문에 O(n*log(n)) 시간이 걸리지 만 새 목록과 TreeSet 을 만들기 위해 O(n) 공간을 사용합니다.

목록이 꽤 큰 경우 (공간은 매우 중요 함) 처리 속도는 문제가 아니므로 각 비 중복 항목을 목록에 추가하는 대신 발견 된 각 중복 항목을 제거 할 수 있습니다.

 List<Person> getListWithoutDups(List<Person> list) {
    TreeSet<Person> set = new TreeSet<Person>(new PersonComparator()); // use custom Comparator here
    Person person;
    // for every Person in the list
    for(int i = 0; i < list.size(); i++) {
        person = list.get(i);
        // if the person is already in the set (meaning it is a duplicate)
        // remove it from the list
        if(set.contains(person) { 
            list.remove(i);
            i--; // make sure to accommodate for the list shifting after removal
        } 
        // otherwise add it to the set of non-duplicates
        else {
            set.add(person);
        }
    }
    return list;
}

목록에 대한 각 remove 작업은 요소가 삭제 될 때마다 목록이 이동하기 때문에 O(n) 시간이 걸리고 각 작업에 log(n) 시간이 소요 log(n) 방법은 O(n^2 log(n)) .

그러나 두 번째 목록이 아닌 TreeSet 만 생성하기 때문에 공간 복잡성이 절반으로 줄어 듭니다.





duplicate-removal