Java의 ArrayList 및 LinkedList 스트리밍 및 성능 분석

14733 단어 javaarraylistlinkedlist두루 다니다
앞말
본고를 통해 당신은 List의 다섯 가지 역행 방식과 각자의 성능과foreach 및 Iterator의 실현을 이해하고 Array List와Linked List의 실현에 대한 이해를 깊이 있게 할 수 있습니다.다음은 같이 봅시다.
1. List의 5가지 반복 방식
1. for each 순환

List<Integer> list = new ArrayList<Integer>();
for (Integer j : list) {
 // use j
}
2. 디스플레이 호출 집합 교체기

List<Integer> list = new ArrayList<Integer>();
for (Iterator<Integer> iterator = list.iterator(); iterator.hasNext();) {
 iterator.next();
}
또는

List<Integer> list = new ArrayList<Integer>();
Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()) {
 iterator.next();
}
3. 아래 표의 점차적인 순환, 종료 조건은 매번size() 함수 비교 판단

List<Integer> list = new ArrayList<Integer>();
for (int j = 0; j < list.size(); j++) {
 list.get(j);
}
4. 아래 표의 점차적인 순환, 종료 조건은size()와 같은 임시 변수 비교 판단

List<Integer> list = new ArrayList<Integer>();
int size = list.size();
for (int j = 0; j < size; j++) {
 list.get(j);
}
5. 아래 표의 체감 순환

List<Integer> list = new ArrayList<Integer>();
for (int j = list.size() - 1; j >= 0; j--) {
 list.get(j);
}
List 5가지 반복 방식의 성능 테스트 및 비교
다음은 성능 테스트 코드입니다. 수량급 크기가 다른 Array List와 Linked List의 다양한 반복 방식을 출력하는 데 걸리는 시간입니다.

package 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 www.trinea.cn 2013-10-28
 */
public class JavaLoopTest {
 public static void main(String[] args) {
  System.out.print("compare loop performance of ArrayList");
  loopListCompare(getArrayLists(10000, 100000, 1000000, 9000000));
  System.out.print("\r
\r
compare loop performance of LinkedList");
  loopListCompare(getLinkedLists(100, 1000, 10000, 100000));
 }
 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];
   List<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];
   List<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);
  long startTime, endTime;
  // Type 1
  for (int i = 0; i < listArray.length; i++) {
   List<Integer> list = listArray[i];
   startTime = Calendar.getInstance().getTimeInMillis();
   for (Integer j : list) {
    // use j
   }
   endTime = Calendar.getInstance().getTimeInMillis();
   printCostTime(i, listArray.length, "for each", endTime - startTime);
  }
  // Type 2
  for (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, "for iterator", endTime - startTime);
  }
  // Type 3
  for (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);
  }
  // Type 4
  for (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, "for size = list.size()", endTime - startTime);
  }
  // Type 5
  for (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;
 static final 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.format(listArray[i].size()));
   while (sb.length() < OTHER_COLUMN_LENGTH) {
    sb.append(" ");
   }
   System.out.print(sb);
  }
  TOTAL_COLUMN_LENGTH = FIRST_COLUMN_LENGTH + OTHER_COLUMN_LENGTH * listArray.length;
  printRowDivider();
 }
 public static void printRowDivider() {
  System.out.println();
  StringBuilder sb = new StringBuilder();
  while (sb.length() < TOTAL_COLUMN_LENGTH) {
   sb.append("-");
  }
  System.out.println(sb);
 }
 public static void printCostTime(int i, int size, String caseName, long costTime) {
  if (i == 0) {
   StringBuilder sb = new StringBuilder().append(caseName);
   while (sb.length() < FIRST_COLUMN_LENGTH) {
    sb.append(" ");
   }
   System.out.print(sb);
  }
  StringBuilder sb = new StringBuilder().append("| ").append(costTime).append(" ms");
  while (sb.length() < OTHER_COLUMN_LENGTH) {
   sb.append(" ");
  }
  System.out.print(sb);
  if (i == size - 1) {
   printRowDivider();
  }
 }
}
PS: in thread “main” java.lang.OutOfMemoryError: Java heap space을 실행하면 main 함수에서 list size의 크기를 줄입니다.
이 중 getArrayLists 함수는 size의 ArrayList를, getLinkedLists 함수는 size의 LinkedList를 각각 되돌려줍니다.loopListCompare 함수는 위의 반복 방식 1-5로 각각list 수조 (크기가 다른list 포함) 의list를 반복합니다.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 
-----------------------------------------------------------------------
for each    | 1 ms  | 3 ms  | 14 ms  | 152 ms 
-----------------------------------------------------------------------
for iterator   | 0 ms  | 1 ms  | 12 ms  | 114 ms 
-----------------------------------------------------------------------
for list.size()  | 1 ms  | 1 ms  | 13 ms  | 128 ms 
-----------------------------------------------------------------------
for size = list.size() | 0 ms  | 0 ms  | 6 ms  | 62 ms  
-----------------------------------------------------------------------
for j--    | 0 ms  | 1 ms  | 6 ms  | 63 ms  
-----------------------------------------------------------------------
 
