З'яўляецца LinkedList сапраўды хутчэй, чым ArrayList ў выпадку ўстаўкі ў сярэдзіне спісу?

- У чым розніца паміж LinkedList і ArrayList ? Калі гэта пераважней выкарыстоўваць LinkedList

Я думаю, што кожны распрацоўшчык Java чуў гэтае пытанне ў інтэрв'ю, па меншай меры адзін раз.

-. Звязаны спіс з'яўляецца пераважнай, калі вы хочаце, каб мець магчымасць ўстаўляць элементы ў сярэдзіне спісу

Гэта агульны адказ на гэтае пытанне. Усё гэта ведаюць. Кожны раз, калі вы задаеце пытанне аб розніцы паміж рэалізацыямі List вы атрымліваеце такія адказы, як:

<�Р> Калі варта выкарыстоўваць LinkedList? Калі вам трэба эфектыўнае выдаленне ў паміж элементамі або ў пачатку?

Адсюль

<�Р> Забыўся згадаць выдаткі ўстаўкі. У LinkedList, калі ў вас ёсць правільнае становішча, ўстаўныя выдаткі O (1) , у той час як у ArrayList ён ідзе да Аб (п) - усё элементы апошнія ўстаўкі кропка павінна быць перамешчаная.

Адсюль

<�Р> Змяненні спісы пераважней масіваў, калі вы хочаце, каб мець магчымасць ўстаўляць элементы ў сярэдзіне спісу (напрыклад, як прыярытэтнай чарзе).

Адсюль

<�Р> ArrayList павольней, таму што трэба скапіяваць частка масіва, каб выдаліць слот, які стаў вольным. LinkedList проста павінен маніпуляваць пару спасылак.

Адсюль

І больш...

Але вы калі-небудзь спрабавалі прайграць яго самастойна? Я паспрабаваў ўчора і атрымаў наступныя вынікі:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {
    public static void main(String... args) {
        final int MAX_VAL = 10000;
        List linkedList = new LinkedList();
        List arrayList = new ArrayList();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }
        long time = System.nanoTime();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(MAX_VAL/2, i);
        }
        System.out.println("LL time: " + (System.nanoTime() - time));
        time = System.nanoTime();
        for(int i = 0; i < MAX_VAL; i++) {
            arrayList.add(MAX_VAL/2, i);
        }
        System.out.println("AL time: " + (System.nanoTime() - time));
    }
}

<�Моцны> Выснова:

<�Р> LL час: 114098106      <�Р> AL час: 24121889

Дык што ж гэта? Чаму LinkedList смактаць так шмат? Можа быць, мы павінны паспрабаваць аперацыю выдалення замест дадаць? Добра, давайце паспрабуем:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Test {
    public static void main(String... args) {
        final int MAX_VAL = 10000;
        List linkedList = new LinkedList();
        List arrayList = new ArrayList();
        for(int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
            arrayList.add(i);
        }
        long time = System.nanoTime();
        for(int i = 0; i < MAX_VAL/2; i++) {
            linkedList.remove(MAX_VAL/2);
        }
        System.out.println("LL time: " + (System.nanoTime() - time));
        time = System.nanoTime();
        for(int i = 0; i < MAX_VAL/2; i++) {
            arrayList.remove(MAX_VAL/2);
        }
        System.out.println("AL time: " + (System.nanoTime() - time));
    }
}

<�Моцны> Выснова:

<�Р> LL час: 27581163      <�Р> AL час: 3103051

О, ArrayList яшчэ хутчэй, чым LinkedList. У чым прычына? Ці быў гэты міф лопнуў? Ці, можа быць, я памыляюся?

enter image description here

17
Часам гэта добрая ідэя, каб праверыць як спарадкаванасці: паспрабуйце ArrayList першай, LinkedList другі.
дададзена аўтар H2ONaCl, крыніца

7 адказы

<�Р> спусташэнне </р>

Не зусім. тут

for(int i = 0; i < MAX_VAL; i++) {
    linkedList.add(MAX_VAL/2, i);
}

вы не проста ўставіць элемент; вы аплачваеце кошт перабору з самага пачатку я кожны раз. Натуральна, што гэта O (я) .

