collections 언제 Java에서 ArrayList를 통해 LinkedList를 사용할 수 있습니까?





15 Answers

지금까지 아무도 LinkedListArrayList 보다 "많이 더 많다"는 일반적인 합의 이외에는이 목록 각각의 메모리 사용량을 처리하지 못했습니다. 그래서 두 목록이 N 개의 null 참조를 차지하는 양을 정확하게 나타 내기 위해 숫자를 계산했습니다 .

참조는 상대 시스템에서 32 또는 64 비트 (null 일 때도 있음)이므로 32 비트 및 64 비트 LinkedListsArrayLists 대해 4 세트의 데이터를 포함 시켰습니다.

참고 : ArrayList 행에 표시된 크기는 트리밍 된 목록입니다 . 실제로 ArrayListArrayList 배열 용량은 일반적으로 현재 요소 수보다 큽니다.

참고 2 : (감사합니다 BeeOnRope) JDK6 중반부터 CompressedOops가 기본값으로 설정되었으므로 64 비트 시스템의 경우 아래의 값은 기본적으로 해당 32 비트 카운터와 기본적으로 일치합니다 (물론 특별히 지정하지 않은 경우).

결과는 LinkedListArrayList 보다 훨씬 더 많은 것을 특히 명확하게 보여줍니다. 특히 요소 수가 매우 높습니다. 메모리가 중요한 요소라면 LinkedLists .

제가 사용하는 공식은 제가 잘못한 것을 해줬는지 알려주고 그것을 고칠 것입니다. 'b'는 32 또는 64 비트 시스템에서 4 또는 8이고 'n'은 요소 수입니다. mod의 이유는 java의 모든 객체가 모두 사용되었는지 여부에 관계없이 8 바이트 공간의 배수를 차지하기 때문입니다.

ArrayList :

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList :

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)
java arraylist collections linked-list

나는 항상 단순하게 다음과 같이 사용했다.

List<String> names = new ArrayList<>();

인터페이스를 이식성을 위한 형식 이름으로 사용하므로 이러한 질문을 할 때 코드를 재 작업 할 수 있습니다.

LinkedListArrayList 이상으로 사용해야하는 경우는 언제입니까?




약 10 년 동안 매우 대규모의 SOA 웹 서비스에 대한 운영 성능 엔지니어링을 해오 고있는 누군가로서, 나는 ArrayList에 비해 LinkedList의 동작을 선호합니다. LinkedList의 정상 상태 처리량이 더 나빠서 하드웨어를 더 많이 구입할 수는 있지만 ArrayList가 압력을 받으면 클러스터의 응용 프로그램이 거의 동시에 배열을 확장 할 수 있으며 배열 크기가 크면 응답 성이 떨어질 수 있습니다 앱이 중단되고 압력이 가해지는 동안 파국적 인 행동입니다.

마찬가지로 기본 처리량 가비지 수집기의 앱에서 더 나은 처리량을 얻을 수 있지만 10GB 힙이있는 Java 앱을 얻으면 풀 GC 동안 25 초 동안 앱 잠금을 해제하여 SOA 앱의 시간 초과 및 오류를 유발할 수 있습니다 SLA가 너무 자주 발생하면 SLA가 손상됩니다. CMS 수집기가 더 많은 리소스를 사용하고 동일한 원시 처리량을 얻지는 못하지만 예측 가능한 대기 시간이 더 짧기 때문에 훨씬 더 나은 선택입니다.

ArrayList는 성능이 의미하는 것이 처리량이고 대기 시간을 무시할 수있는 경우에만 성능을위한 더 나은 선택입니다. 직장에서의 경험에서 나는 최악의 대기 시간을 무시할 수 없다.




그래, 나도 알아, 이건 고대의 질문이지만, 나는 내 두 센트를 던질거야.

LinkedList는 거의 항상 잘못된 선택이며 성능에 현명한 선택입니다. LinkedList가 호출되는 매우 구체적인 알고리즘이 있습니다. 그러나 매우 드물고 알고리즘은 대개 LinkedList가 탐색 한 요소를 비교적 빠르게 목록에 삽입하고 삭제할 수있는 기능에 따라 달라집니다 ListIterator를 사용합니다.

