Можно ли иметь компаратор Java, в котором порядок может динамически меняться?

Question

У меня есть набор значений с метками времени, которые я хотел бы поместить в отсортированный набор.

public class TimedValue {
    public Date time;
    public double value;

    public TimedValue(Date time, double value) {
        this.time = time;
        this.value = value;
    }
}

Бизнес-логика для сортировки этого набора говорит, что значения должны быть упорядочены в порядке убывания значения, , если только оно не более чем на 7 дней старше, чем новейшее значение .

Итак, в качестве теста я придумал следующий код ...

DateFormat dateFormatter = new SimpleDateFormat("MM/dd/yyyy");
TreeSet<TimedValue> mySet = new TreeSet<TimedValue>(new DateAwareComparator());
mySet.add(new TimedValue(dateFormatter.parse("01/01/2009"), 4.0 )); // too old
mySet.add(new TimedValue(dateFormatter.parse("01/03/2009"), 3.0)); // Most relevant
mySet.add(new TimedValue(dateFormatter.parse("01/09/2009"), 2.0));

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

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

Но хотя я это вижу, я не уверен, что верю в это.

Будет ли отсортированная коллекция переупорядочивать весь набор при добавлении каждого элемента? Есть ли какие-либо ошибки в использовании отсортированной коллекции таким образом (т.е. производительность)? Было бы лучше вручную отсортировать список после того, как все значения были добавлены (я предполагаю, что это будет)?

Последующий: Как и подозревали многие (и даже я в определенной степени), отсортированная коллекция не поддерживает такой способ «динамического переупорядочения». Я считаю, что мой первоначальный тест "работал" совершенно случайно. По мере того, как я добавлял больше элементов в набор, «порядок» разрушался довольно быстро. Спасибо за все отличные ответы, я реорганизовал свой код, чтобы использовать подходы, предложенные многими из вас.

Answer 1

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

Я предлагаю вам сделать что-то вроде следующего:

• Соберите ваши данные в неупорядоченном наборе (или списке)
• Найти новейшее значение
• Создайте компаратор на основе этого значения , так что все сравнения, использующие этот компаратор, будут фиксированными (т. Е. Он никогда не вернет другой результат, основанный на тех же входных значениях; сам компаратор является неизменным, хотя и зависит от значения, изначально предоставленного в конструкторе)
• Создайте отсортированную коллекцию с использованием этого компаратора (любым подходящим способом в зависимости от того, что вы хотите с ним делать)

Answer 2

Я бы посоветовал против этого по нескольким причинам:

1. Поскольку это в основном красно-черное дерево за сценой (которое не обязательно нужно восстанавливать с нуля при каждой вставке), вы можете легко получить значения в неправильной части дерева (аннулировать большую часть TreeSet API).
2. Поведение не определено в спецификации, поэтому может измениться позже, даже если оно работает сейчас.
3. В будущем, когда что-то будет странно не так в чем-то, касающемся этого кода, вы потратите время, подозревая, что в этом причина.

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

Answer 3

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

Внимательно прочитайте договор Comparator.compare(). Ваш компаратор удовлетворяет этим ограничениям?

Чтобы уточнить, если ваш компаратор возвращает, что два значения не равны, когда вы вызываете его один раз, но потом возвращает, что эти два значения равны, потому что более позднее значение было добавлено в набор и изменило выходные данные компаратора, определение «Set» (без дубликатов) отменяется.

Совет Джона Скита в его ответе является отличным советом и позволит избежать необходимости беспокоиться о подобных проблемах. Действительно, если ваш Comparator не возвращает значения, соответствующие equals(), то у вас могут быть большие проблемы. Будет ли отсортированный набор пересортироваться каждый раз, когда вы добавляете что-то, я бы не зависел, но худшее, что может произойти из-за изменения order , это то, что ваш набор не останется отсортированным.

Answer 4

Нет, это не сработает.

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

При хранении ключей в двоичном дереве каждый форк в пути выбирается в результате операции сравнения. Если последующее сравнение вернет другой результат, будет взят другой форк, и ранее сохраненный ключ не будет найден.