З іншага боку, спіс павінен быць дастаткова вялікім, перш чым вы на самой справе сведкам выйгрыш у прадукцыйнасці ўстаўкі ў сярэдзіне спісу. <�Код> System.arraycopy з'яўляецца вокамгненна хуткай аперацыяй, і, з другога боку, кожная ўстаўка ў LinkedList патрабуе выдзялення асобніка вузла.

Такім чынам, ArrayList гэта лепшы выбар для 99% або больш рэальных выпадках, і выкарыстоўваючы вузкае перавага LinkedList патрабуе вялікай асцярожнасці.

Агульныя заўвагі па microbenchmarking ў JVM

Я таксама павінен папярэдзіць вас, што ваш код бенчмаркетынгу дрэнна недасканалы. Існуе даволі значны пералік рэчаў, каб назіраць за тым, калі microbencharking на JVM, напрыклад:

  • заўсёды разагрэць код, каб дазволіць JIT кампілятар атрымаць да яго;
  • быць вельмі асцярожнай інтэрпрэтацыяй nanoTime вынікаў з-за праблемы дакладнасці/дакладнасці. Зрабіць чытанне расці прынамсі, у мілісекундах (мільёны нанасекунд) для забеспячэння надзейнасці;
  • <�Літый> кантраляваць паразітныя пабочныя эфекты зборшчыка смецця;
  • і інш.

Таму савет выкарыстоўваць гатовую аснову microbenchmarking, такія як OpenJDK ў JMH ,

27
дададзена
O (я) справядліва толькі для LinkedList, ArrayList ўставіць direcly.
дададзена аўтар AlexWien, крыніца
@MarkoTopolnik, ды цяпер больш зразумела, у вашым пасце гэта ўводзіць у зман
дададзена аўтар AlexWien, крыніца
ок, 9 upvotes да памылкі былі вырашаны, людзі робяць upvote ўсляпую?
дададзена аўтар AlexWien, крыніца
Гэта не ітэрацыя зроблена вашым для -loop, але ўнутраная ітэрацыя неабходна для пераходу да <�я> я -га элемента спісу.
дададзена аўтар Marko Topolnik, крыніца
@AlexWien Я думаю, што людзі бачылі праз гэтую памылку да асноўнай кропцы, якая была згаданая О.П., а таксама. Ён, здаецца, не ўлічвалі гэта ў яго рэалізацыі.
дададзена аўтар Marko Topolnik, крыніца
Дзякуй! Ніколі не думаў пра ролю ітэрацыі да!
дададзена аўтар bsiamionau, крыніца
8
дададзена
калі вы ведаеце памер загадзя вы можаце ініцыялізаваць ArrayList з такім памерам, эканомячы час у пераразмеркаванні памяці для ўнутранага масіва, падчас гэтага ()
дададзена аўтар AlexWien, крыніца
новы ArrayList (MAX_VAL);
дададзена аўтар AlexWien, крыніца
@Matej Не! MAX_VAL дастаткова. ensureCapacity() вылучае толькі тады, калі бягучы памер не з'яўляецца дастатковым. Толькі тады выкарыстоўваецца каэфіцыент current_size * 1,5. addAll() яшчэ лепш.
дададзена аўтар AlexWien, крыніца
@Matej, добра вы маеце рацыю, прабачце.
дададзена аўтар AlexWien, крыніца
Я думаю, што вынікі розныя для двух аперацый (і бенчмаркетынгу зламаная). Але ў любым выпадку, для гэтых аперацый, якія змяняюць спіс з адным addAll павінен быць хутчэй (пераважаюць няяўна стварэння Integer аб'екты).
дададзена аўтар Tom Hawtin - tackline, крыніца
Можа быць, нам трэба было б ініцыялізаваць спіс масіва з памерам 2 * MAX_VAL. Аднак, як правіла, не necessry як спісы масіва эўрыстычны папярэдне вылучыць больш прасторы, калі спісы мадыфікаваных для прадухілення частых пераразмеркаванне. напрыклад IBM ява загадзя вылучае 1/2 з масіва бягучага памеру, іншыя рэалізацыі могуць выкарыстоўваць розныя эўрыстыкі. Аналагічны падыход можна знайсці праз іншых моў праграмавання і фреймворков, а таксама.
дададзена аўтар Matej, крыніца
@AlexWien Першапачаткова, ёсць цыкл, які ініцыялізуе масіў шляхам дадання MAX_VAL элементаў. Пасля гэтага кроку, алгарытм працягваецца з самай пратэставанымі часткамі, і дадае яшчэ MAX_VAL элементы ў сярэдзіну масіва. Мы будзем мець 2 * MAX_VAL элементаў у масіве. Калі мы будзем выкарыстоўваць MAX_VAL для ініцыялізацыі масіва, мы маем сітуацыю, калі масіў запоўнены, і мы былі б арыенцірам у пераразмеркаванні. Калі мы будзем выкарыстоўваць 2 * MAX_VAL, мы б эталонныя Устаўкі без паўторнага размеркавання. Абодва маюць сэнс. :-)
дададзена аўтар Matej, крыніца

