Performance Test: ArrayList, Vector, LinkedList

В рамках изучение Java Collection Framework в нашей школе, мы решили сделать несколько заметок на закрелепление понимания принципов реализаций структур данных в Java.

Первыми в обзоре получились: ArrayList, Vector, LinkedList. У нас получилось 5 тестов, которые показывают основные отличия списков от массивов (в случае ArrayList/Vector).

Итак, какие тесты запускались и что в них происходит.
Давайте посмотрим на список:

FillListTest: добавление элементов в начало списка.

Random random = new Random();

for (int i = 0; i < LIST_LOAD_SIZE; i++) {
	listToTest.add(0, Integer.toString(random.nextInt(ELEMENTS_RANGE)));
}

FillListByIndexTest: добавление элементов по индексу в конец списка.

        Random random = new Random();

        for (int i = 0; i < LIST_LOAD_SIZE; i++) {
            listToTest.add(i, Integer.toString(random.nextInt(ELEMENTS_RANGE)));
        }

GetListTest: случайный доступ/чтение по индексу в списке.

        Random random = new Random();

        for (int i = 0; i < LIST_GET_SIZE; i++) {
            listToTest.get(random.nextInt(LIST_GET_SIZE));
        }

 

RemoveListTest: удаление элементов из головы списка.

        for (int i = 0; i < LIST_GET_SIZE; i++) {
            listToTest.remove(0);
        }

 

InsertListTest: добавление элементов через позицию итератора.

        Random random = new Random();
        ListIterator listIterator = listToTest.listIterator(listToTest.size() / 2);

        for (int i = 0; i < INSERT_SIZE && i < listToTest.size(); i++) {
            listIterator.add(Integer.toString(random.nextInt(ELEMENTS_RANGE)));
        }

 

Каждый тест был выполнен над ArrayList, Vector и LinkedList классами. Результат.

ArrayList Add 1000000 elements to first : 238.43 sec
Vector Add 1000000 elements to first : 226.28 sec
LinkedList Add 1000000 elements to first : 1.04 sec
————————————-
ArrayList Add 1000000 elements by index to last : 0.45 sec
Vector Add 1000000 elements by index to last : 1.16 sec
LinkedList Add 1000000 elements by index to last : 1.30 sec
————————————-
ArrayList Random access by index 50000 times : 0.01 sec
Vector Random access by index 50000 times : 0.02 sec
LinkedList Random access by index 50000 times : 59.70 sec
————————————-
ArrayList Remove first element 10000 times : 29.08 sec
Vector Remove first element 10000 times : 25.53 sec
LinkedList Remove first element 10000 times : 0.01 sec
————————————-
ArrayList Insert 10000 elements in the middle by iterator : 2.14 sec
Vector Insert 10000 elements in the middle by iterator : 1.99 sec
LinkedList Insert 10000 elements in the middle by iterator : 0.02 sec
————————————-

Давайте посмотрим, где скорость хорошая, где есть «просадка» в силу внутреннего устройства реализации.

Сравнительный анализ результатов

 

Сразу скажем, что Vector взяли за компанию для ArrayList. Накладные расходы на сихнронизацию в одно-поточном приложении небольшие, поэтому скорость Vector очень похожа на скорость ArrayList, немного ему уступая.

Несколько комментариев по результатам каждой реализации:

1) добавление элементов в начало списка

- ArrayList, Vector: происходит копирование/смещение массива при вставки новых элементов в начало. Сложность задачи возрастает, особенно при больших объёмах коллекции.

+ LinkedList: список получает новый головной элемент при вставке в начало. Затраты только на создание ссылки «связности» (next), которыми оперирует двух-связный список.

2) добавление элементов по индексу в конец списка

+ ArrayList, Vector, LinkedList: у всех хорошие результаты, только LinkedList немного медленней из-за поддержки связей в двух-связном списке. У ArrayList/Vector не происходит смещение, но случается переполнение capacity. Но даже в этом случае, средняя скорость вышла выше, при том же объеме элементов, что и LinkedlList в этом тесте.

3) случайный доступ/чтение по индексу в списке

+ ArrayList, Vector: так как внутри этих реализаций массивы, то доступ по индексу обеспечивается за быстрое и константное время.

- LinkedList: индекса нет, нахождения элемента происходит последовательным перебором с головы списка в цикле.

4) удаление элементов из головы списка

- ArrayList, Vector: происходит копирование/смещение массива при удалении элементов не с конца. Сложность задачи возрастает, особенно при больших объёмах коллекции.

+LinkedList: головный элемент «отцепляется» от списка headNode.next / headNode.item = null. Операция происходит очень быстро.

5) добавление элементов через позицию итератора

- ArrayList, Vector: происходит копирование/смещение массива при добавлении элементов не с конца. Сложность задачи возрастает, особенно при больших объёмах коллекции.