compare loop performance of LinkedList
-----------------------------------------------------------------------
list size    | 100  | 1,000  | 10,000 | 100,000 
-----------------------------------------------------------------------
for each    | 0 ms  | 1 ms  | 1 ms  | 2 ms  
-----------------------------------------------------------------------
for iterator   | 0 ms  | 0 ms  | 0 ms  | 2 ms  
-----------------------------------------------------------------------
for list.size()  | 0 ms  | 1 ms  | 73 ms  | 7972 ms 
-----------------------------------------------------------------------
for size = list.size() | 0 ms  | 0 ms  | 67 ms  | 8216 ms 
-----------------------------------------------------------------------
for j--    | 0 ms  | 1 ms  | 67 ms  | 8277 ms 
-----------------------------------------------------------------------
첫 번째 표는 ArrayList 비교 결과이고, 두 번째 표는 LinkedList 비교 결과입니다.
시계 가로는 같은 경로 방식, 크기가 다른list 경로의 시간 소모, 세로는list 경로의 시간 소모입니다.
PS: List를 처음 훑어보는 데 약간의 시간이 걸리기 때문에 for each의 결과는 약간의 편차가 있습니다. 테스트 코드의 몇 가지 Type 순서를 바꾸면 for each의 시간과 for iterator이 가깝다는 것을 알 수 있습니다.
반복 방식 성능 테스트 결과 분석
1. foreach 소개
foreach는 자바 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 스트리밍 방식 결과 분석
a. ArrayList 크기가 10만 개가 되기 전에 다섯 가지 반복 방식의 시간 소모는 거의 같다
b. 10만 이후 네 번째, 다섯 번째 반복 방식은 세 가지보다 빠르고 get 방식은 Iterator 방식보다 우수하며

int size = list.size();
for (int j = 0; j < size; j++) {
 list.get(j);
}
list.size()을 임시 변수 크기로 대체하면 성능이 더욱 우수합니다.Array List의 교체기 Iterator과 get 방법의 실현을 봅시다.

private class Itr implements Iterator<E> {
 int cursor;  // index of next element to return
 int lastRet = -1; // index of last element returned; -1 if no such
 int expectedModCount = modCount;
 
 public boolean hasNext() {
  return cursor != size;
 }
 
 @SuppressWarnings("unchecked")
 public E next() {
  checkForComodification();
  int i = cursor;
  if (i >= size)
   throw new NoSuchElementException();
  Object[] elementData = ArrayList.this.elementData;
  if (i >= elementData.length)
   throw new ConcurrentModificationException();
  cursor = i + 1;
  return (E) elementData[lastRet = i];
 }
 ……
}
 