Answer 5

Я на 99% уверен, что это не сработает. Если значение в наборе внезапно меняет свое поведение сравнения, вполне возможно, что на самом деле оно больше не будет найдено; то есть set.contains(value) вернет false, потому что алгоритм поиска в какой-то момент выполнит сравнение и продолжит работу в неправильном поддереве, потому что это сравнение теперь возвращает результат, отличный от того, который был при вводе значения.

Answer 6

Как уже отмечалось, Компаратор не может сделать это за вас, потому что транзитивность нарушена. По сути, чтобы иметь возможность сортировать элементы, вы должны уметь сравнивать каждые два из них (независимо от остальных), что, очевидно, вы не можете сделать. Таким образом, ваш сценарий в основном либо не будет работать, либо даст непоследовательный результат.

Может быть, вам подойдет что-нибудь попроще:

• применить простой компаратор, который использует значение по мере необходимости
• и просто удалите из списка / коллекции все элементы, которые на 7 дней старше, чем самые новые. Как правило, каждый раз, когда добавляется новый элемент, вы проверяете, является ли он самым новым, и, если это так, удаляете те, которые старше на 7 дней.

Это не будет работать, если вы также удалите элементы из списка, и в этом случае вам нужно будет сохранить все те, которые вы удалили, в отдельном списке (который, кстати, вы бы отсортировали по дате) и добавить их обратно в список. исходный список в случае, если МАКС (дата) меньше после удаления.

Answer 7

Возможно, что запись изменится с <7 дней до> 7 дней в середине сортировки, поэтому то, что вы делаете, нарушает правила для компаратора. Конечно, это не означает, что это не сработает: многие вещи, которые задокументированы как «непредсказуемые», на самом деле работают, если вы точно знаете, что происходит внутри.

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

По крайней мере, я бы сказал, что вы не можете полагаться на TreeSet или любую "отсортированную структуру", волшебным образом прибегающую к самому себе, когда даты пересекают границу. В лучшем случае это может сработать, если вы выполните повторную сортировку непосредственно перед отображением и не будете полагаться на что-то правильное между обновлениями.

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

Поэтому я бы сказал: прочитайте исходный код Sun для любых классов или функций, которые вы планируете использовать, и посмотрите, сможете ли вы выяснить, что произойдет. Тестирование это хорошо, но есть потенциально сложные случаи, которые сложно протестировать. Наиболее очевидным является то, что: если в процессе сортировки запись переходит границы даты? То есть он может один раз взглянуть на запись и сказать, что она <7, но в следующий раз, когда увидит ее,> 7. Это может быть плохо, плохие новости.

Одна очевидная хитрость, которая приходит мне в голову: преобразовывать дату в возраст, когда вы добавляете запись в структуру, а не динамически. Таким образом, это не может измениться в сортировке. Если конструкция будет жить дольше нескольких минут, пересчитайте возрасты в какое-то подходящее время и затем пересортируйте. Я сомневаюсь, что кто-то скажет, что ваша программа неверна, потому что вы сказали, что записи менее 7 дней, а на самом деле ей 7 дней, 0 часов, 0 минут и 2 секунды. Даже если кто-то заметил, насколько точны их часы?

Answer 8

Я думаю, что неизменяемый характер Comparator должен быть индивидуальным для каждой сортировки, поэтому, если вы согласны в течение всей операции сортировки, у вас все в порядке (до тех пор, пока предметы пересекают 7-дневную границу средней сортировки).

Однако, возможно, вы захотите сделать более очевидным, что вы спрашиваете конкретно о TreeSet, который, я полагаю, повторно использует информацию из предыдущих сортировок, чтобы сэкономить время при добавлении нового элемента, так что это немного особый случай , Javadocs TreeSet специально относятся к семантике Comparator, поэтому вас, вероятно, официально не поддерживают, но вам придется прочитать код, чтобы получить представление о том, безопасны ли вы.

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