LinkedList가 ArrayList를 능가하는 일반적인 사용 사례가 하나 있습니다. 그러나 LinkedList 대신 성능이 목표라면 ArrayBlockingQueue (큐 크기의 상한을 미리 결정할 수 있고 모든 메모리를 앞에 할당 할 수있는 경우) 또는이 CircularArrayList 구현을 고려해야합니다 . (예, 2001 년 이후입니다. 따라서이를 일반화해야하지만, 최근 JVM의 기사에서 인용 된 것과 비교할 수있는 성능 비율을 얻었습니다)




맞음 또는 틀린 : 로컬에서 테스트를 실행하고 직접 결정하십시오!

편집 / 제거는 ArrayList 보다 LinkedList 에서 빠릅니다.

Array 에 의해 뒷받침되는 ArrayList 는 크기가 두 배가되어야하며 대용량 응용 프로그램에서는 더 나쁩니다.

아래는 각 작업에 대한 단위 테스트 결과입니다. 타이밍은 나노초 단위로 표시됩니다.

Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

코드는 다음과 같습니다.

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}



1) 검색 : ArrayList 검색 작업은 LinkedList 검색 작업에 비해 매우 빠릅니다. ArrayList의 get (int index)은 LinkedList의 성능이 O (n) 인 동안 O (1)의 성능을 제공합니다.

이유 : ArrayList는 요소에 대한 인덱스 기반 시스템을 유지 관리하므로 배열 데이터 구조를 암시 적으로 사용하므로 목록의 요소를 더 빠르게 검색 할 수 있습니다. 반면에 LinkedList는 요소를 검색하기 위해 모든 요소를 ​​순회해야하는 이중 연결 목록을 구현합니다.

2) 삭제 : ArrayList가 가변적 인 성능을 제공하는 동안 LinkedList 제거 작업은 O (1) 성능을 제공합니다. 최악의 경우 O (n), 최상의 경우 O (1) (마지막 요소를 제거하는 동안) .

결론 : LinkedList 요소 삭제는 ArrayList에 비해 빠릅니다.

이유 : LinkedList의 각 요소는 두 개의 포인터 (주소)를 유지합니다.이 포인터는 목록의 두 인접 요소를 가리 킵니다. 따라서 제거는 제거 될 노드의 두 인접 노드 (요소)에서 포인터 위치의 변경 만 필요합니다. In ArrayList에서 제거 된 요소에 의해 생성 된 공간을 채우기 위해 모든 요소를 ​​이동해야합니다.

3) 삽입 성능 : LinkedList 추가 메소드는 O (1) 성능을 제공하지만 ArrayList는 최악의 경우 O (n)을 제공합니다. 이유는 제거에 설명 된 것과 같습니다.

4) 메모리 오버 헤드 : ArrayList는 인덱스와 요소 데이터를 유지하지만 LinkedList는 요소 데이터와 인접 노드에 대한 두 개의 포인터를 유지하므로 LinkedList에서 메모리 소비가 상대적으로 높습니다.

이 클래스들 사이 에는 다음과 같은 몇 가지 유사점 이 있습니다.

ArrayList와 LinkedList는 모두 List 인터페이스의 구현입니다. 그들은 둘 다 요소 삽입 순서를 유지합니다. 즉, ArrayList 및 LinkedList 요소를 표시하는 동안 결과 집합은 요소가 List에 삽입 된 것과 동일한 순서를 갖게됩니다. 이 두 클래스는 비 동기화되어 있으며 Collections.synchronizedList 메서드를 사용하여 명시 적으로 동기화 할 수 있습니다. 이러한 클래스에 의해 돌려 주어진 iterator와 listIterator는 패스트 패스트입니다. 반복자의 작성 후, 반복자의 독자적인 remove 메소드 또는 add 메소드 이외의 방법으로리스트가 구조적으로 변경되면, 반복자는 ConcurrentModificationException를 Throw합니다.

