сравнить и равно в PriorityQueues - PullRequest
Новая
       29

сравнить и равно в PriorityQueues

6 голосов
/ 25 июня 2011

Я немного запутался со всем: «Если порядок, наложенный символом c на S, несовместим с равенством, отсортированный набор (или отсортированная карта) будет вести себя странно».предупреждения в Javadoc.Я даже не уверен, что PriorityQueue - это то, что мне нужно ...

Моя ситуация такова: у меня есть класс Event с целой отметкой времени и некоторые другие поля.Я ищу структуру данных, в которую я могу вставить эти события и которая сортирует события по отметке времени.Разные события могут иметь одну и ту же временную метку, поэтому, если я правильно понимаю, сравнение и равные будут несовместимыми.

Мой первый подход состоял в том, чтобы позволить Event реализовать Comparable и обеспечить сравнение, например: public int compareTo (Event e) {return this.timestamp - e.getTimestamp ();}

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

Заранее благодарен за помощь:)

Редактировать:
Я простохотите, чтобы события сортировались по отметке времени.Вполне может быть, что два разных события имеют одну и ту же метку времени.Так что CompareTo вернет 0, потому что они имеют одинаковую временную метку и равны для сортировки.Но equals () не вернет true, потому что это разные события.
Я не уверен, что PriorityQueue - это то, что нужно использовать.Я посмотрел на SortedSet, но у него были те же предупреждения о непротиворечивости сравнений и равных.
Может быть, я занимаюсь этим с неправильной точки зрения, я не знаю ...

Ответы [ 3 ]

5 голосов
/ 25 июня 2011

Различные события могут иметь одну и ту же метку времени

и сортировать события по метке времени

Это последнее требование несколько неясно.Должен ли итератор коллекции возвращать экземпляры в отсортированном порядке?Или должна ли коллекция, если вы poll() в цикле, вернуть свое прежнее содержимое в отсортированном порядке?

iterator() возвращает элементы в порядке

Это не относится к PriorityQueue.Вы можете использовать SortedSet, но для этого требуется, чтобы порядок сортировки был согласован с равенством, чего, как вы правильно заметили, вы не можете достичь.Насколько я знаю, в JDK нет Collection, который бы сохранял свои элементы в отсортированном порядке для порядка сортировки, который считает некоторые элементы равными.Однако вы можете использовать массив или ArrayList и отсортировать его вручную после изменений, используя Arrays.sort или Collection.sort.Если коллекция меняется редко, такой подход я бы выбрал.Если оно часто меняется, вам придется выйти за рамки JDK или реализовать структуру данных самостоятельно.

poll() возвращает элементы в отсортированном порядке

Для этого подходит очередь с приоритетами.A PriorityQueue не требует, чтобы Comparator (или реализация Comparable) соответствовали равным;его JavaDoc четко пишет:

head этой очереди является наименьшим элементом относительно указанного порядка.Если несколько элементов связаны для наименьшего значения, заголовок является одним из этих элементов - связи нарушаются произвольно.

Более того, реализация PriorityQueue в JDK 6 использует equals только для реализацииindexOf(E), contains(Object) и remove(Object), которые никоим образом не используют компаратор.Так что на самом деле не существует способа, которым согласованность с равными могла бы иметь значение для этого Collection.

Comparable vs. Comparator

Обратите внимание, что не имеет значения,реализовать Comparable или Comparator, если речь идет о соответствии с равными.Для SortedSet, либо должен соответствовать равным, для PriorityQueue, Collection.sort или Arrays.sort, ни то, ни другое не должно быть.

TreeSet и согласованность с equals

Поднято из комментариев:

TreeSet является SortedSet и явно заявляет, что полагается только на сравнение / сравнение.В нем четко сказано: «Поведение набора четко определено, даже если его порядок не соответствует уравнениям; он просто не соблюдает общий контракт интерфейса Set».

Если вы цитируете,Пожалуйста, укажите все соответствующие части.Полный абзац гласит:

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

Так что да, он четко определен, но не выполняет то, что требует вопрос: если вы передадите TreeSet.addEvent с той же отметкой времени, что и другая Event в наборе, новый Event будет считаться дубликатом и не будет добавлен, даже если Event s не equal.Вопрос задается о сортировке Collection;что не должно исключать Events, которые дублируют ключ сортировки, не так ли?

4 голосов
/ 25 июня 2011

Если порядок, наложенный c на S, не совпадает с равенством, отсортированный набор (или отсортированная карта) будет вести себя странно.

Это означает, что если и только если e1.equals(e2), то e1.compareTo(e2) == 0.

А если и только если !e1.equals(e2), то e1.compareTo(e2) != 0.

Это то, что вы должны сделать, чтобы согласовать оба метода.

Таким образом, при реализации сравнения вы также должны переопределить equals () следующим образом: 

@Override
public boolean equals(Event e) {
    return this.timestamp.equals(e.timestamp);
}

Примечание: я не знаю тип данных отметки времени, но если это примитивный тип, используйте == вместо equals() для переопределенного метода.

0 голосов
/ 25 июня 2011

Когда вы реализуете Comparable, вы также должны переопределить equals(Object), потому что compareTo должен возвращать ноль только тогда и только тогда, когда equals возвращает true.

compareTo (T) долженвозвращать ноль только тогда и только тогда, когда equals (Object) возвращает true.

И это еще не все.Из-за другого контракта вы должны / должны переопределить hashCode() при переопределении equals.

Равные объекты должны иметь одинаковые хеш-коды. 

public class Event implements Comparable<Event> {

    private long timestamp;

    public long getTimestamp() {
        return this.timestamp;
    }

    @Override
    public int compareTo(Event o) {
        return (this.timestamp < o.timestamp ? -1
                : (this.timestamp == o.timestamp ? 0 : 1));
    }

    @Override
    public int hashCode() {
        return (int) (this.timestamp ^ (this.timestamp >>> 32));
    }

    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Event) {
            return this.timestamp == ((Event) obj).timestamp;
        }

        return false;
    }

}

compareToРеализация *, 1021 * и hashCode была взята из реализации, которую вы можете увидеть в java.lang.Long.Вы также можете сгенерировать эти методы с помощью IDE, например Eclipse.

Если вы хотите иметь CompareTo, значение которого равно 0, когда equals должен возвращать false (как указано в другом комментарии), тогда вы должны реализовать Comparator вместореализация Comparable. 

public class EventComparator implements Comparator<Event>, Serializable {

    private static final long serialVersionUID = 1L;

    @Override
    public int compare(Event o1, Event o2) {
        return (o1.getTimestamp() < o2.getTimestamp() ? -1
                : (o1.getTimestamp() == o2.getTimestamp() ? 0 : 1));
    }

}
...