+LinkedList: при использовании позиции итератора, мы получаем ссылку на конкретный эллемент в памяти, после которого нужно вставить новый элемент. «Переклеивание» ссылок происходит очень быстро.

Вот и все. При написании данных тестов, мы подошли со стороны позитивных сторон LinkedList, получился своебразный PR обзор этой структуры :-).  На самом деле, понимая как работает LinkedList — связный список, вы сможете понять как работает ArrayList  и когда его лучше использовать или не использовать.

 

Кому интересно, дальше приведены детали реализации программы:

Ниже приведены методы-драйверы всего процесса тестирования.

public class PerformanceDemo {
    private PerformanceReport performanceReport = new PerformanceReport();

    public static void main(String[] main) throws ExecutionException, InterruptedException {
        PerformanceDemo demo = new PerformanceDemo();
        demo.testAll();
    }

    private void testAll() throws ExecutionException, InterruptedException {
        runListTest();
        System.gc();
        performanceReport.printReport(System.out);
    }

    private void runListTest() throws ExecutionException, InterruptedException {
        int reportSize = 15;
        performanceReport.reset(reportSize);
        ExecutorService executor = Executors.newFixedThreadPool(reportSize);

        ArrayList arrayList = new ArrayList();
        Vector vector = new Vector();
        LinkedList linkedList = new LinkedList();

        String operation = String.format("Add %d elements to first", LIST_LOAD_SIZE);

        performanceReport.track(executor.submit(buildTest(ARRAY_LIST_CLASS, operation, 
                new FillListTest(new ArrayList<>()))).get());
        performanceReport.track(executor.submit(buildTest(VECTOR_CLASS, operation, 
                new FillListTest(new Vector<>()))).get());
        performanceReport.track(executor.submit(buildTest(LINKED_LIST_CLASS, operation, 
                new FillListTest(new LinkedList<>()))).get());
        performanceReport.addEmptyLine();

 

Так как тесты однотипные (нужно засечь время старта, выполнить тестовый код, засечь время финиша), мы решили использовать интерфейс Runnable для всех тестов, но не много-поточности ради. На вход тесту, например FillListTest, задаётся объект коллекция, над которым и нужно провести тестовую операцию

public abstract class ListTest implements Runnable {
    public static final int LIST_LOAD_SIZE = 1_000_000;
    public static final int LIST_GET_SIZE = 50_000;
    public static final int LIST_REMOVE_SIZE = 10_000;
    public static final int INSERT_SIZE = 10_000;
    public static final int ELEMENTS_RANGE = LIST_LOAD_SIZE;

    public static final String ARRAY_LIST_CLASS = "ArrayList";
    public static final String LINKED_LIST_CLASS = "LinkedList";
    public static final String VECTOR_CLASS = "Vector";

    protected List listToTest;

    public ListTest(List listToTest) {
        this.listToTest = listToTest;
    }

    public abstract void run();
}

public class FillListTest extends ListTest {

    public FillListTest(List listToTest) {
        super(listToTest);
    }

    @Override
    public void run() {
        Random random = new Random();

        for (int i = 0; i < LIST_LOAD_SIZE; i++) {
            listToTest.add(0, Integer.toString(random.nextInt(ELEMENTS_RANGE)));
        }
    }
}

 

Остальный четыре *Test класса похожие на FillListTest. Смысловая часть приведена в начале заметки.

Метод для создания Callable объекта, который вернет нам сущность PerformanceTracker, это и есть строка для нашего финального отчёта:

    private Callable<PerformanceTracker> buildTest(final String collectionName, 
                                                   final String operationName,
                                                   final Runnable listTest) {
        return new Callable<PerformanceTracker>() {
            @Override
            public PerformanceTracker call() {
                final long startTime = System.currentTimeMillis();
                listTest.run();
                final long endTime = System.currentTimeMillis();
                return new PerformanceTracker(collectionName, operationName, startTime, endTime);
            }
        };
    }

 

Служебный класс PerformanceReport, который мы заполняем по ходу тестирования:

public class PerformanceReport {
    private List<PerformanceTracker> trackerList = new ArrayList<>();

    public void reset(int size) {
        trackerList = new ArrayList<>(size);
    }

    public void track(PerformanceTracker performanceTracker) {
        trackerList.add(performanceTracker);
    }

    public void printReport(PrintStream outputStream) {
        for (PerformanceTracker tracker : trackerList) {
            if (tracker != null ) {
                outputStream.printf("%s %s : %.2f sec%n", tracker.getCollectionName(), 
                        tracker.getOperation(), tracker.getDuration() / 1000f);
            } else {
                outputStream.println("-------------------------------------");
            }
        }
    }

    public void addEmptyLine() {
        trackerList.add(null);
    }
}