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 와 LinkedList 가 Deque 인터페이스를 구현하고 있지만 구현이 다릅니다.
주요 차이점 :
-
의 ArrayDeque 클래스의 크기 조정 어레이 구현 Deque와의 인터페이스와 LinkedList의의 클래스는리스트 구현
-
NULL 요소는 LinkedList에 추가 할 수 있지만 ArrayDeque 에는 없습니다.
-
ArrayDeque 는 양쪽 끝에서 추가 및 제거 작업에 LinkedList 보다 효율적 이며 LinkedList 구현은 반복 중에 현재 요소를 제거하는 데 효율적입니다.
-
LinkedList의의 구현은보다 많은 메모리가 소비 의 ArrayDeque을
따라서 NULL 요소를 지원할 필요가 없으며 메모리 양이 적고 양쪽 끝에 요소를 추가 / 제거하는 효율성을 찾고 ArrayDeque 가 가장 좋습니다.
자세한 내용은 설명서 를 참조하십시오.
답변
비록 ArrayDeque<E>및하면 LinkedList<E>모두 구현 한 Deque<E>인터페이스가 있지만 기본적으로 개체의 ArrayDeque 어레이를 사용하는 E[]것이 일반적으로 머리와 꼬리 요소의 위치에 대한 인덱스를 사용하므로, 그 개체의 내부 요소를 유지하기 위해.
한마디로 Deque (모든 Deque의 방법과 함께)처럼 작동하지만 배열의 데이터 구조를 사용합니다. 어느 쪽이 더 좋은지에 관해서는 어떻게 그리고 어디서 사용하는지에 달려 있습니다.
답변
항상 그런 것은 아닙니다.
예를 들어, 아래의 경우 leetcode 103에 따른 linkedlist것보다 성능이 좋습니다 ArrayDeque.
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> rs=new ArrayList<>();
if(root==null)
return rs;
// ? here ,linkedlist works better
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
boolean left2right=true;
while(!queue.isEmpty())
{
int size=queue.size();
LinkedList<Integer> t=new LinkedList<>();
while(size-->0)
{
TreeNode tree=queue.remove();
if(left2right)
t.add(tree.val);
else
t.addFirst(tree.val);
if(tree.left!=null)
{
queue.add(tree.left);
}
if(tree.right!=null)
{
queue.add(tree.right);
}
}
rs.add(t);
left2right=!left2right;
}
return rs;
}
}