Сортировка Collections.sort() и замер времени выполнения

291

24 августа 2017, 19:31

Здравствуйте, пытаюсь замерить время для сортировки в одинаковых условиях для LinkedList & ArrayList.

public static long test(List<Integer> list, int reps) {
    List<Integer> copy = list;
    long begin = System.nanoTime();
    for (int i = 0; i < reps; i++) {
        Collections.sort(list);
        list = copy;
    }
    long end = System.nanoTime();
    return (end - begin) / reps;
}

Array List: 50241 ns

Linked List: 109349 ns

Array List: 22740 ns

Linked List: 37354 ns

Array List: 36633 ns

Linked List: 45177 ns

Сортировка идёт за log(n), но у меня при трех повторениях выдаёт, что LinkedList сортируется в 2-3 раза медленнее (очень редко приблизительно одинаково). Вообще, замеряет как будто рандомно, не могу понять почему такой разброс замеров.

Answer 1

Use the Source, Luke - иными словами смотрите исходные тексты.

Итак всматриваемся и видим, что исходники ArrayList показывают, что это всего лишь обертка над Object[]

Далее, давайте заглянем в исходники LinkedList - видим, что это обертка над структурой типа двунаправленный список:

 private static class Entry<E> {
   E element; //собственно сам элемент
   Entry<E> next;  //указатель на следующий элемент
   Entry<E> previous;  //указатель на следующий элемент
   //blah-blah
 }

Обертка собственно говоря содержит только указатель на голову такого списка header, далее если надо позиционироваться на нужный элемент то надо пройтись по списку от начала до конца: header.next() и так n раз - в случае же ArrayList - позиционирование производится практически мгновенно по индексу массива.

Вот собственно говоря и все - сортировка предусматривает активные операции по позиционированию в списке/массиве, соответственно, в случае LinkedList - это выливается в нудные последовательные перемещения вдоль списка, а ArrayList - как бы устройство с прямым доступом.