public E get(int index) {
 rangeCheck(index);
 
 return elementData(index);
}
이를 통해 알 수 있듯이 get과 Iterator의 next 함수 역시 직접 포지셔닝 데이터를 통해 원소를 얻는 것은 단지 몇 가지 판단이 많았을 뿐이다.
c. 이를 통해 알 수 있듯이 천만 크기의 Array List에서도 몇 가지 반복 방식의 차이는 50ms 정도에 불과하고 자주 사용하는 10만 정도의 시간은 거의 같다.foreach의 장점을 고려하여foreach라는 간편한 방식으로 반복할 수 있다.
3. LinkedList 스트리밍 방식 결과 분석
A. LinkedList 크기가 만 개에 가까울 때 get 방식과 Iterator 방식은 이미 두 개의 수량급이 차이가 났고 10만 시 Iterator 방식의 성능은 get 방식보다 훨씬 낫다.
LinkedList의 교체기와 get 방법의 실현을 봅시다.

private class ListItr implements ListIterator<E> {
 private Node<E> lastReturned = null;
 private Node<E> next;
 private int nextIndex;
 private int expectedModCount = modCount;
 
 ListItr(int index) {
  // assert isPositionIndex(index);
  next = (index == size) ? null : node(index);
  nextIndex = index;
 }
 
 public boolean hasNext() {
  return nextIndex < size;
 }
 
 public E next() {
  checkForComodification();
  if (!hasNext())
   throw new NoSuchElementException();
 
  lastReturned = next;
  next = next.next;
  nextIndex++;
  return lastReturned.item;
 }
 ……
}
 
public E get(int index) {
 checkElementIndex(index);
 return node(index).item;
}
 
/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
 // assert isElementIndex(index);
 
 if (index < (size >> 1)) {
  Node<E> x = first;
  for (int i = 0; i < index; i++)
   x = x.next;
  return x;
 } else {
  Node<E> x = last;
  for (int i = size - 1; i > index; i--)
   x = x.prev;
  return x;
 }
}
위 코드에서 알 수 있듯이 LinkedList 교체기의 next 함수는next 바늘을 통해 다음 요소를 신속하게 얻고 되돌려줍니다.get 방법은 처음부터 index 아래에 표시될 때까지 반복합니다. 원소를 찾는 시간의 복잡도는 오 (n) 이고, 반복된 시간의 복잡도는 O (n2) 에 도달합니다.
따라서 LinkedList의 반복에 대해foreach를 추천하고 get 방식을 사용하지 마십시오.
4. ArrayList 및 LinkedList 스트리밍 방식 결과 비교 분석
위의 수량 등급을 보면 마찬가지로 foreach 순환이 반복되고 Array List와 Linked List의 시간 차이가 많지 않기 때문에 이 예시를 조금만 수정하면 list size을 확대하면 양자가 기본적으로 하나의 수량 등급에 있다는 것을 발견할 수 있다.
그러나 ArrayList get 함수가 직접 위치를 정하여 가져오는 방식의 시간 복잡도는 O(1)이고 LinkedList의 get 함수 시간 복잡도는 O(n)이다.
공간 소비를 고려하여 Array List를 선택하는 것이 좋습니다.개별 삽입 삭제에는 LinkedList를 사용할 수 있습니다.
결론 총결
위의 분석을 통해 우리는 기본적으로 다음과 같이 요약할 수 있다.
  • ArrayList든 LinkedList든 반복은 foreach를 사용하는 것을 권장합니다. 특히 데이터의 양이 비교적 많을 때 LinkedList는 get을 사용하지 않습니다.
  • List는 ArrayList를 선호합니다.개별 삽입 삭제에는 LinkedList를 사용할 수 있습니다.
  • 은 List 순환 내부에서 아래 표까지 사용해야 할 수 있습니다. 이 때 foreach와 자증count를 사용할지 get 방식을 종합적으로 고려합니다.
    • 총결산
    이상은 이 글의 전체 내용입니다. 본고의 내용이 여러분이 자바를 공부하거나 사용할 때 도움이 되었으면 좋겠습니다. 의문이 있으면 댓글을 남겨 주십시오.
    '초보자 필수'HTML은 정말 그 조합법에 맞나요?(BEM을 부드럽게 사용)
    [백준] 1764번: 듣보잡

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage