Понимать метод сравнения при сортировке коллекции - PullRequest
Новая
       22

Понимать метод сравнения при сортировке коллекции

0 голосов
/ 28 декабря 2018

У меня есть следующий фрагмент кода для сортировки коллекции элементов, имеющих свойство метки: 

Collections.sort(myList, new Comparator<ListItem>() {
            @Override
            public int compare(ListItem lhs, ListItem rhs) {
                Crashlytics.log(Log.DEBUG, TAG, "lhs.getLabel(): " + lhs.getLabel() + " | rhs.getLabel(): " + rhs.getLabel());
                if (lhs.getLabel() == null || rhs.getLabel() == null) {
                    return 0;
                }
                return lhs.getLabel().compareTo(rhs.getLabel());
            }
        });

У меня есть несколько отчетов о сбоях со следующей трассировкой стека: 

Caused by java.lang.IllegalArgumentException: Comparison method violates its general contract!
       at java.util.TimSort.mergeLo(TimSort.java:777)
       at java.util.TimSort.mergeAt(TimSort.java:514)
       at java.util.TimSort.mergeForceCollapse(TimSort.java:457)
       at java.util.TimSort.sort(TimSort.java:254)
       at java.util.Arrays.sort(Arrays.java:1498)
       at java.util.ArrayList.sort(ArrayList.java:1470)
       at java.util.Collections.sort(Collections.java:201)
       at uk.co.aquanetix.activities.MyActivity.onCreate(MyActivity.java:59)
       at android.app.Activity.performCreate(Activity.java:7183)
       at android.app.Instrumentation.callActivityOnCreate(Instrumentation.java:1220)
       at android.app.ActivityThread.performLaunchActivity(ActivityThread.java:2910)
       at android.app.ActivityThread.handleLaunchActivity(ActivityThread.java:3032)
       at android.app.ActivityThread.-wrap11(Unknown Source)
       at android.app.ActivityThread$H.handleMessage(ActivityThread.java:1696)
       at android.os.Handler.dispatchMessage(Handler.java:105)
       at android.os.Looper.loop(Looper.java:164)
       at android.app.ActivityThread.main(ActivityThread.java:6944)
       at java.lang.reflect.Method.invoke(Method.java)
       at com.android.internal.os.Zygote$MethodAndArgsCaller.run(Zygote.java:327)
       at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:1374)

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

Моя проблема в том, что я не могу воспроизвести его.Это происходит только в какой-то конкретной ситуации, которую я не могу понять.

Как видите, я отправляю значения меток в Crashlytics, поэтому это те значения, которые были отправлены, когда произошел сбой. 

0 | 1545921010869 | D/MyActivity lhs.getLabel(): 14:49:22 | rhs.getLabel(): 13:21:22
1 | 1545921010870 | D/MyActivity lhs.getLabel(): 13:25:41 | rhs.getLabel(): 14:49:22
2 | 1545921010870 | D/MyActivity lhs.getLabel(): 13:25:41 | rhs.getLabel(): 14:49:22
3 | 1545921010870 | D/MyActivity lhs.getLabel(): 13:25:41 | rhs.getLabel(): 13:21:22
4 | 1545921010870 | D/MyActivity lhs.getLabel(): 14:53:26 | rhs.getLabel(): 13:25:41
5 | 1545921010870 | D/MyActivity lhs.getLabel(): 14:53:26 | rhs.getLabel(): 14:49:22
6 | 1545921010870 | D/MyActivity lhs.getLabel():  | rhs.getLabel(): 14:49:22
7 | 1545921010870 | D/MyActivity lhs.getLabel():  | rhs.getLabel(): 13:25:41

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

Мои вопросы:

  • В чем может быть причина невозможности воспроизведения с использованием тех же значений?
  • Должен ли код быть лучше без условия if?

1 Ответ

0 голосов
/ 28 декабря 2018

Как вы заметили, этот компаратор не транзитивен.Рассмотрим три ListItem s a, b и c с метками "a", "b" и null соответственно.При использовании этого компаратора оба значения compare(a, c) и compareTo(b, c) равны 0, поскольку c.getLabel() равно null, но compare(a, b) явно не соответствует, что нарушает правило танзитивности.

Для решения этой проблемыВ этой проблеме вы можете произвольно решить, что ListItem s с метками null всегда будут последними (или первыми, ради аргумента. Просто замените 1 s в приведенном ниже коде на -1 s и наоборот): 

Collections.sort(myList, new Comparator<ListItem>() {
    @Override
    public int compare(ListItem lhs, ListItem rhs) {
        if (lhs.getLabel() == null) {
            if (rhs.getLabel() == null) {
                return 0;
            }
            return 1;
        }
        if (rhs.getLabel() == null) {
            return -1;
        }
        return lhs.getLabel().compareTo(rhs.getLabel());
    }
});

Обратите внимание, что если вы используете Java 8, вы можете сохранить большую часть этого стандартного кода: 

myList.sort(Comparator.comparing
            (ListItem::getLabel, Comparator.nullsLast(Comparator.naturalOrder())));
...