Сортировка ArrayList может завершиться ошибкой при использовании списка в компараторе. Это задокументировано? - PullRequest
Новая
       42

Сортировка ArrayList может завершиться ошибкой при использовании списка в компараторе. Это задокументировано?

0 голосов
/ 06 января 2019

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

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

        if (keys.contains(itemId)) {
          ...

Поскольку keys - это список, который мы сортируем, это может произойти в компараторе, если ключ не найден в списке из-за внутренней механики TimSort.

Вопрос: упоминается ли где-нибудь в Javadoc (не удалось его найти), что вы не должны получать доступ к базовому списку в Comparator? Это плохая реализация TimSort, которая должна сортировать копию? Или это была глупая идея, прежде всего, получить доступ к базовому списку в компараторе?

Программа, приведенная ниже, предоставлена ​​ T.J. Crowder демонстрирует, что содержимое базового списка может быть непоследовательным во время обращений к Comparator. (Эта программа демонстрирует рассматриваемое явление, но не отражает фактическое приложение, на которое повлияла проблема.) 

import java.util.*;

public class Example {
    private static String[] chars = {
        "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"
    };

    private List<String> list;
    private String[] entries;

    private Example() {
        this.entries = new String[1000];
        for (int n = 0; n < 1000; ++n) {
            this.entries[n] = chars[n % chars.length] + n;
        }
        // Ensure it's an ArrayList, specifically
        this.list = new ArrayList<String>(Arrays.asList(this.entries));
    }

    public static void main(String[] args) {
        (new Example()).run();
    }

    class ListComparator implements Comparator<String> {
        public int compare(String a, String b) {
            for (String s : entries) {
                int i1 = Example.this.list.indexOf(s);
                if (i1 == -1) {
                    System.out.println(s + ": Missing");
                } else {
                    int i2 = Example.this.list.lastIndexOf(s);
                    if (i2 != i1) {
                        System.out.println(s + ": Duplicated, at " + i1 + " and " + i2);
                    }
                }
            }
            return a.compareTo(b);
        }
    }

    private void run() {
        this.list.sort(new ListComparator());
    }
}

Вот первые несколько строк вывода из цикла: 

b1: Missing
a52: Duplicated, at 2 and 32
b27: Missing
a52: Duplicated, at 2 and 32
c2: Missing
a52: Duplicated, at 2 and 32
c2: Missing
c28: Missing
a52: Duplicated, at 2 and 32
b53: Duplicated, at 5 and 33
c28: Missing
d29: Missing
a52: Duplicated, at 2 and 32
b53: Duplicated, at 5 and 33
d3: Missing
d29: Missing
a52: Duplicated, at 2 and 32
b53: Duplicated, at 5 and 33
d3: Missing
d29: Missing
e30: Missing

1 Ответ

0 голосов
/ 08 января 2019

Немного истории: в JDK 7 алгоритм TimSort заменил предыдущий алгоритм «устаревшей сортировки слиянием». В JDK 8 Collections.sort() делегирует новый метод по умолчанию List.sort(). Этот метод по умолчанию переопределяется на ArrayList, что делает сортировку на месте. Предыдущая реализация Collections.sort() копировала список во временный массив, выполняла сортировку этого временного массива, а затем копировала элементы из временного массива обратно в исходный список.

Если компаратор сортировки просматривает отсортированный список, то на его поведение наверняка будет влиять новое поведение сортировки на месте ArrayList, представленное в JDK 8. Переход от "сортировки слиянием устаревших типов" к TimSort в JDK 7 в этом случае, вероятно, это никак не повлияет, поскольку JDK 7 все еще выполняет сортировку по временной копии.

Поведение копирования-сортировки-копирования List.sort() описано в разделе «Требования к реализации», который определяет поведение реализации метода по умолчанию, но не является частью контракта интерфейса, который накладывается на все реализации. Таким образом, ArrayList (и другие подклассы) могут изменить это поведение. Отмечу, что документации для переопределенной реализации ArrayList.sort() нет. Я полагаю, что было бы небольшое улучшение, если бы была добавлена ​​некоторая документация, определяющая порядок сортировки на месте.

Если сортировка на месте ArrayList является проблемой, вы можете скопировать список перед сортировкой: 

List<Key> list = ... ;
List<Key> newList = new ArrayList<>(list);
newList.sort(keyComparator); // uses the old list
list = newList;

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

...