<�Моцны> Ваш тэст мае ўхіл - ня вымярае розніцу звычайнай прадукцыйнасці .

Агульныя заўвагі аб структуры LinkedList (у параўнанні з ArrayList, для вялікага спісу):

    <�Літый> даданне/выдаленне вузла на галаву ці хвост вельмі хутка </літый>
  1. атрыманне элемента з сярэдзіны вельмі павольна
  2. атрыманне элемента становіцца хутчэй (лінейна) па меры набліжэнне да любога канца спісу
  3. атрыманне элемента з галавы або хваста набліжаецца да хуткасці з ArrayList
  4. <�Літый> даданне/выдаленне элемента дзесьці ў сярэдзіне складаецца з двух аперацый: атрымліваюць ўстаўку плюс вузел </літый>
  5. Калі вы карыстаецеся ListIterator, вы можаце дадаць/выдаліць вузел дзесьці ў сярэдзіне і ў пазбяганне атрымаць - вельмі хуткая аперацыя

Ваш тэст мае намер праверыць (5).

Але ён заўсёды праводзіць горшы выпадак - даданне/выдаленне элемента роўна пасярэдзіне.

Your micro-benchmark gives systematic error. You need to uniformly or randomly distribute the add/remove location. Or carry out macro-benchmarking with real-life complex & challenging apps.

An interesting read on the challenge of creating an accurate micro-benchmark: Java theory and practice: Anatomy of a flawed microbenchmark

4
дададзена

Я перапісаў праграму Мацей, каб выпадковым чынам выбраць метад і запусціць масіў з 50 выпрабаванняў для кожнага метаду. Калі ўзяць у сярэдняе хуткай паловы выпрабаванняў у кожнай катэгорыі, то вынік заключаецца ў наступным:

LL: 570
AL: 120
LL итератора: 1
AL итератора: 60

LL итератор сапраўды займае шмат часу сартавальнік. У горшым выпадку гэта падзенне прадукцыйнасці ў 15 разоў як за кошт прагрэву (першы цыкл) і дс (выпадковыя шыпы на неўпарадкаваных дадзеных).

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;

public class TestList {

    public static void main(String... args) {
        final int MAX_VAL = 10000;
        int[] currentIndex = {0, 0, 0, 0};
        int[] remaining = {50, 50, 50, 50};
        int[][] sequence = new int[4][50];

        while (keepWorking(remaining)) { //run 50 tests for each case at random

            int currentMethod = chooseMethod(remaining); //choose case. Probability is higher for tests with less trials

            switch (currentMethod) { //run a test based on the choice
                case 0:
                    sequence[currentMethod][currentIndex[currentMethod]] = getLL(MAX_VAL);
                    break;
                case 1:
                    sequence[currentMethod][currentIndex[currentMethod]] = getAL(MAX_VAL);
                    break;
                case 2:
                    sequence[currentMethod][currentIndex[currentMethod]] = getLLIt(MAX_VAL);
                    break;
                default:
                    sequence[currentMethod][currentIndex[currentMethod]] = getALIt(MAX_VAL);
                    break;
            }

            remaining[currentMethod]--;
            currentIndex[currentMethod]++;
        }

        for (int[] ar : sequence) {
            Arrays.sort(ar);
        }

        System.out.println("Time (us\nLL    \tAL\tLL incr\t AL incr");
        for (int i = 0; i < sequence[0].length; i++) {
            System.out.println(sequence[0][i] + "\t" + sequence[1][i] + "\t" + sequence[2][i] + "\t" + sequence[3][i]);
        }
        System.out.println("\nTime normalized to fastest run of a method\nLL\tAL\tLL incr\t AL incr");
        for (int i = 0; i < sequence[0].length; i++) {
            System.out.print(i);
            for (int j = 0; j < sequence.length; j++) {  //to 4
                int a = sequence[j][i]/(sequence[j][0]/100); //to keep result within the scope of int
                System.out.print("\t" + a);
            }
            System.out.println();
        }
    }

