ArrayDeque가 LinkedList보다 나은 이유

ArrayDeque가 LinkedList보다 나은 이유

---

Java의 ArrayDeque가 Deque 인터페이스를 구현할 때 Java의 LinkedList보다 나은 이유 를 이해하려고합니다 .

코드에서 ArrayDeque를 사용하는 사람은 거의 없습니다. 누군가 ArrayDeque가 구현되는 방식을 더 밝히면 도움이 될 것입니다.

이해하면 더 확실하게 사용할 수 있습니다. JDK 구현이 헤드 및 테일 참조를 관리하는 방식에 대해 명확하게 이해할 수 없었습니다.

---

연결된 구조는 각 요소에서 캐시 누락으로 반복되는 최악의 구조 일 수 있습니다. 게다가 그들은 더 많은 메모리를 소비합니다.

양쪽 끝을 추가 / 제거해야하는 경우 ArrayDeque가 연결된 목록보다 훨씬 좋습니다. 각 요소에 대한 임의 액세스는 순환 큐에 대해 O (1)입니다.

연결된 목록의 유일한 더 나은 작업은 반복 중에 현재 요소를 제거하는 것입니다.

---

주요 성능 병목 현상 LinkedList은 deque의 끝까지 밀어 넣을 때마다 구현이 본질적으로 JVM / OS와 관련된 새로운 링크 된 목록 노드를 할당하므로 비용이 많이 든다는 것입니다. 또한 어느 끝에서나 터질 때마다 내부 노드 LinkedList가 가비지 수집 대상 이 되어 더 많은 작업을 수행합니다. 또한 링크 된 목록 노드가 여기 저기 할당되므로 CPU 캐시를 사용하면 큰 이점이 없습니다.

관심이 있다면, 요소를 추가 ArrayList하거나 ArrayDeque상각 된 일정한 시간에 실행 한다는 증거가 있습니다. 이것을 참조하십시오 .

---

ArrayDeque Java 6의 새로운 기능이므로 많은 코드 (특히 이전 Java 버전과 호환되는 프로젝트)에서이 코드를 사용하지 않습니다.

삽입 할 각 항목에 대해 노드를 할당하지 않기 때문에 경우에 따라 더 낫습니다. 대신 모든 요소가 거대한 배열에 저장되며 가득 차면 크기가 조정됩니다.

---

를 비판하는 모든 사람들은 Java 6을 사용 하고 LinkedList있던 다른 모든 사람들이 Java 6 이전에 사용되었고 대부분의 책에서 시작으로 가르치기 때문에 대부분의 시간을 사용한다고 생각합니다.ListArrayListLinkedList

그렇다고 맹목적으로 LinkedList또는 ArrayDeque측면을 취한다는 의미는 아닙니다 . 알고 싶다면 Brian이 수행 한 아래 벤치 마크를 살펴보십시오 .

테스트 설정은 다음을 고려합니다.

• 각 테스트 개체는 500 자 문자열입니다. 각 문자열은 메모리에서 다른 객체입니다.
• 테스트하는 동안 테스트 배열의 크기가 달라집니다.
• 각 배열 크기 / 대기열 구현 조합에 대해 100 개의 테스트가 실행되고 평균 테스트 시간이 계산됩니다.
• 각 테스트는 각 큐에 모든 객체를 채우고 모두 제거하는 것으로 구성됩니다.
• 밀리 초 단위로 시간을 측정하십시오.

검사 결과:

• 10,000 개 미만의 요소에서 LinkedList 및 ArrayDeque 테스트는 모두 평균 1ms 수준에서 테스트되었습니다.
• 데이터 집합이 커질수록 ArrayDeque와 LinkedList 평균 테스트 시간의 차이가 커집니다.
• 9,900,000 요소의 테스트 크기에서 LinkedList 방식은 ArrayDeque 방식보다 ~ 165 % 길었습니다.

그래프:

테이크 아웃 :

• 요구 사항이 100 또는 200 요소를 저장하는 경우 대기열 중 하나를 사용하여 큰 차이를 만들지 않습니다.
• 그러나 모바일에서 개발하는 경우 엄격한 메모리 제한으로 인해 목록이 필요할 수있는 최대 용량 ArrayList또는 ArrayDeque최대 용량을 정확하게 추측 할 수 있습니다.
• 인터페이스를 구현하지 않기 때문에 특히 LinkedList사용하기로 결정할 때 신중하게 사용하여 작성된 많은 코드가 있습니다 (충분히 큰 이유라고 생각합니다). 코드베이스가 List 인터페이스와 광범위하게 통신하고 아마도로 이동하기로 결정했을 수 있습니다 . 내부 구현에 사용하는 것이 좋습니다.ArrayDequeListArrayDeque

---

ArrayDeque에서 요소에 액세스하는 것은 요소에 액세스하기 위해 O (1)을 사용하는 LinkedList에 비해 항상 빠릅니다. 연결 목록에서 마지막 요소를 찾으려면 O (N)이 필요합니다.

ArrayDeque는 Linked List와 달리 다음 노드를 추적 할 필요가 없으므로 메모리 효율적입니다.

자바 문서에 따르면, 다음과 같이 인용되었습니다.

ArrayDeque는 Deque 인터페이스의 크기 조정 가능 배열 구현입니다. 어레이 대기열에는 용량 제한이 없습니다. 사용을 지원하기 위해 필요에 따라 커집니다. 스레드 안전하지 않습니다. 외부 동기화가 없으면 여러 스레드의 동시 액세스를 지원하지 않습니다. 널 요소는 금지됩니다. 이 클래스는 스택으로 사용될 때 Stack보다 빠르며 대기열로 사용될 때 LinkedList보다 빠를 것입니다.

이 두 가지를 벤치마킹 하면 ArrayDeque가 더 빠릅니다.

---

비록 ArrayDeque<E>및하면 LinkedList<E>모두 구현 한 Deque<E>인터페이스가 있지만 기본적으로 개체의 ArrayDeque 어레이를 사용하는 E[]것이 일반적으로 머리와 꼬리 요소의 위치에 대한 인덱스를 사용하므로, 그 개체의 내부 요소를 유지하기 위해.

한마디로 Deque (모든 Deque의 방법과 함께)처럼 작동하지만 배열의 데이터 구조를 사용합니다. 어느 쪽이 더 좋은지에 관해서는 어떻게 그리고 어디서 사용하는지에 달려 있습니다.

---

요소에 액세스하기위한 ArrayDeque의 시간 복잡도는 O (1)이고 LinkList의 경우 시간이 O (N)이며 마지막 요소에 액세스합니다. ArrayDeque는 스레드로부터 안전하지 않으므로 수동으로 동기화해야 여러 스레드를 통해 액세스 할 수 있으므로 더 빠릅니다.

참고 URL : https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist