Почему Collections.sort () не оптимизирован для ArrayList, а предназначен для LinkedList? - PullRequest
Новая
       26

Почему Collections.sort () не оптимизирован для ArrayList, а предназначен для LinkedList?

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

Почему Collections.sort() создает дополнительный массив объектов и выполняет сортировку по Тиму массива, а затем, наконец, копирует отсортированный массив обратно в List объект? Я знаю, что этот вызов оптимизирован для LinkedList, но не потеряем ли мы производительность для ArrayList?

Мы могли бы избежать 2n количества операций при преобразовании его в массив объектов и добавлении их обратно в список. Я знаю, что эти дополнительные операции не повлияют на Big-O всей операции сортировки, но я считаю, что она могла бы быть дополнительно оптимизирована для ArrayList.

Я что-то здесь упускаю? Я просто пытаюсь понять, почему архитектура такова. Спасибо.

https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/Collections.java#l164

1 Ответ

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

Вы смотрите старую версию JDK. По крайней мере, с тех пор, как JDK 1.8.0_162 Collections.sort() вызывает List s sort(Comparator<? super E> c). И хотя реализация по умолчанию создает массив из List и сортирует этот массив, ArrayList переопределяет эту реализацию по умолчанию и сортирует резервный массив напрямую.

Collections * sort: 

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    list.sort(null);
}

List sort: 

default void sort(Comparator<? super E> c) {
    Object[] a = this.toArray();
    Arrays.sort(a, (Comparator) c);
    ListIterator<E> i = this.listIterator();
    for (Object e : a) {
        i.next();
        i.set((E) e);
    }
}

ArrayList sort: 

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

Другими словами, это было исправлено в версиях JDK, более новых, чем та, на которую вы смотрите.

Вы можете посмотреть источник здесь (благодаря ссылке eckes).

...