LinkedList를 언제 사용하고 ArrayList를 사용해야합니까?

1) 위에서 설명한 바와 같이 삽입 및 제거 작업은 ArrayList (O (n))와 비교하여 LinkedList에서 좋은 성능 (O (1))을 제공합니다. 따라서 응용 프로그램에서 자주 추가 및 삭제해야하는 요구 사항이있는 경우 LinkedList가 최선의 선택입니다.

2) 검색 (메서드 가져 오기) 작업은 ArrayList (O (1))에서는 빠르지 만 LinkedList (O (n))에서는 수행되지 않습니다. 따라서 추가 및 제거 작업이 적고 검색 작업 요구 사항이 많으면 ArrayList가 최선의 방법입니다.




Joshua Bloch, LinkedList의 저자 :

LinkedList를 실제로 사용하는 사람이 있습니까? 나는 그것을 썼고 결코 그것을 사용하지 않는다.

링크 : https://twitter.com/joshbloch/status/583813919019573248

나는 다른 답변들처럼 유익하지 않다는 답변에 대해 유감 스럽지만, 그것이 가장 흥미롭고 자명 할 것이라고 생각했습니다.




나는 이것이 오래된 게시물이지만, 솔직히 아무도 그 LinkedList도구에 대해 언급 한 것을 믿을 수 없다 Deque. Deque(와 Queue) 의 메소드를 보라 . 당신이 공정한 비교를 원하는 경우, 실행 시도 LinkedListArrayDeque와 기능에 대한-기능 비교를.




LinkedList와 ArrayList wrt를 아래의 매개 변수와 비교해 보겠습니다.

1. 구현

ArrayList 는리스트 인터페이스의 사이즈 변경 가능한 배열 구현이며,

LinkedList 는 목록 인터페이스의 이중 연결 목록 구현입니다.

2. 성과

  • get (int index) 또는 검색 작업

    ArrayList get (int index) 연산은 일정 시간, 즉 O (1)에서 실행되는 while

    LinkedList get (int index) 작업 실행 시간은 O (n)입니다.

    ArrayList 가 LinkedList보다 빠르다는 이유는 ArrayList 가 내부적으로 배열 데이터 구조를 사용하므로 요소에 인덱스 기반 시스템을 사용하기 때문입니다.

    LinkedList 는 지정된 요소 인덱스에서 노드를 검색하기 위해 처음부터 끝까지 (어느 쪽이든 가깝게) 반복 할 때 해당 요소에 대한 인덱스 기반 액세스를 제공하지 않습니다.

  • 삽입 () 또는 추가 (객체) 연산

    LinkedList의 삽입 은 일반적으로 ArrayList와 비교하여 빠릅니다. LinkedList에서 추가 또는 삽입은 O (1) 연산입니다.

    ArrayList에 있는 동안 배열이 전체 즉 최악의 경우 ArrayList O (n)에서 추가 작업의 런타임을 만드는 배열 크기를 조정하고 요소를 새 배열에 복사하는 추가 비용이 있습니다. 그렇지 않으면 O (1)입니다. .

  • remove (int) 연산

    LinkedList의 제거 작업은 일반적으로 ArrayList 즉 O (n)과 동일합니다.

    에서 LinkedList의 두 오버로드 제거 방법이 있습니다. 하나는 목록의 머리 부분을 제거하고 상수 시간 O (1)에서 실행되는 매개 변수없이 remove ()입니다. LinkedList의 다른 오버로드 된 remove 메소드는 remove (int) 또는 remove (Object)이며, 이는 매개 변수로 전달 된 Object 또는 int를 제거합니다. 이 메서드는 LinkedList가 객체를 발견하고 원래 목록에서 링크를 끊을 때까지 LinkedList를 탐색합니다. 따라서이 메소드 런타임은 O (n)입니다.

    ArrayList에 있는 동안 remove (int) 메서드는 이전 배열의 요소를 새로운 업데이트 된 배열에 복사하기 때문에 런타임은 O (n)입니다.

3. 역 반복기

LinkedList 는 descendingIterator ()를 사용하여 반대 방향으로 반복 할 수 있습니다. while

ArrayList 에는 descendingIterator ()가 없으므로 ArrayList에 대해 역방향으로 반복 처리하기 위해 자체 코드를 작성해야합니다.

4. 초기 용량

생성자가 오버로드되지 않으면 ArrayList 는 초기 용량 10의 빈 목록을 만듭니다.

LinkedList 는 초기 용량없이 빈 목록 만 구성합니다.

5. 메모리 오버 헤드

LinkedList 의 노드가 다음 노드와 이전 노드의 주소를 유지해야하기 때문에 LinkedList의 메모리 오버 헤드 가 ArrayList와 비교할 때 많습니다. 동안

에서는 ArrayList를 각 인덱스 만 실제 객체 (데이터)를 보유하고있다.

Source







그것은 당신이리스트에서 더 많은 일을 할 것인지에 달려 있습니다.

ArrayList인덱싱 된 값에 액세스하는 것이 더 빠릅니다. 객체를 삽입하거나 삭제할 때 훨씬 나 빠집니다.

자세한 내용을 보려면 배열과 링크 된 목록의 차이점에 대해 설명하는 기사를 읽으십시오.




연결된 목록 (다른 대답에서 읽지 않은)의 중요한 기능은 두 목록의 연결입니다. 배열의 경우 이것은 O (n) (일부 재 할당의 + 오버 헤드)이며 연결된 목록은 O (1) 또는 O (2)뿐입니다 ;-)

중요 : Java의 LinkedList경우이 사실이 아닙니다! Java에서 연결된 목록에 대한 빠른 concat 메서드가 있습니까?를 참조하십시오 .




ArrayList그리고 LinkedList모두 구현 List interface및 그 방법과 결과는 거의 동일하다. 그러나 요구 사항에 따라 다른 것보다 더 나은 것을 만드는 몇 가지 차이점이 있습니다.

ArrayList 대 LinkedList

1) Search: ArrayList검색 작업은 검색 작업에 비해 매우 빠릅니다 LinkedList. get(int index)in ArrayList은 성능이 O(1)떨어지는 동안 LinkedList성능 을 제공합니다 O(n).

Reason: ArrayList배열 데이터 구조를 암시 적으로 사용하므로 목록에있는 요소를 검색 할 때 인덱스 데이터 구조를 더 빠르게 사용하므로 요소에 대해 인덱스 기반 시스템을 유지 관리합니다. 다른 쪽에서 LinkedList는 요소를 검색하기 위해 모든 요소를 ​​순회해야하는 이중 연결 목록을 구현합니다.

2) Deletion: LinkedList제거 작업은 O(1)성능을 ArrayList제공 하는 동시에 가변적 인 성능을 제공합니다 : O(n)최악의 경우 (첫 번째 요소를 제거하는 동안) 그리고 O(1)최선의 경우 (마지막 요소를 제거하는 동안).

결론 : LinkedList 요소 삭제는 ArrayList에 비해 빠릅니다.

이유 : LinkedList의 각 요소는 목록의 두 인접 요소를 가리키는 두 개의 포인터 (주소)를 유지합니다. 따라서 제거는 제거 될 노드의 두 인접 노드 (요소)에서 포인터 위치의 변경 만 필요합니다. In ArrayList에서 제거 된 요소에 의해 생성 된 공간을 채우기 위해 모든 요소를 ​​이동해야합니다.

3) 최악의 경우에 주는 Inserts Performance: LinkedList방법은 O(1)성능을 ArrayList제공합니다 O(n). 이유는 제거에 대해 설명 된 것과 같습니다.

4) Memory Overhead: ArrayList는 요소 데이터를 LinkedList유지 하면서 인덱스와 요소 데이터를 관리하고 이웃 노드에 대해서는 두 개의 포인터

따라서 LinkedList에서의 메모리 소비는 상대적으로 높습니다.

