TreeSet Comparator не удалось удалить дубликаты в некоторых случаях? - PullRequest
Новая
       67

TreeSet Comparator не удалось удалить дубликаты в некоторых случаях?

0 голосов
/ 19 ноября 2018

У меня есть следующий компаратор для моего TreeSet: 

public class Obj {
    public int id;
    public String value;
    public Obj(int id, String value) {
        this.id = id;
        this.value = value;
    }
    public String toString() {
        return "(" + id + value + ")";
    }
}

Obj obja = new Obj(1, "a");
Obj objb = new Obj(1, "b");
Obj objc = new Obj(2, "c");
Obj objd = new Obj(2, "a");
Set<Obj> set = new TreeSet<>((a, b) -> {
    System.out.println("Comparing " + a + " and " + b);
    int result = a.value.compareTo(b.value);
    if (a.id == b.id) {
        return 0;
    }
    return result == 0 ? Integer.compare(a.id, b.id) : result;
});
set.addAll(Arrays.asList(obja, objb, objc, objd));
System.out.println(set);

Распечатывается [(1a), (2c)], что позволило удалить дубликаты.

Но когда я изменил последний Integer.compare на Integer.compare(b.id, a.id) (то есть переключил положения a и b), он распечатывает [(2a), (1a), (2c)]. Ясно, что один и тот же идентификатор 2 появился дважды.

Как исправить компаратор, чтобы всегда удалять дубликаты на основе идентификаторов и сортировать упорядоченный набор по значению (возрастанию), а затем идентификатору (убыванию)?

1 Ответ

0 голосов
/ 19 ноября 2018

Вы спрашиваете:
Как исправить компаратор, чтобы всегда удалять дубликаты на основе идентификаторов и сортировать упорядоченный набор по значению (возрастанию), а затем идентификатору (убыванию)?

Требуется, чтобы компаратор

  1. удалял дубликаты на основе Obj.id
  2. сортировки набора по Obj.alue и Obj.id

Требование 1) приводит к 

Function<Obj, Integer> byId = o -> o.id;
Set<Obj> setById = new TreeSet<>(Comparator.comparing(byId));

Требование 2) приводит к 

Function<Obj, String> byValue = o -> o.value;
Comparator<Obj> sortingComparator =  Comparator.comparing(byValue).thenComparing(Comparator.comparing(byId).reversed());
Set<Obj> setByValueAndId = new TreeSet<>(sortingComparator);

Давайте посмотрим на JavaDoc из TreeSet.В нем говорится:

Обратите внимание, что порядок, поддерживаемый набором [...], должен соответствовать equals, если он должен правильно реализовывать интерфейс Set.Это так, потому что интерфейс Set определен в терминах операции equals, но экземпляр TreeSet выполняет все сравнения элементов, используя свой метод compareTo (или сравнение), поэтому два элемента, которые считаются равными этимМетод, с точки зрения набора, равен.

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

Насколькокак я вижу, нет способа определить Comparator, который удовлетворяет обоим требованиям.Поскольку TreeSet на первом месте, требование Set 1) должно соответствовать.Для выполнения требования 2) вы можете создать второй TreeSet: 

Set<Obj> setByValueAndId = new TreeSet<>(sortingComparator);
setByValueAndId.addAll(setById);

. Или, если вам не нужен сам набор, но для обработки элементов в нужном порядке, вы можете использовать Stream:

Consumer<Obj> consumer = <your consumer>;
setById.stream().sorted(sortingComparator).forEach(consumer);

Кстати:
Хотя можно отсортировать элементы Stream в соответствии с заданным Comparator, не существует метода distinct, который принимает Comparator для удаления дубликатов в соответствии сit.

EDIT:
У вас есть две разные задачи: 1. удаление дубликатов, 2. сортировка.Один Comparator не может решить обе задачи.Итак, какие есть альтернативы?

Вы можете переопределить equals и hashCode на Obj.Тогда для удаления дубликатов можно использовать HashSet или Stream.
Для сортировки вам все равно понадобится Comparator (как показано выше).Реализация Comparable только для сортировки привела бы к упорядочению, которое "не соответствует" в соответствии с Comparable JavaDoc .

Поскольку Stream может решать обе задачи, онобыл бы мой выбор.Сначала мы переопределяем hashCode и equals, чтобы идентифицировать дубликаты по id: 

public int hashCode() {
    return Integer.hashCode(id);
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Obj other = (Obj) obj;
    if (id != other.id)
        return false;
    return true;
}

Теперь мы можем использовать Stream: 

// instantiating one additional Obj and reusing those from the question
Obj obj3a = new Obj(3, "a");

// reusing sortingComparator from the code above
Set<Obj> set = Stream.of(obja, objb, objc, objd, obj3a)
        .distinct()
        .sorted(sortingComparator)
        .collect(Collectors.toCollection(LinkedHashSet::new));

System.out.println(set); // [(3a), (1a), (2c)]

Возвращенные LinkedHashSetимеет семантику Set, но также сохранил порядок sortingComparator.

РЕДАКТИРОВАТЬ (отвечая на вопросы из комментариев)

Q: Почему это не такне закончите работу правильно?
Убедитесь сами.Измените последнюю строку вашего Comparator следующим образом 

int r = result == 0 ? Integer.compare(a.id, b.id) : result;
System.out.println(String.format("a: %s / b: %s / result: %s -> %s", a.id, b.id, result, r));
return r;

Запустите код один раз, а затем переключите операнды Integer.compare.Переключение приводит к другому пути сравнения.Разница заключается в сравнении (2a) и (1a).

При первом запуске (2a) больше (1a), поэтому оно сравнивается со следующей записью (2c).Это приводит к равенству - дубликат найден.

Во втором запуске (2a) меньше, чем (1a).Таким образом, (2a) будет сравниваться как следующий с предыдущей записью.Но (1a) уже самая маленькая запись, и предыдущей нет.Следовательно, для (2a) дубликат не найден и он добавлен в набор.

Q: Вы сказали, что один компаратор не может выполнить две задачи, мои 1-е компараторы фактически выполнили обе задачи правильно.
Да - но только для данного примера.Добавьте Obj obj3a к набору, как я сделал, и запустите ваш код.Возвращенный отсортированный набор: 

[(1a), (3a), (2c)]

Это нарушает ваше требование сортировки для равных value s по убыванию id.Теперь он поднимается на id.Запустите мой код, и он вернет правильный порядок, как показано выше.

Борясь с Comparator некоторое время назад, я получил следующий комментарий: «... это отличное упражнение, демонстрирующее, насколько сложноручные реализации компаратора могут быть ... "( source )

...