개요
Java 언어에서는 데이터 수집 프레임 워크가 제공되며, 이는 목록 및 세트와 같은 일부 초록 데이터 유형을 정의합니다. 각 초록 데이터 유형에는 고유 한 구현이 있으며 기본 계층은 ArrayList 및 LinkedList와 같은 다른 구현 방법을 채택합니다.
또한 Java는 데이터 세트를 가로 지르는 몇 가지 다른 방법을 제공합니다. 개발자는 다양한 기본 구현에서 특성, 해당 행사 및 성능을 명확하게 이해해야합니다. 이 내용을 아래에서 자세히 분석하겠습니다.
데이터 요소는 메모리에 어떻게 저장됩니까?
메모리에는 데이터 요소에 대한 두 가지 주요 저장 방법이 있습니다.
1. 순차적 인 저장소, 랜덤 액세스 (직접 액세스) :
이러한 방식으로, 인접한 데이터 요소는 인접한 메모리 주소에 저장되며 전체 메모리 주소는 연속적입니다. 메모리 주소는 요소의 위치에 따라 직접 계산하여 직접 읽을 수 있습니다. 특정 위치에서 요소를 읽는 평균 시간 복잡성은 O (1)입니다. 일반적으로 배열을 기반으로 구현 된 세트만이 기능을 갖습니다. Arraylist는 Java로 표시됩니다.
2. 체인 저장, 순차적 액세스 :
이러한 방식으로, 각 데이터 요소는 메모리의 인접한 위치에 있지 않아야하며, 각 데이터 요소에는 다음 요소의 메모리 주소가 포함됩니다. 메모리 주소는 요소의 위치에 따라 직접 계산할 수 없으며 요소는 순서대로 만 읽을 수 있습니다. 특정 위치에서 요소를 읽는 평균 시간 복잡성은 O (n)입니다. 주로 링크 된 목록으로 표시됩니다.
Linkedlist는 Java로 표시됩니다.
Java에서 제공되는 트래버스 방법은 무엇입니까?
1. 카운터를 기반으로 루프 트래버스를위한 전통 :
Traverser 자체는 컬렉션 외부의 카운터를 유지 한 다음 각 위치의 요소를 순서대로 읽고 마지막 요소를 읽을 때 중지됩니다. 가장 중요한 것은 그 위치에 따라 요소를 읽는 것입니다. 이것은 또한 가장 원시적 인 수집 트래버스 방법입니다.
작문 방법은 다음과 같습니다.
for (int i = 0; i <list.size (); i ++) {list.get (i);}2. 반복자 트래버스, 반복자 :
반복자는 원래 OO 설계 패턴으로, 주요 목적은 다른 데이터 세트의 특성을 차단하고 컬렉션의 인터페이스를 균일하게 통과하는 것입니다. OO 언어로서 Java는 자연스럽게 컬렉션에서 반복자 모드를 지원합니다.
작문 방법은 다음과 같습니다.
iterator iterator = list.iterator (); while (iterator.hasnext ()) {iterator.next ();}3. Foreach Loop Traversal :
명시 적으로 선언 된 반복자 및 카운터가 차단됩니다.
장점 : 코드는 간결하며 오류가 발생하지 않습니다.
단점 : 간단한 트래버스 만 수행 할 수 있으며 트래버스 프로세스 중에 데이터 컬렉션을 작동 (삭제, 교체) 할 수 없습니다.
작문 방법은 다음과 같습니다.
for (ElementType 요소 : list) {}각 트래버스 방법의 구현 원리는 무엇입니까?
1. 카운터를 기반으로 루프 트래버스를위한 전통 :
Traverser 자체는 컬렉션 외부의 카운터를 유지 한 다음 각 위치의 요소를 순서대로 읽고 마지막 요소를 읽을 때 중지됩니다. 가장 중요한 것은 그 위치에 따라 요소를 읽는 것입니다.
2. 반복자 트래버스, 반복자 :
각 특정 구현 데이터 세트는 일반적으로 해당 반복기를 제공해야합니다. 루프 용 전통과 비교하여 반복자는 명시 적 트래버스 카운터입니다. 따라서 순차적 인 컬렉션 저장을 기반으로 한 반복자는 위치별로 데이터에 직접 액세스 할 수 있습니다. 체인 스토리지 세트를 기반으로 한 반복자는 정상 구현을 위해 현재 트래버스 위치를 저장해야합니다. 그런 다음 현재 위치에 따라 포인터를 앞뒤로 움직입니다.
3. Foreach Loop Traversal :
소형화 된 바이트 코드에 따르면, Foreach는 반복자 메소드를 사용하여이를 구현하지만 Java 컴파일러는 이러한 코드를 생성하는 데 도움이되었습니다.
각 트래버스 방법은 다른 저장 방법에 대해 어떻게 수행됩니까?
1. 카운터를 기반으로 루프 트래버스를위한 전통 :
요소의 위치에 기초하기 때문에 위치별로 읽으십시오. 따라서 순차적 스토리지의 경우 특정 위치에서 읽기 요소의 평균 시간 복잡성이 O (1)이기 때문에 전체 세트를 가로 지르는 평균 시간 복잡성은 O (n)이라는 것을 알 수 있습니다. 체인 저장의 경우, 특정 위치에서의 판독 요소의 평균 시간 복잡성은 O (n)이기 때문에 전체 세트를 가로 지르는 평균 시간 복잡성은 O (n2) (n의 제곱)입니다.
배열리스트 코드 위치별로 읽기 : 요소 위치별로 직접 읽습니다.
과도 객체 [] elementData; public e get (int index) {rangeCheck (index); return ElementData (index);} e ElementData (int index) {return (e) elementData [index];}LinkedList 코드 위치별로 읽기 : 매번 0 번째 요소에서 뒤로 읽어야합니다. 실제로, 그것은 또한 내부적으로 작은 최적화를 만들었습니다.
일시적인 int size = 0; 과도 노드 <E> 첫 번째; 과도 노드 <E> 마지막; public e get (int index) {int index (index) {checkElementIndex (index); return node (index) .item;} node <e> 노드 (int index) {if (index <(size >> 1)) {// 쿼리 위치는 연결 목록의 첫 번째 절반에 있습니다. <index; i ++ x = x.next; return x;} else {// 쿼리 위치는 링크 된 목록의 후반에 있으며, <e> x = last; for (int i = size-1; i> index; i-)를 찾습니다.2. 반복자 트래버스, 반복자 :
그런 다음 RandomAccess 유형의 컬렉션에는 그다지 의미가 없습니다. 대신 일부 추가 작업에는 추가 실행 시간이 추가됩니다. 그러나 Iterator는 현재 트래버스 위치를 유지하기 때문에 순차적 인 액세스 컬렉션에 큰 의미가 있습니다. 따라서 횡단 할 때마다 컬렉션의 첫 번째 요소에서 찾아보기 시작할 필요가 없습니다. 포인터를 하나씩 움직입니다. 이러한 방식으로, 전체 세트를 가로 지르는 시간 복잡성은 O (n)으로 감소된다;
(이것은 링크 사전 목록 만 사용됩니다) 링크드 목록의 반복자는 내부적으로 구현되며, 이는 현재 트래버스 위치를 유지 한 다음 포인터를 작동시키기 위해 다음을 움직입니다.
암호:
public e next () {checkforcomodification (); if (! hasnext ())이 새로운 nosuchelementexception (); lastreturned = next; next = next.next; nextindex ++; return lasturned.item;} problice () {checkforcomodification (); if (! hasprevious ()); hasprevious (); (다음 == null)? 마지막 : Next.prev; NextIndex-; return lastreturned.item;}}3. Foreach Loop Traversal :
Java Bytecode를 분석함으로써 Foreach의 내부 구현 원리가 반복기를 통해 구현되지만이 반복기는 Java 컴파일러에 의해 생성되므로 수동으로 작성할 필요가 없습니다. 그러나 유형 변환 점검은 매번 필요하기 때문에 반복자보다 조금 더 오래 걸립니다. 시간 복잡성은 반복자의 시간 복잡성과 동일합니다.
반복기를 사용한 바이트 코드 :
코드 : 새로운 # // 클래스 java/util/arraylistdupinvokespecial # // 메소드 java/util/arraylist. "<init>":() vastore_aload_invokeinterface #, // interfacemethod java/util/list.terator :() ljava/util/iterator; Store_goTo alotho aLoado aLokeTo # Interfacemethod Java/util/iterator.next :() ljava/lang/object; popaload_invokeinterface #, // interfacemethod java/util/iterator.hasnext :() Zifne Return
Foreach의 바이트 코드 사용 :
코드 : 새로운 # // 클래스 java/util/arraylistdupinvokespecial # // 메소드 java/util/arraylist. "<init>":() vastore_aload_invokeinterface #, // interfacemethod java/util/list.terator :() ljava/util/iterator; Store_goTo alotho aLoado aLokeTo # 인터페이스 메드 Java/util/iterator.next :() ljava/lang/object; checkcast # // class loop/modelastore_aload_invokeinterface #, // interfacemethod java/util/iterator.hasnext :() Zifne Return
각 트래버스 방법은 어떤 경우에 적용됩니까?
1. 카운터를 기반으로 루프 트래버스를위한 전통 :
순차적 스토리지 : 높은 읽기 성능. 트래버스 순차 스토리지 컬렉션에 적합합니다.
체인 저장 : 시간 복잡성이 너무 높고 체인 저장 컬렉션을 통과하는 데 적합하지 않습니다.
2. 반복자 트래버스, 반복자 :
순차적 인 저장소 : 시간이 너무 신경 쓰지 않으면이 방법을 선택하는 것이 좋습니다. 결국, 코드는 더 간결하고 외부의 문제를 방지합니다.
체인 저장 : 큰 의미가 있습니다. 평균 시간 복잡성은 O (n)으로 감소되므로 매우 매력적 이므로이 트래버스 방법이 권장됩니다.
3. Foreach Loop Traversal :
Foreach는 코드를 더 간결하게 만듭니다. 그러나 몇 가지 단점이 있습니다. 즉, 트래버스 프로세스 중에 데이터 컬렉션 (삭제 등)을 작동 할 수 없으므로 경우에는 사용되지 않습니다. 또한 반복자를 기반으로 구현되지만 유형 변환 문제로 인해 반복기를 직접 사용하는 것보다 조금 느리게됩니다. 다행히도 시간 복잡성은 동일합니다. 따라서 선택하는 방법, 위의 두 가지 방법을 참조하여 타협을 선택하십시오.
Java의 모범 사례는 무엇입니까?
Java Data Collection Framework에서 RandomAccess 인터페이스가 제공되며 방법이없고 태그 만 제공됩니다. 일반적으로 목록 인터페이스 구현에 의해 목록의 구현이 임의의 액세스를 지원하는지 여부를 표시하기 위해 사용됩니다.
데이터 세트는이 인터페이스를 구현하므로 임의의 액세스를 지원하고 위치별로 읽기 요소의 평균 시간 복잡성은 O (1)입니다. 예를 들어, ArrayList.
이 인터페이스가 구현되지 않으면 임의의 액세스가 지원되지 않음을 의미합니다. 예를 들어 LinkedList입니다.
따라서 JDK 개발자들 도이 문제를 발견 한 것 같습니다. 권장되는 방법은 먼저 임의의 액세스가 지원되는지, 즉 RandomAccess의 인스턴스를 나열하는지 결정하는 것입니다.
예를 들어:
if (randomaccess의 인스턴스를 목록) {// 루프 트래버스에 전통적인 사용. } else {// 반복자 또는 foreach를 사용합니다. }위의 것은 편집기가 소개 한 Java Traversal Collection 방법 (구현 원리, 알고리즘 성능 및 해당 행사)의 분석입니다. 나는 그것이 모두에게 도움이되기를 바랍니다!