ArrayList 대 LinkedList

ArrayList 대 LinkedList

---

나는 이것에 대한 이전 게시물 을 따르고 있었다 .

LinkedList 용

• get은 O (n)입니다.
• add는 O (1)입니다.
• 제거는 O (n)입니다.
• Iterator.remove는 O (1)입니다.

ArrayList의 경우

• get은 O (1)
• add는 O (1) 상각되지만 배열 크기를 조정하고 복사해야하므로 O (n) 최악의 경우입니다.
• 제거는 O (n)입니다.

그래서 이것을 살펴봄으로써 5000000 요소에 대해 내 컬렉션에 순차적으로 삽입 LinkedList하면 ArrayList.

그리고 반복하여 컬렉션에서 요소를 가져와야한다면, 즉 중간에 요소를 잡지 않고 여전히 LinkedList`ArrayList를 능가합니다.

이제 위의 두 진술을 확인하기 위해 아래에 샘플 프로그램을 작성했습니다.하지만 위의 진술이 틀린 것으로 판명 된 것에 놀랐습니다.

ArrayListLinkedlist두 경우 모두에서 능가 합니다. LinkedList컬렉션에서 추가하고 가져 오는 것 보다 시간이 덜 걸렸습니다 . 내가 잘못하고있는 것이 있습니까? 아니면 5000000 크기의 컬렉션에 대한 초기 진술 LinkedList과 ArrayList맞지 않는 내용 이 있습니까?

요소 수를 50000 개로 줄이면 LinkedList성능이 향상되고 초기 명령문이 적용 되기 때문에 크기를 언급했습니다 .

long nano1 = System.nanoTime();

List<Integer> arr = new ArrayList();
for(int i = 0; i < 5000000; ++i) {
    arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );

for(int j : arr) {
    ;
}
System.out.println( (System.nanoTime() - nano1) );

long nano2 = System.nanoTime();

List<Integer> arrL = new LinkedList();
for(int i = 0; i < 5000000; ++i) {
    arrL.add(i);
}
System.out.println( (System.nanoTime() - nano2) );

for(int j : arrL) {
    ;
}
System.out.println( (System.nanoTime() - nano2) );

---

big-O 복잡성은 점근 적 동작을 설명하며 실제 구현 속도를 반영하지 않을 수 있습니다. 각 작업의 속도가 아니라 목록의 크기에 따라 각 작업의 비용이 증가하는 방식을 설명합니다. 예를 들어, 다음 구현 add은 O (1)이지만 빠르지 않습니다.

public class MyList extends LinkedList {
    public void add(Object o) {
        Thread.sleep(10000);
        super.add(o);
    }
}

귀하의 경우 ArrayList가 내부 버퍼 크기를 상당히 공격적으로 증가시켜 많은 재 할당이 발생하지 않기 때문에 잘 수행되고 있다고 생각합니다. 버퍼의 크기를 조정할 필요가없는 경우 ArrayList는 더 빠른 adds 를 갖습니다 .

이러한 종류의 프로파일 링을 수행 할 때도 매우주의해야합니다. 예열 단계를 수행하고 (따라서 JIT는 결과에 영향을주지 않고 일부 최적화를 수행 할 수있는 기회를 갖도록) 프로파일 링 코드를 변경하고 여러 실행에 걸쳐 결과를 평균화하는 것이 좋습니다.

private final static int WARMUP = 1000;
private final static int TEST = 1000;
private final static int SIZE = 500000;

public void perfTest() {
    // Warmup
    for (int i = 0; i < WARMUP; ++i) {
        buildArrayList();
    }
    // Test
    long sum = 0;
    for (int i = 0; i < TEST; ++i) {
        sum += buildArrayList();
    }
    System.out.println("Average time to build array list: " + (sum / TEST));
}

public long buildArrayList() {
    long start = System.nanoTime();
    ArrayList a = new ArrayList();
    for (int i = 0; i < SIZE; ++i) {
        a.add(i);
    }
    long end = System.nanoTime();
    return end - start;
}

... same for buildLinkedList

( sum넘칠 수 있으며 사용하는 것이 더 나을 수 있습니다 System.currentTimeMillis()).

컴파일러가 빈 get루프를 최적화 할 수도 있습니다 . 루프가 실제로 올바른 코드가 호출되는지 확인하는 작업을 수행하는지 확인하십시오.

---

이것은 나쁜 벤치 마크 IMO입니다.

• jvm을 워밍업하려면 루프에서 여러 번 반복해야합니다.
• 반복 루프에서 무언가를해야하거나 최적화 된 배열이 될 수 있습니다.
• ArrayList비용이 많이 듭니다. 한 번에 구성하는 ArrayList것처럼 new ArrayList(500000)구성했다면 모든 할당이 상당히 저렴할 것입니다 (사전 할당 백업 어레이 하나).
• 메모리 JVM을 지정하지 않았습니다. -xMs == -Xmx (모든 항목이 사전 할당 됨)로 실행되어야하며 GC가 트리거되지 않을만큼 충분히 높아야합니다.
• 이 벤치 마크는 LinkedList의 가장 불쾌한 측면 인 랜덤 액세스를 다루지 않습니다. (반복자가 반드시 같은 것은 아닙니다). 무작위 선택으로 대규모 컬렉션 크기의 10 %를 피드 list.get하면 연결 목록이 첫 번째 또는 마지막 요소가 아닌 다른 것을 잡는 데 끔찍하다는 것을 알게 될 것입니다.

arraylist의 경우 : jdk get은 예상되는 것입니다.

public E get(int index) {
    RangeCheck(index);

    return elementData[index];
}

(기본적으로 인덱스 배열 요소를 반환합니다.,

연결 목록의 경우 :

public E get(int index) {
    return entry(index).element;
}

비슷해 보입니까? 좀 빠지는. 항목은 기본 배열이 아닌 메소드이며 수행해야하는 작업을 확인하십시오.

private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

그렇습니다. say를 요청 list.get(250000)하면 머리에서 시작하여 다음 요소를 반복적으로 반복해야합니다. 250000 액세스 정도 (더 적은 액세스가되는 것에 따라 헤드 또는 테일에서 시작하는 코드에 최적화가 있습니다.)

---

ArrayList는 LinkedList보다 간단한 데이터 구조입니다. ArrayList에는 인접한 메모리 위치에 포인터의 단일 배열이 있습니다. 배열이 할당 된 크기 이상으로 확장 된 경우에만 다시 만들어야합니다.

LinkedList는 노드 체인으로 구성됩니다. 각 노드는 할당되어 분리되어 있으며 다른 노드에 대한 앞뒤 포인터가 있습니다.

이것은 무엇을 의미합니까? 중간에 삽입, 연결, 삭제 등을 할 필요가 없다면 ArrayList는 일반적으로 더 빠를 것입니다. 메모리 할당이 덜 필요하고 참조의 위치가 훨씬 더 좋습니다 (프로세서 캐싱에 중요 함).

---

얻은 결과가 "big O"특성과 모순되지 않는 이유를 이해합니다. 우리는 첫 번째 원칙으로 돌아 가야합니다. 즉 정의 .

f (x) 및 g (x)를 실수의 일부 하위 집합에 정의 된 두 함수로 지정합니다. 하나 쓰기

f(x) = O(g(x)) as x -> infinity

충분히 큰 x 값에 대해 f (x)는 절대 값에서 g (x)를 곱한 상수입니다. 즉, f (x) = O (g (x)) 양의 실수 M과 실수 x0이있는 경우에만

|f(x)| <= M |g(x)| for all x > x_0.

많은 맥락에서 변수 x가 무한대로 갈수록 성장률에 관심이 있다는 가정은 언급되지 않은 채로 남아 있으며, f (x) = O (g (x))라고 더 간단하게 씁니다.

따라서 문 은 N이 무한대가되는 경향이 _있으므로 크기 N 목록에 add1 is O(1)대한 add1작업 의 시간 비용이 상수 C _add1 을 향하는 경향이 있음을 의미합니다.

그리고 성명서 add2 is O(1) amortized over N operations, means는 N이 무한대가되는 경향이 있으므로 일련의 N 연산 중 하나의 평균 시간 비용이 add2상수 C _add2 를 향하는 경향이 있다는 것입니다.

말하지 않은 것은 C _add1 및 C _add2 상수가 무엇인지 입니다. 사실 LinkedList의이 벤치 마크에서 ArrayList를보다 느린 이유는 C의 것입니다 _ADD1은 C의보다 큰 _ADD2 .

교훈은 big O 표기법이 절대적 또는 상대적 성능을 예측하지 않는다는 것입니다. 제어 변수가 매우 커짐에 따라 성능 함수 의 모양 만 예측 됩니다. 이것은 알아두면 유용하지만 알아야 할 모든 것을 알려주지는 않습니다.

---

big-O-notation은 절대 타이밍이 아니라 상대적 타이밍에 관한 것이며 한 알고리즘의 수를 다른 알고리즘과 비교할 수 없습니다.

동일한 알고리즘이 튜플 수의 증가 또는 감소에 어떻게 반응하는지 정보 만 얻을 수 있습니다.

한 알고리즘은 한 작업에 1 시간, 두 작업에 2 시간이 걸리며 O (n)이고 다른 알고리즘도 O (n)이며 한 작업에 1 밀리 초, 두 작업에 2 밀리 초가 걸립니다.

JVM으로 측정하는 경우 또 다른 문제는 핫스팟 컴파일러의 최적화입니다. do-nothing-loop는 JIT 컴파일러에 의해 제거 될 수 있습니다.

세 번째로 고려해야 할 사항은 캐시를 사용하고 동시에 가비지 수집을 실행하는 OS와 JVM입니다.

---

LinkedList에 대한 좋은 사용 사례를 찾기가 어렵습니다. Dequeu 인터페이스 만 사용해야하는 경우 ArrayDeque를 사용해야합니다. 실제로 List 인터페이스를 사용해야하는 경우 LinkedList가 임의의 요소에 액세스 할 때 실제로 제대로 작동하지 않기 때문에 항상 ArrayList를 사용하라는 제안을 자주 듣게됩니다.

불행히도 목록의 시작 또는 중간에있는 요소를 제거하거나 삽입해야하는 경우 ArrayList에는 성능 문제가 있습니다.

그러나 ArrayList와 LinkedList의 장점을 결합한 GapList라는 새로운 목록 구현이 있습니다. ArrayList와 LinkedList 모두에 대한 드롭 인 대체물로 설계되었으므로 List 및 Deque 인터페이스를 모두 구현합니다. 또한 ArrayList에서 제공하는 모든 공용 메서드가 구현됩니다 (ensureCapacty, trimToSize).

GapList의 구현은 인덱스별로 요소에 대한 효율적인 임의 액세스를 보장하며 (ArrayList가 수행하는 것처럼) 동시에 효율적으로 목록의 앞뒤에 요소를 추가하고 제거합니다 (LinkedList가 수행하는 것처럼).

GapList에 대한 자세한 정보는 http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list 에서 찾을 수 있습니다 .

---

1) 기본 데이터 구조 ArrayList와 LinkedList의 첫 번째 차이점은 ArrayList가 Array에 의해 지원되고 LinkedList가 LinkedList에 의해 지원된다는 사실입니다. 이것은 성능에 더 많은 차이를 가져올 것입니다.

2) LinkedList는 Deque를 구현합니다. ArrayList와 LinkedList의 또 다른 차이점은 List 인터페이스와 별도로 LinkedList는 add () 및 poll () 및 기타 여러 Deque 함수에 대한 선입 선출 작업을 제공하는 Deque 인터페이스도 구현한다는 것입니다. 3) ArrayList에 요소 추가 ArrayList에 요소를 추가하는 것은 Array의 크기 조정을 트리거하지 않으면 O (1) 동작이며,이 경우 O (log (n))가되고, 반면 LinkedList에 요소를 추가합니다. 탐색이 필요하지 않으므로 O (1) 작업입니다.

4) 위치 에서 요소 제거 특정 인덱스에서 요소를 제거하기 위해 예를 들어 remove (index)를 호출하여 ArrayList는 O (n)에 가깝게 복사 작업을 수행하고 LinkedList는 해당 지점으로 이동해야합니다. 그것은 O (n / 2), 근접성에 따라 어느 방향에서든 횡단 할 수 있기 때문입니다.

5) ArrayList 또는 LinkedList 반복 반복은 LinkedList 및 ArrayList 모두에 대한 O (n) 연산이며 여기서 n은 요소의 수입니다.

6) 위치에서 요소 검색 get (index) 연산은 ArrayList에서 O (1)이고 LinkedList에서 O (n / 2)는 해당 항목까지 트래버스해야하기 때문에입니다. 그러나 Big O 표기법에서 O (n / 2)는 상수를 무시하기 때문에 O (n)입니다.

7) Memory LinkedList는 데이터를 저장하기위한 정적 중첩 클래스 인 래퍼 객체 인 Entry를 사용하며, ArrayList는 데이터를 Array에 저장하는 동안 다음과 이전의 두 노드를 사용합니다.

따라서 Array가 한 Array에서 다른 Array로 콘텐츠를 복사 할 때 크기 조정 작업을 수행하는 경우를 제외하고는 LinkedList보다 ArrayList의 경우 메모리 요구 사항이 적습니다.

Array가 충분히 크면 해당 지점에서 많은 메모리를 사용하고 가비지 수집을 트리거하여 응답 시간을 늦출 수 있습니다.

ArrayList와 LinkedList 사이의 위의 모든 차이점에서 보면 remove () 또는 get ()보다 자주 add () 작업을 수행하는 경우를 제외하고 거의 모든 경우에서 ArrayList가 LinkedList보다 더 나은 선택입니다.

특히 연결 목록은 해당 위치의 참조를 내부적으로 유지하고 O (1) 시간에 액세스 할 수 있기 때문에 시작 또는 끝에서 요소를 추가하거나 제거하는 경우 ArrayList보다 연결 목록을 수정하는 것이 더 쉽습니다.

즉, 요소를 추가하려는 위치에 도달하기 위해 연결된 목록을 탐색 할 필요가 없습니다.이 경우 추가는 O (n) 연산이됩니다. 예를 들어, 링크 된 목록 중간에 요소를 삽입하거나 삭제합니다.

제 생각에는 Java에서 대부분의 실용적인 목적으로 LinkedList보다 ArrayList를 사용하십시오.

---

O 표기법 분석은 중요한 정보를 제공하지만 한계가 있습니다. 정의에 따라 O 표기법 분석은 모든 작업을 실행하는 데 거의 동일한 시간이 걸리는 것으로 간주하며 이는 사실이 아닙니다. @seand가 지적했듯이 연결된 목록은 내부적으로 더 복잡한 논리를 사용하여 요소를 삽입하고 가져옵니다 (소스 코드를 살펴보면 IDE에서 Ctrl + 클릭 할 수 있음). ArrayList는 내부적으로 요소를 배열에 삽입하고 가끔씩 크기를 늘릴 필요가 있습니다 (실제로는 o (n) 작업이더라도 매우 빠르게 수행 할 수 있음).

건배

---

추가 또는 제거를 2 단계 작업으로 분리 할 수 ​​있습니다.

LinkedList : 인덱스 n에 요소를 추가하면 포인터를 0에서 n-1로 이동할 수 있으며 소위 O (1) 추가 작업을 수행 할 수 있습니다. 제거 작업은 동일합니다.

---

ArraryList : ArrayList는 RandomAccess 인터페이스를 구현합니다. 즉, O (1)의 요소에 액세스 할 수 있습니다.
인덱스 n에 요소를 추가하면 O (1)의 n-1 인덱스로 이동하여 n-1 이후의 요소를 이동하고 n 슬롯에 요소를 추가 할 수 있습니다.
이동 작업은라는 기본 메서드에 의해 수행되며 System.arraycopy매우 빠릅니다.

public static void main(String[] args) {

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

    List<Integer> linkList = new LinkedList<Integer>();

    long start = 0;
    long end = 0;
    Random random = new Random();

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(random.nextInt(100000), 7);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(random.nextInt(100000), 7);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(0, 7);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(0, 7);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,index == size-1" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,index == size-1" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.remove(Integer.valueOf(random.nextInt(100000)));
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList remove ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.remove(Integer.valueOf(random.nextInt(100000)));
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList remove ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.remove(0);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList remove ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.remove(0);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList remove ,index == 0" + (end - start));

}

참고 URL : https://stackoverflow.com/questions/5846183/arraylist-vs-linkedlist