Измерение времени не подтверждает преимущества LinkedList

Я читаю различия между ArrayList и LinkedList, указанные в Когда использовать LinkedList вместо ArrayList?< /а>. Я разработал небольшой пример приложения, чтобы проверить главное преимущество LinkedList, но полученные результаты не подтверждают, что LinkedList перевешивает ArrayList в производительности операции:

ListIterator.add(E element)

Вот мой код:

public static void main(String[] args) {

        int number = 100000;

        long startTime1 = System.currentTimeMillis();
        fillLinkedList(number);
        long stopTime1 = System.currentTimeMillis();

        long startTime2 = System.currentTimeMillis();
        fillArrayList(number);
        long stopTime2 = System.currentTimeMillis();

        System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1));
        System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2));

    }


    public static void fillLinkedList(int number){

        LinkedList<Integer> list = new LinkedList<Integer>();
        ListIterator<Integer> it = list.listIterator();
        int i = 0;
        while(i++<number){
            it.add(i);
        }
    //  System.out.println("LinkedList size: "+list.size());

    }


    public static void fillArrayList(int number){
        ArrayList<Integer> list = new ArrayList<Integer>();
        ListIterator<Integer> it = list.listIterator();
        int i = 0;
        while(i++<number){
            it.add(i);
        }
    //  System.out.println("ArrayList size: "+list.size());
    }

Измерение дает:

number            10,000     100,000     500,000      1,000,000     5,000,000

ArrayList            7         17         60             77           170

LinkedList           7         21         89             838          4127

Я заметил, что увеличение количества элементов значительно снижает производительность LinkedList, в то время как ArrayList ведет себя значительно лучше. Я понял что-то ложное?


java arraylist linked-list listiterator
person arjacsoh    schedule 05.10.2013    source источник
comment
Обратите внимание, что с LinkedList вам нужно создать объект Node для каждой вставки. С ArrayList вам нужно увеличить массив.   -  person Sotirios Delimanolis    schedule 05.10.2013
comment
Вы все правильно поняли. Переполнение стека полно с...   -  person GOTO 0    schedule 05.10.2013
comment
Для будущих измерений вам, вероятно, следует использовать System.nanoTime() вместо System.currentTimeMillis(), поскольку точность последнего намного меньше, и вы фактически измеряете здесь не текущее время, а разницу между двумя точками.   -  person Sebastiaan van den Broek    schedule 05.10.2013
comment
Если вы сначала заполните ArrayList, а потом LinkedList, то результаты будут очень разными. ArrayList по-прежнему в основном выигрывает, но он намного ближе.   -  person Hari Menon    schedule 05.10.2013
comment
О, и, пожалуйста, публикуйте полные исполняемые образцы, когда это возможно, это облегчит расследование.   -  person zch    schedule 05.10.2013
comment
Как вы думаете, почему в этом случае LinkedList должно быть быстрее, чем ArrayList? Я не вижу ничего в упомянутом вопросе, который поддерживает это предположение. LinkedList и ArrayList имеют одинаковое асимптотическое амортизированное поведение при добавлении. Однако для последнего постоянный фактор существенно меньше.   -  person nosid    schedule 05.10.2013
comment
stackoverflow.com/questions/10656471/   -  person Prabhakaran Ramaswamy    schedule 05.10.2013
comment
Хорошо, ответ на связанный вопрос пишет, что ListIterator.add(E element) равен O(n-index) в ArrayList. Я не понимаю, что такое индекс при переборе списка с помощью итератора. Однако в лучшем случае производительность должна быть как минимум равной, что можно доказать на моем примере.   -  person arjacsoh    schedule 05.10.2013

Ответы (3)


arrow_upward
6
arrow_downward

ArrayList быстрее при добавлении элемента в конец контейнера или очень близко, так как тогда не нужно сдвигать много элементов. Медленно, при добавлении в середине или в начале. Я изменил ваш цикл на следующий:

    while(i++<number){
        it.add(i);
        if(i%2 == 0)
            it.previous();
    }

Теперь it всегда будет указывать на середину list. С этим тестом LinkedList работает намного быстрее. Результаты за 200000 год:

LinkedList needed: 47
ArrayList needed: 4702
person zch    schedule 05.10.2013
comment
Можете ли вы объяснить, что вы подразумеваете под: теперь он всегда будет указывать на середину списка? Я не думаю, что ваш код делает это. - person arjacsoh; 05.10.2013
comment
@arjacsoh - каждую секунду add я возвращаюсь на один элемент назад. Фактически я делаю add n раз, но продвигаюсь только n/2 раза. - person zch; 05.10.2013
comment
Это верно, но не то же самое с вашим утверждением. Теперь оно всегда будет указывать на середину списка. - person arjacsoh; 05.10.2013
comment
@arjacsoh, если вы хотите, чтобы я был предельно точен: после каждой итерации цикла it будет указывать на элемент с индексом (list.size()+1)/2. - person zch; 05.10.2013

arrow_upward
0
arrow_downward

Вставка и удаление в начале или середине (массива или списка) — это когда список вытесняет массив.

person Mike Makuch    schedule 05.10.2013

arrow_upward
-1
arrow_downward

Насколько я понимаю, преимущество LinkedList заключается в вставке значения в заданный индекс (скажем, в середине или в начале). ArrayList не проиграет при последовательной вставке, так как ему не нужно сдвигать элементы.

После того, как вы заполнили свои списки, как указано выше, посмотрите, что вы получите за вставку на месте в разные места. Я изменил ваш пример, чтобы показать пример значительного выигрыша LinkedList (по крайней мере, в моей настройке):

public static void main(String[] args) {

    int number = 5000000;

    LinkedList<Integer> llist = new LinkedList<Integer>();
    ArrayList<Integer> alist = new ArrayList<Integer>();

    long startTime1 = System.nanoTime();
    fillLinkedList(number, llist);
    long stopTime1 = System.nanoTime();

    long startTime2 = System.nanoTime();
    fillArrayList(number, alist);
    long stopTime2 = System.nanoTime();

    System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1));
    System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2));

    startTime1 = System.nanoTime();
    llist.add(1, 4);
    stopTime1 = System.nanoTime();

    startTime2 = System.nanoTime();
    alist.add(1, 4);
    stopTime2 = System.nanoTime();

    System.out.println(" LinkedList needed: "+ (stopTime1 - startTime1));
    System.out.println(" ArrayList needed: "+ (stopTime2 - startTime2));

}

public static void fillLinkedList(int number, LinkedList<Integer> list){


    ListIterator<Integer> it = list.listIterator();
    int i = 0;
    while(i++<number){
        it.add(i);
    }
    //  System.out.println("LinkedList size: "+list.size());

}


public static void fillArrayList(int number, ArrayList<Integer> list){
    ListIterator<Integer> it = list.listIterator();
    int i = 0;
    while(i++<number){
        it.add(i);
    }
    //  System.out.println("ArrayList size: "+list.size());
}
person grdryn    schedule 05.10.2013