이 클래스들 사이에는 다음과 같은 몇 가지 유사점이 있습니다.

  • ArrayList와 LinkedList는 모두 List 인터페이스의 구현입니다.
  • 그들은 둘 다 요소 삽입 순서를 유지합니다. 즉, ArrayList 및 LinkedList 요소를 표시하는 동안 결과 집합은 요소가 List에 삽입 된 것과 동일한 순서를 갖게됩니다.
  • 이 두 클래스는 비 동기화되어 있으며 Collections.synchronizedList 메서드를 사용하여 명시 적으로 동기화 할 수 있습니다.
  • iteratorlistIterator이러한 클래스에 의해 반환은 fail-fast(리스트가 구조적으로 반복자의 작성 후에 이외 방법으로 변경되면 iterator's자신의 제거 또는 방법을 추가, 반복자 것이다 ).throwConcurrentModificationException

LinkedList를 언제 사용하고 ArrayList를 사용해야합니까?

  • 위에서 설명한대로 삽입 및 제거 작업은 (O(1))LinkedList비해 좋은 성능 을 제공 합니다 ArrayList(O(n)).

    따라서 응용 프로그램에서 자주 추가 및 삭제해야하는 요구 사항이있는 경우 LinkedList가 최선의 선택입니다.

  • 검색 ( get method) 작업은 빠르게 수행 Arraylist (O(1))되지만LinkedList (O(n))

    따라서 추가 및 제거 작업이 적고 검색 작업 요구 사항이 많으면 ArrayList가 최선의 방법입니다.




TL, 현대적인 컴퓨터 아키텍처로 인한 DRArrayList 은 거의 모든 가능한 유스 케이스에 대해 훨씬 더 효율적입니다. 따라서 LinkedList매우 독특하고 극단적 인 몇 가지 경우를 제외하고는 피해야합니다.

이론적으로 LinkedList에는 O (1)이 있습니다. add(E element)

또한 목록의 중간에 요소를 추가하는 것이 매우 효율적입니다.

LinkedList는 캐시 적대적 데이터 구조 이므로 실습은 매우 다릅니다 . 성능 POV에서 - 캐시 친화적 인LinkedList 것보다 성능이 좋은 경우는 거의 없습니다 . ArrayList

다음은 임의의 위치에 요소를 삽입하는 벤치 마크 테스트 결과입니다. 당신이 볼 수 있듯이, 훨씬 더 효율적이라면 배열리스트는 이론적으로리스트의 중간에있는 각각의 삽입 은 배열 의 n 이후 요소를 "이동"해야 할 것이다. (더 낮은 값이 더 좋다) :

차세대 하드웨어 (더 크고 효율적인 캐시)로 작업하면 결과가 훨씬 결정적입니다.

LinkedList는 동일한 작업을 수행하는 데 훨씬 많은 시간이 필요합니다. source 코드

이것에는 크게 두 가지 이유가 있습니다.

  1. 주로 -의 노드가 LinkedList메모리에 무작위로 흩어져 있습니다. RAM ( "Random Access Memory")은 실제로 랜덤하지 않으며 메모리 블록을 캐쉬로 가져와야합니다. 이 작업은 시간이 걸리며 이러한 페치가 자주 발생하면 캐시의 메모리 페이지를 항상 바꿔야합니다. -> 캐시 실패 -> 캐시가 효율적이지 않습니다. ArrayList요소는 연속 메모리에 저장됩니다. 이는 현대 CPU 아키텍처가 정확히 최적화하고있는 것입니다.

  2. 보조 LinkedList 포인터는 뒤로 / 앞으로 포인터를 보유해야하는데, 이는 저장된 값 대비 메모리 소비의 3 배를 의미합니다 ArrayList.

DynamicIntArray , btw는 IntObject가 아닌 (기본 유형)을 보유하는 사용자 정의 ArrayList 구현 이므로 모든 데이터가 실제로 인접하여 저장되므로 훨씬 효율적입니다.

기억해야 할 핵심 요소는 메모리 블록을 가져 오는 비용이 단일 메모리 셀을 액세스하는 비용보다 더 중요하다는 것입니다. 이것이 바로 1MB의 순차 메모리가 여러 메모리 블록에서이 양의 데이터를 읽는 것보다 최대 400 배 빠른 속도를 보이는 이유입니다.

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

출처 : 모든 프로그래머가 알아야 할 대기 시간 번호

요점을 더욱 명확하게하기 위해 목록의 시작 부분에 요소를 추가하는 벤치 마크를 확인하십시오. 이것은 in-theory LinkedList가 정말로 빛나야 하는 유스 케이스이며, ArrayList좋지 않은 결과 나 더 나쁜 경우의 결과를 제시해야합니다.

참고 : 이것은 C ++ Std 라이브러리의 벤치 마크입니다. 그러나 C ++ 및 Java 결과가 표시된 이전 경험은 매우 유사합니다. 소스 코드

순차적 대량 메모리를 복사하는 것은 최신 CPU가 최적화 한 작업입니다. 이론을 바꾸고 실제로 다시 만들 ArrayList거나 Vector훨씬 더 효율적입니다.

크레딧 : 여기에 게시 된 모든 벤치 마크는 Kjell Hedström에 의해 작성되었습니다 . 그의 블로그 에서 더 많은 데이터를 찾을 수 있습니다.




remove ()와 insert () 모두 ArrayLists와 LinkedLists 모두에 대해 O (n)의 런타임 효율성을가집니다. 그러나 선형 처리 시간의 배경은 두 가지 다른 이유에서 비롯됩니다.

ArrayList에서 O (1)의 요소를 얻지 만 다음 요소를 모두 변경해야하므로 실제로 제거하거나 삽입하면 O (n)이됩니다.

LinkedList에서 원하는 요소에 실제로 도착하려면 O (n)이 필요합니다. 원하는 인덱스에 도달 할 때까지 맨 처음부터 시작해야하기 때문입니다. 실제로 제거 또는 삽입은 상수입니다. remove ()에 대한 참조 1 개와 insert ()에 대한 참조 2 개를 변경해야하기 때문입니다.

어느 쪽이 삽입과 제거에 더 빠를 것인가는 그것이 일어나는 곳에 달려 있습니다. 우리가 상대적으로 적은 요소들을 거쳐야하기 때문에 LinkedList가 더 빨라질 것입니다. 우리가 끝까지 가까워지면 ArrayList는 더 빠를 것입니다. 왜냐하면 우리는 일정 시간 내에 거기에 도착하고 그 뒤의 나머지 요소를 변경해야하기 때문입니다. 가운데에서 정확하게 끝나면 LinkedList가 더 빨라집니다. 왜냐하면 n 개의 요소를 통과하는 것이 n 개의 값을 이동하는 것보다 빠르기 때문입니다.

보너스 : ArrayList에 대해 O (1) 메서드를 만드는 방법은 없지만 실제로 LinkedLists에서이 작업을 수행하는 방법이 있습니다. 도중에 엘리먼트를 제거하고 삽입하는 전체 목록을 살펴보고 싶다고 가정 해 봅시다. 일반적으로 LinkedList를 사용하여 각 요소에 대해 처음부터 시작하고, 현재 작업중인 요소를 반복자를 사용하여 "저장할"수도 있습니다. Iterator의 도움으로 LinkedList에서 작업 할 때 remove () 및 insert ()에 대한 O (1) 효율성을 얻습니다. LinkedList가 ArrayList보다 항상 좋은 점을 알고있는 유일한 성능 이점으로 생각합니다.




여기서 본 테스트 중 하나는 테스트를 한 번 수행하는 것입니다. 그러나 내가 알아 차린 것은 당신이이 테스트를 여러 번 실행해야하고 결과적으로 시간이 수렴된다는 것입니다. 기본적으로 JVM은 예열해야합니다. 특정 유스 케이스의 경우, 항목을 추가 / 제거하여 마지막 항목이 약 500 개까지 증가해야했습니다. 내 테스트 에서 약 50,000 명의 NS에 도착하여 약 90,000 NS ... LinkedList로 연결되는 링크 LinkedList가 더 빨리 나타났습니다 ArrayList. 아래 코드를 참조하십시오.

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}



Related