    public static boolean keepWorking(int[] remaining) {

        for (int i = 0; i < remaining.length; i++) {
            if (remaining[i] > 0) {
                return true;
            }
        }
        return false;
    }

    public static int chooseMethod(int[] rem) {
        int[] bins = new int[rem.length];
        for (int i = 0; i < rem.length; i++) {
            for (int j = i; j < rem.length; j++) {
                bins[j] += rem[i];
            }
        }
        int randomNum = new Random().nextInt(bins[rem.length - 1]);
        for (int i = 0; i < bins.length; i++) {
            if (randomNum < bins[i]) {
                return i;
            }
        }
        return -1;
    }

    public static int getLL(int MAX_VAL) {

        List linkedList = new LinkedList<>();
        for (int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
        }
        long time = System.nanoTime();

        for (int i = 0; i < MAX_VAL; i++) {
            linkedList.add(MAX_VAL/2, i);
        }
        return (int) (System.nanoTime() - time)/1000;
    }

    public static int getAL(int MAX_VAL) {

        List arrayList = new ArrayList<>(MAX_VAL);
        for (int i = 0; i < MAX_VAL; i++) {
            arrayList.add(i);
        }
        long time = System.nanoTime();
        for (int i = 0; i < MAX_VAL; i++) {
            arrayList.add(MAX_VAL/2, i);
        }
        return (int) (System.nanoTime() - time)/1000;
    }

    public static int getLLIt(int MAX_VAL) {

        List linkedList = new LinkedList<>();
        for (int i = 0; i < MAX_VAL; i++) {
            linkedList.add(i);
        }

        long time = System.nanoTime();

        ListIterator li = linkedList.listIterator(MAX_VAL/2);
        for (int i = 0; i < MAX_VAL; i++) {
            li.add(i);
        }
        return (int) (System.nanoTime() - time)/1000;
    }

    public static int getALIt(int MAX_VAL) {

        List arrayList = new ArrayList<>(MAX_VAL);
        for (int i = 0; i < MAX_VAL; i++) {
            arrayList.add(i);
        }

        long time = System.nanoTime();
        ListIterator ali = arrayList.listIterator(MAX_VAL/2);
        for (int i = 0; i < MAX_VAL; i++) {
            ali.add(i);
        }
        return (int) (System.nanoTime() - time)/1000;
    }
}
1
дададзена

так як ArrayList захоўвае значэння паслядоўна такім чынам 1: хутчэй, каб дадаць значэння (проста дадайце значэнне ў апошнім індэксе) 2: павольней, каб абнавіць або выдаліць (давядзецца прайсці ўвесь спіс, перш чым мы пяройдзем да вузла)

паколькі спіс масіва працуе на канцэпцыі LinkedList 1: павольней ўстаўкі (павінна знаходзіць спасылку на прад або наступнае значэнне) 2: хутчэй у Updation (як толькі дакладны вузел можа быць дасягнута з дапамогай спасылкі)

this link can be referred

0
дададзена

Некаторыя варта выконваць асцярожнасць пры простым прафілявання, як гэта:

  • Вываз смецця можа адбыцца ў непрадказальнае час запаволення непрадказальная частка.
  • JRE павольней, калі ён спачатку пачынаецца і пазней «падагравае».

Каб абыйсці гэтую праблему, зрабіць прафіляванне у цыкле, паўтараючы абодва выпадку шмат разоў лепш у выпадковым парадку, і прыняць тыпавыя значэння, а не канечнасці. Часам гэта паставіць розныя вынікі.

0
дададзена

ў ідэальным сцэнары вы заўсёды ўстаўляць у адсартаваны спіс. Спачатку вы знайсці індэкс ўстаўкі з дапамогай бінарнага механізм пошуку, а затым ўставіць у гэты індэкс. Акрамя таго, пры гэтым вы не можаце выкарыстоўваць адзін і той жа ListIterator ўвесь час. У вас будзе ўсталяваць итератор Новы індэкс месцазнаходжаньня evrytime. Такім чынам, у гэтым рэжыме рэальнага жыццёвага сцэнара, які ўстаўкі хутчэй.

0
дададзена