머리말
이 기사를 통해 5 가지 트래버스 목록, 각각의 성능 및 Foreach 및 Iterator의 구현을 이해하고 Arraylist 및 LinkedList 구현에 대한 이해를 심화시킬 수 있습니다. 아래에서 함께 살펴 보겠습니다.
1. 목록을 가로 지르는 5 가지 방법
1. 각 루프마다
목록 <integer> list = new arraylist <integer> (); for (integer j : list) {// J}}2. 디스플레이 호출 수집 반복자
목록 <integer> list = new ArrayList <integer> (); for (iterator <integer> iterator = list.iterator (); iterator.hasnext ();) {iterator.next ();}또는
목록 <integer> list = new arraylist <integer> (); iterator <integer> iterator = list.iterator (); while (iterator.hasnext ()) {iterator.next ();}3. 첨자 증분 루프의 첨자, 종료 조건은 size () 함수가 호출 될 때마다 비교하고 판단하는 것입니다.
목록 <integer> list = new ArrayList <integer> (); for (int j = 0; j <list.size (); j ++) {list.get (j);}4. 종료 조건이 size ()와 같은 합계 인 임시 변수의 첨자, 비교 및 판단의 증분주기
목록 <integer> list = new arraylist <integer> (); int size = list.size (); for (int j = 0; j <size; j ++) {list.get (j);}5. 첨자 감소 사이클
목록 <integer> list = new arraylist <integer> (); for (int j = list.size () -1; j> = 0; j-) {list.get (j);}5 가지 트래버스 목록의 성능 테스트 및 비교
다음은 성능 테스트 코드로, 다양한 트래버스 방법의 Arraylist 및 다양한 순서의 링크리스트에 소요되는 시간을 출력합니다.
패키지 cn.trinea.java.test; import java.text.decimalformat; import java.util.arraylist; import java.util.calendar; import java.util.iterator; import java.util.linkedlist; import java.util.list;/** javalooptest * @author ww.r. 2013-10-28 */public class javalooptest {public static void main (String [] args) {System.out.print ( "ArrayList의 루프 성능 비교"); LOOPLISTCOMPARE (GetArrayLists (10000, 100000, 100000, 9000000)); System.out.print ( "/r/n/r/ncompare 루프 루프 링크리스트 성능"); looplistcompare (getLinkedLists (100, 1000, 10000, 10000)); } public static list <integer> [] getArraylists (int ... sizearray) {list <integer> [] listarray = new arraylist [sizearray.length]; for (int i = 0; i <listarray.length; i ++) {int size = sizearray [i]; 목록 <integer> list = new ArrayList <integer> (); for (int j = 0; j <size; j ++) {list.add (j); } listArray [i] = list; } return listArray; } public static list <integer> [] getLinkedLists (int ... sizearray) {list <integer> [] listArray = new LinkedList [sizearray.length]; for (int i = 0; i <listarray.length; i ++) {int size = sizearray [i]; 목록 <integer> list = new LinkedList <integer> (); for (int j = 0; j <size; j ++) {list.add (j); } listArray [i] = list; } return listArray; } public static void looplistcompare (list <integer> ... listarray) {printheader (listarray); 긴 시작, 종료 시간; // (int i = 0; i <listarray.length; i ++) {list <integer> list = listArray [i]; starttime = calendar.getInstance (). gettimeInmillis (); for (integer j : list) {// a a us} endtime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "각각", endtime -starttime); } // (int i = 0; i <listarray.length; i ++) {list <integer> list = listArray [i]; starttime = calendar.getInstance (). gettimeInmillis (); // iterator <integer> iterator = list.iterator (); // while (iterator.hasnext ()) {// iterator.next (); //} for (iterator <integer> iterator = list.iterator (); iterator.hasnext ();) {iterator.next (); } endTime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "반복자 용", endtime -starttime); } // (int i = 0; i <listarray.length; i ++) {list <integer> list = listArray [i]; starttime = calendar.getInstance (). gettimeInmillis (); for (int j = 0; j <list.size (); j ++) {list.get (j); } endTime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "for list.size ()", endtime -starttime); } // (int i = 0; i <listarray.length; i ++) {list <integer> list = listArray [i]; starttime = calendar.getInstance (). gettimeInmillis (); int size = list.size (); for (int j = 0; j <size; j ++) {list.get (j); } endTime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "size = list.size ()", endtime -starttime); } // (int i = 0; i <listarray.length; i ++) {list <integer> list = listArray [i]; starttime = calendar.getInstance (). gettimeInmillis (); for (int j = list.size () -1; j> = 0; j-) {list.get (j); } endTime = calendar.getInstance (). getTimeInmillis (); printCostTime (i, listarray.length, "for j-", endtime-starttime); }} static int first_column_length = 23, Other_column_length = 12, Total_column_length = 71; 정적 최종 Decimalformat comma_format = new Decimalformat ( "#, ###"); public static void printheader (list <integer> ... listarray) {printrowdivider (); for (int i = 0; i <listarray.length; i ++) {if (i == 0) {StringBuilder sb = new StringBuilder (). Append ( "List Size"); while (sb.length () <first_column_length) {sb.append ( ");} system.out.print (sb);} stringBuilder sb = new StringBuilder (). Append ("| ") .append (comma_format.forray [i] .size ()); SB. Append.out.out.print (sb); (sb.length () <Total_column_length) {sb.append ( "-");} public static void printcosttime (int i, int size, string casename) {if (i == 0) {stringbuilder <column_length) {SB.Append ( ""); System.out.print (SB); }}} 추신 : 실행이 in thread “main” java.lang.OutOfMemoryError: Java heap space 에서는 main 기능에서 list size 의 크기를 줄이십시오.
getArrayLists 함수는 size 다른 배열리스트를 반환하고 getLinkedLists 함수는 size 다른 링크 사전 목록을 반환합니다.
loopListCompare 함수는 위의 Traversal 방법 1-5를 사용하여 각 목록 배열에서 목록을 통과합니다 (다양한 크기 목록 포함).
print 로 시작하는 기능은 출력 도우미 기능입니다.
테스트 환경은 Windows 7 32 비트 시스템 3.2g 듀얼 코어 CPU 4G 메모리, Java 7, Eclipse -XMS512M -XMX512M입니다.
최종 테스트 결과는 다음과 같습니다.
compare loop performance of ArrayList-----------------------------------------------------------------------list size | 10,000 | 100,000 | 1,000,000 | 10,000,000 ----------------------------------------------------------------------------------------------------- 1ms | 3ms | 14ms | 152 ms -----------------------------------------------------------------------for iterator | 0ms | 1ms | 12ms | 114 ms -----------------------------------------------------------------------for list.size() | 1ms | 1ms | 13ms | 128 ms -----------------------------------------------------------------------for size = list.size() | 0ms | 0ms | 6ms | 62ms --------------------------------------------------------------------------------------------- 0ms | 1ms | 6ms | 63 ms ----------------------------------------------------------------------- compare loop performance of LinkedList-----------------------------------------------------------------------list size | 100 | 1,000 | 10,000 | 100,000 ------------------------------------------------------------------------------------------------------------------------------------------------------------------- 0ms | 1ms | 1ms | 2 ms -----------------------------------------------------------------------for iterator | 0ms | 0ms | 0ms | 2 ms -----------------------------------------------------------------------for list.size() | 0ms | 1ms | 73ms | 7972 ms -----------------------------------------------------------------------for size = list.size() | 0ms | 0ms | 67ms | 8216 MS -------------------------------------------------------------------------- | 0ms | 1ms | 67ms | 8277 ms ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
첫 번째 표는 ArrayList의 비교 결과이며 두 번째 표는 LinkedList의 비교 결과입니다.
테이블의 수평 방향은 동일한 트래버스 방법에서 다른 크기의 목록의 순회 시간 소비이며, 수직 방향은 동일한 목록의 다른 트래버스 방법의 횡선 소비 시간입니다.
추신 : 목록의 첫 번째 트래버스는 시간이 조금 더 걸리므로 for each 의 결과는 약간 벗어납니다. 테스트 코드의 여러 유형을 교체하면 for each for iterator 의 경우에 가깝습니다.
트래버스 방법의 성능 테스트 결과 분석
1. 소개를위한
Foreach는 Java SE5.0에서 도입 한 매우 강력한 루프 구조입니다. for (Integer j : list) for each int in list 읽어야합니다.
for (Integer j : list) 구현은 거의 동일합니다
iterator <integer> iterator = list.iterator (); while (iterator.hasnext ()) {integer j = iterator.next ();}Foreach 코드는 쓰기가 간단하며 초기 값, 종료 값 및 국경간에 신경을 쓸 필요가 없으므로 실수를하기가 쉽지 않습니다.
2. Arraylist Traversal 방법의 결과 분석
에이. Arraylist 크기가 100,000이되기 전에 5 개의 트래버스 방법의 시간 소비는 거의 동일했습니다.
비. 100,000 이후, 네 번째 및 다섯 번째 트래버스 방법은 처음 3 개보다 빠르며 Get 메소드는 반복자 방법보다 낫습니다.
int size = list.size (); for (int j = 0; j <size; j ++) {list.get (j);} 임시 변수 크기로 list.size() 교체하는 것이 더 나은 성능입니다. Iterator 의 구현을 살펴보고 ArrayList에서 메소드를 get 십시오.
개인 클래스 ITR은 반복자 <e> {int cursor를 구현합니다. // int lastret = -1을 반환 할 다음 요소의 색인; // 마지막 요소의 색인이 반환되었습니다. -1 int expectModCount = modCount가없는 경우; public boolean hasnext () {return cursor! = size; } @SuppressWarnings ( "선택 취소") public e next () {checkforcomodification (); int i = 커서; if (i> = size) 새 nosuchelementException ()을 던지십시오. Object [] ElementData = ArrayList.this.elementData; if (i> = ElementData.length) Throw New ConcurrentModificationException (); 커서 = i + 1; return (e) ElementData [lastret = i]; }…} public e get (int index) {rangecheck (index); return elementData (색인);} 이것으로부터 우리는 get 및 Iterator 의 next 함수가 데이터를 직접 위치시킴으로써 요소를 얻는다는 것을 알 수 있지만, 몇 가지 더 판단이 더 있습니다.
기음. 위에서부터, 우리는 수천만 명의 배열 목록에서도 몇 가지 트래버스 방법의 차이는 약 50ms에 불과하며 시간은 거의 100,000입니다. Foreach의 장점을 고려할 때, 우리는 Traversal에 대한 Foreach의 간단한 방법을 사용하도록 선택할 수 있습니다.
3. Linkedlist Traversal 방법의 결과 분석
에이. LinkedList의 크기가 10,000에 가까운 경우 get 메소드 및 Iterator 방법은 이미 약 2 배 정도 다릅니다. 100,000이면 Iterator 방법의 성능이 Get 메소드보다 훨씬 우수합니다.
반복자의 구현을 살펴보고 LinkedList에서 메소드를 get 십시오.
Private Class Listitr는 ListITerator <e> {개인 노드 <e> lastreturned = null; 개인 노드 <e> 다음; 개인 int NextIndex; Private int exclingModCount = modCount; Listitr (int index) {// assert ispositionIndex (index); 다음 = (색인 == 크기)? NULL : 노드 (인덱스); NextIndex = index; } public boolean hasnext () {return nextIndex <size; } public e next () {checkforcomodification (); if (! hasnext ())은 새로운 nosuchelementexception ()을 던지십시오. lastreturned = 다음; 다음 = next.next; NextIndex ++; 반환 lastreturned.item; }…} public e get (int index) {CheckElementIndex (index); return node (index) .item;} /*** 지정된 요소 인덱스에서 (널) 노드를 반환합니다. */node <e> 노드 (int index) {// asselementIndex (index); if (index <(size >> 1)) {node <e> x = 첫 번째; for (int i = 0; i <index; i ++) x = x.next; 반환 x; } else {node <e> x = 마지막; for (int i = size-1; i> index; i-) x = x.prev; 반환 x; }} 위의 코드에서 LinkedList Ierator의 next 함수가 다음 포인터를 통해 다음 요소를 빠르게 가져 와서 반환한다는 것을 알 수 있습니다. GET 메소드는 처음부터 인덱스 첨자까지 가로 지르고 O (n)의 시간 복잡성을 가진 요소를 찾으면 트래버스의 시간 복잡성이 O (n2)에 도달합니다.
따라서 get 사용을 피하기 위해 Linkedlist의 Traversal에 Foreach를 사용하는 것이 좋습니다.
4. ArrayList 및 LinkedList Traversal Method의 결과에 대한 비교 분석
위의 순서에서, 그것은 또한 foreach loop traversal이며, Arraylist 및 Linkedlist의 시간은 비슷합니다. 이 예제를 약간 수정하고 list size 늘리면 두 가지가 기본적으로 동일한 순서에 있음을 알 수 있습니다.
그러나 ArrayList get 함수의 시간 복잡성은 O (1)이고 링크드 목록 Get 함수의 시간 복잡성은 O (n)입니다.
공간 소비를 고려하면 먼저 ArrayList를 선택하는 것이 좋습니다. 개별 삽입 및 삭제의 경우 LinkedList를 사용할 수 있습니다.
결론 요약
위의 분석을 통해 기본적으로 다음을 요약 할 수 있습니다.
요약
위는이 기사의 전체 내용입니다. 이 기사의 내용이 Java를 배우거나 사용할 때 모든 사람에게 도움이되기를 바랍니다. 궁금한 점이 있으면 의사 소통을 위해 메시지를 남길 수 있습니다.