4

Решил сравнить быстродействие. Написал простой пример:

public class ServiceList {
    public void addList(List list, String name){
        Date start = new Date();
        for (int i = 0; i < 4000000; i++) {
            list.add(new String());
        }
        Date finish = new Date();


        long time = finish.getTime() - start.getTime();
        //sum = sum + time;

        System.out.println("ADD "+ name + " : " + time);
    }
}


public class Main {
        public static void main(String[] args) {
            for(int i = 0; i < 10; i++) {
                new ServiceList().addList(new ArrayList(), "ArrayList");
                new ServiceList().addList(new LinkedList(), "LinkedList"); 
                System.out.println("- - - - - - - - -");

            }
        }
    }

Результаты просто удивляют:

ADD ArrayList : 1218
ADD LinkedList : 2673
- - - - - - - - -
ADD ArrayList : 156
ADD LinkedList : 187
- - - - - - - - -
ADD ArrayList : 141
ADD LinkedList : 125
- - - - - - - - -
ADD ArrayList : 141
ADD LinkedList : 297
- - - - - - - - -
ADD ArrayList : 31
ADD LinkedList : 656
- - - - - - - - -
ADD ArrayList : 188
ADD LinkedList : 32
- - - - - - - - -
ADD ArrayList : 223
ADD LinkedList : 422
- - - - - - - - -
ADD ArrayList : 31
ADD LinkedList : 1001
- - - - - - - - -
ADD ArrayList : 312
ADD LinkedList : 391
- - - - - - - - -
ADD ArrayList : 31
ADD LinkedList : 1141
- - - - - - - - -

Почему они такие разные? А порой даже linked быстрее?

2

1 ответ 1

11

Нет смысла сравнивать эти структуры, если нет контекста их применения. Вставки только в конец? Удаления будут? Доступ нужен к каким элементам?

  1. У вас вставка всегда в конец. Там сложность O(1) для обеих реализаций. Вот только у ArrayList ресайз происходит, если он полностью забит. А стартовый размер, если память не изменяет, равен 10. То есть, уже после десятой вставки там будет ресайз.
  2. По поводу вставки. LinkedList выигрывает, когда вставки осуществляются в середину списка. Особенно, если вы переиспользуете итератор, тогда вставка/удаление может выполняться за O(1).
  3. Обращение к элементу в ArrayList всегда за O(1). В LinkedList в худшем случае O(n).
  4. Мне почему-то кажется, что вы там больше замеряете не работу с коллекциями, а время на создание строк. А если там в промежутках stop the world у GC будет, то вообще не релевантный тест тогда.
  5. У вас тесты без прогрева. По-хорошему, до тестов нужно прогреть jvm.
  6. Использовать Date для замеров времени - ужас. Используйте System.nanoTime() или хотя бы System.currentTimeMillis().

К чему это я? Ну да, вы получили какие-то метрики, но на них не сделать никаких выводов, пока не ясен контекст использования этих структур.

2
  • Хочу полностью сравнить. Добавление, вставку, удаление и поиск в начале, середине и конце, но пока только на добавлении остановился. Как по хорошему сделать метрику более менее и прогреть jvm? Commented 6 мая 2018 в 15:06
  • @KeyJibo по поводу тестов я небольшую памятку написал ru.stackoverflow.com/a/824248/15479 Commented 7 мая 2018 в 9:07

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.