자바 의 Arrays 라 는 도구 류 를 정말 사용 할 수 있 습 니까?

자바 소스 코드 시리즈 3-도구 류 Arrays
오늘 자바 의 소스 코드 세 번 째 탄,Arrays 라 는 도구 류 의 소스 코드 를 공유 합 니 다.최근 에 데이터 구 조 를 복습 하면 서 Arrays 안의 정렬 알고리즘 과 이분 검색 등의 실현 을 알 게 되 었 고 수익 이 매우 많 기 때문에 Arrays 와 같은 소스 코드 를 연구 하기 로 결정 했다.부족 한 점 은 논평 구역 에서 교류 하고 지적 하 는 것 을 환영 합 니 다.
1.Arrays 클래스 를 알 고 있 습 니 다.
우선 자바 의 utils 패키지 아래 자바 Collections Framework 의 일원 입 니 다.그것 의 취 지 는 바로 도구 류 로 배열 을 조작 하 는 여러 가지 방법 을 밀봉 했다.예 를 들 어 정렬,2 분 검색,배열 의 복사 등 이다.우리 가 일상적으로 수조 체조 에 대한 기본 적 인 수 요 를 만족 시 키 고 그 밑바닥 의 실현 을 이해 하면 우리 가 그것 을 더욱 잘 사용 할 수 있 을 뿐만 아니 라 더 좋 은 코드 의 사고방식 도 키 울 수 있다.
2.구조 방법
도구 류 이기 때문에 그 구조 방법 은 사유 로 정의 되 고 모든 실현 방법 은 정적 방법 이다.즉,이런 종 류 는 실례 화 되 어 서 는 안 되 고,통속 적 으로 말 하면 new 가 안 된다 는 것 이다.클래스 이름 을 통 해서 만 직접 호출 방법(반사 제외).이렇게 하 는 목적 은 이런 실 용화 할 수 없 는 능력 을 강화 하고 이런 도구 류 로 서 의 근본 적 인 기능 을 강조 하 는 것 이다.원본 코드 는 다음 과 같 습 니 다.

 // Suppresses default constructor, ensuring non-instantiability.
 private Arrays() 
{
}

3.상용 방법의 해석
3.1 집합 요 소 를 빠르게 삽입 하 는 방법 asList(T...a):
기본 사용:

 /**
  *        
  */
 @Test
 public void toArrayTest(){
  List<Integer> list = Arrays.asList(2,4,5,6,6);
  for (Integer integer : list) {
   System.out.print(integer+" ");
  }
 }

출력 결과:
2 4 5 6 6
원본 코드 보기:

@SafeVarargs
 @SuppressWarnings("varargs")
 public static <T> List<T> asList(T... a) {
  return new ArrayList<>(a);
 }

// ArrayList        
  private final E[] a;
  ArrayList(E[] array) {
   a = Objects.requireNonNull(array);
  }

이 방법의 실현 은 비교적 간단 하 다.바로 Array List 의 구조 방법 을 호출 하 는 것 이 고 매개 변 수 는 하나의 배열 이다.즉,우리 가 구성 하고 자 하 는 수 를 Array List 의 구조 방법 에 전달 하여 예화 하 는 것 이다.
3.2 2 점 에서 찾 는 방법
Arrays 클래스 의 2 분 검색 8 가지 기본 유형 은 모두 관련 되 어 있 지만 모두 방법의 과부하 입 니 다.그 실현 원 리 는 모두 같다.여기 서 int 유형 을 예 로 들 어 설명 한다.
기본 사용:

 @Test
 public void binarySearchTest(){
  int[] arrays = {1,4,6,7,9,3};
  //      7    
  int result = Arrays.binarySearch(arrays,7);
  System.out.println(result);
 }

결과:
3
이 방법 은 주로 세 가지 방법 과 관련된다.

//        
public static int binarySearch(int[] a, int key) {
  return binarySearch0(a, 0, a.length, key);
 }

/*
       ： a       
 fromIndex        
 toIndex         
 key         
 */
public static int binarySearch(int[] a, int fromIndex, int toIndex,
         int key) {
  //       
  rangeCheck(a.length, fromIndex, toIndex);
  return binarySearch0(a, fromIndex, toIndex, key);
 }

 // Like public version, but without range checks.
 private static int binarySearch0(int[] a, int fromIndex, int toIndex,
          int key) {
  int low = fromIndex;
  int high = toIndex - 1;

  while (low <= high) {
    
   //           
   int mid = (low + high) >>> 1;
   int midVal = a[mid];
   
   //     
   if (midVal < key)
    low = mid + 1;
   else if (midVal > key)
    high = mid - 1;
   else
    return mid; // key found
  }
  return -(low + 1); // key not found.
 }

물론 실현 의 핵심 방법 은 상술 한 사유 방법binarySearch0()이라는 방법 이기 때문에 실현 의 논리 도 복잡 하지 않다.
첫 번 째 단 계 는 두 변수 가 검색 영역 을 저장 하 는 시작 과 끝 을 설명 하 는 것 입 니 다.
두 번 째 순환,비교,비교 범 위 를 계속 축소 합 니 다.배열 의 값 과 목표 값 이 같 을 때 까지 다음 표 시 를 되 돌려 줍 니 다.찾 지 못 하면 마이너스,즉 아래 의 l 두 줄 코드 를 되 돌려 줍 니 다.

return mid; // key found
return -(low + 1); // key not found.

나 는 이 이분법 이 실현 하 는 하 이 라 이 트 는 바로 중간 값 의 이동 연산 을 구 하 는 것 이 라 고 생각한다.

int mid = (low + high) >>> 1;

어떤 사람 은 왜 이 위 연산 을 사용 해 야 하 는 지,나눗셈 이 안 되 는 지 궁금 해 했다.주로 성능 을 고려 하기 위해 서다.이 위 연산 은 두 기계 주 기 를 차지 하고 곱셈 법 은 네 개의 연산 주 기 를 차지 하기 때문에 이 위 연산 의 속 도 는 곱셈 법의 연산 속도 보다 훨씬 빠 를 것 이다.계 산 량 이 작 으 면 차이 가 크 지 않 을 수 있 지만 계 산 량 이 많 으 면 차이 가 매우 뚜렷 하 다.
3.3 배열 의 복사

 @Test
 public void testCopyArrange(){
   //    
  int [] srcArray = {11,2,244,5,6,54};
  //         3   
  int[] descArray = Arrays.copyOf(srcArray,3);
  
  System.out.println(Arrays.toString(descArray));
 }

출력 결과:
[11, 2, 244]
소스 코드 분석:

/*     ：
 original    
 newLength         
 */
public static int[] copyOf(int[] original, int newLength) {
   //           ，        
  int[] copy = new int[newLength];
  System.arraycopy(original, 0, copy, 0,
       Math.min(original.length, newLength));
  return copy;
 }

public static native void arraycopy(Object src, int srcPos,
          Object dest, int destPos,
          int length);

분석:주로 로 컬 방법 인 array copy 를 호출 하여 배열 의 지정 한 길 이 를 복사 한 것 입 니 다.소스 코드 가 배열 의 길 이 를 검사 하지 않 은 것 을 볼 수 있 습 니 다.주로arraycopy()이 방법 을 사용 할 때Math.min()방법 을 사용 하여 성명 의 길 이 를 안전 한 범위 내 에서 보장 합 니 다.만약 에 복사 한 길이 가 배열 의 길 이 를 초과 하면...모든 배열 을 기본 으로 복사 합 니 다.네 이 티 브 수식 방법 에 대해 서 는 사용 할 수 있 습 니 다여기 봐 봐..

 System.arraycopy(original, 0, copy, 0,
       Math.min(original.length, newLength));

물론 배열 이 지정 한 구간 을 복사 해 야 한다 면 ArrayscopyOfRange(int[] original, int from, int to)의 실현 원리 와arraycopy()방법의 원 리 를 유사 하 게 사용 할 수 있다.

@Test
 public void testCopy(){
  int [] srcArray = {11,2,244,5,6,54};
   //          
  int[] descArray = Arrays.copyOfRange(srcArray,0,3);
  System.out.println(Arrays.toString(descArray));
 }

출력 결과:
[11, 2, 244]
주:copyOfRange(int[] original, int from, int to)의 매개 변 수 는 복사 결과 에 포함 되 지 않 습 니 다.상기 예 는 색인 이 2 인 요소 만 복사 할 수 있 고 색인 이 3 인 요 소 는 포함 되 지 않 습 니 다.이 점 은 주의해 야 합 니 다.
3.4 equals 방법
주로 Object 류 의 equals 방법 을 재 작성 하여 두 배열 의 내용 이 같 는 지,즉 그들 중의 요소 가 같 는 지 비교 하 는 데 사용 합 니 다.
기본 용법:

 @Test
 public void equalTest(){
  int[] array ={1,2,3,4};
  int[] result ={1,2,3,4};
  System.out.println(Arrays.equals(array,result)); 
  System.out.println(array == result);
 }

결과:
true
false
소스 코드 를 보기 전에 equals 방법 을 다시 쓴 후에 두 대상 이 비교 하 는 것 은 값,즉 그들의 내용 이라는 점 이 매우 중요 하 다.equals 방법 을 다시 쓰 는 주의사항여기 로 옮 겨..
원본 코드 는 다음 과 같 습 니 다.

 public static boolean equals(int[] a, int[] a2) {
  //        
  if (a==a2)
   return true;
  if (a==null || a2==null)
   return false;

  int length = a.length;
  //        
  if (a2.length != length)
   return false;
  
  //           
  for (int i=0; i<length; i++)
   if (a[i] != a2[i])
    return false;

  return true;
 }

소스 코드 설명 은 다음 과 같 습 니 다.
소스 코드 는 네 번 의 판단 을 했 는데 각각 첫 번 째 주소 비교,비어 있 는 지,그리고 길이 의 비교 이 고 마지막 으로 배열 의 각 요 소 를 비교 했다.
다음 의 첫 번 째 판단,즉 첫 번 째 주소 의 비 교 를 설명 할 필요 가 있다.우리 가 배열 변 수 를 설명 할 때 이 변 수 는 배열 의 첫 번 째 주 소 를 대표 합 니 다.아래 코드 를 보 세 요.

 @Test
 public void equalTest(){
  int[] array ={1,2,3,4};
  System.out.println(array);
  
 }

결과:
[I@4f2410ac     // [대표 배열 I 대표 정수@구분자 뒤에 있 는 메모리 주소 16 진수
이것 은 주 소 를 나타 낸다.아니면 하나의 배열 을 설명 할 때 더미 안에 메모리 영역 을 만 들 기 때 문 입 니까?그러나 이 메모리 영역 은 더미 에 비해 작 을 수 있 습 니 다.찾기 가 쉽 지 않 습 니 다.찾기 편 하도록 배열 메모리 의 첫 주 소 를 표시 합 니 다.가상 컴퓨터 는 변수 이름 array 에 주 소 를 전달 합 니 다.이것 도 참조 형식 입 니 다.주소,즉 array 가 메모리 주 소 를 가리 키 는 것 으로 이해 합 니 다.실행 할 때마다 주소 가 다 를 수 있 습 니 다.가상 컴퓨터 가 열 린 메모리 공간 이 다 를 수 있 기 때 문 입 니 다.
이것 을 이해 하면a==a2이해 하기 쉽다.만약 두 그룹의 메모리 주소 가 모두 같다 면 두 그룹의 메모리 주 소 는 틀림없이 같다.
그리고 프로그램 이 비교적 잘 쓴 곳 은 바로 소스 코드 에서 배열 의 모든 요소 에 대한 비교,즉 아래 의 이 코드 라 고 생각 합 니 다.

for (int i=0; i<length; i++)
   if (a[i] != a2[i])
    return false;

  return true;

판단 조건 으로 사용a[i] != a2[i]하면 비교 횟수 를 줄 이 고 성능 을 높 일 수 있다.만약 에 여기 가 똑 같은 비교 라면 매번 전체 배열 을 옮 겨 다 녀 야 한다.만약 에 데이터 의 양 이 많 으 면 성능 이 많이 느 릴 것 이다.또 한 번 소스 의 매력 에 감탄 했다.
3.5 정렬 방법 sort()와 parallelsert()Arrays이 유형 은 주로 두 가지 유형의 정렬 방법 직렬sort()과 병렬parallelSort()두 가지 방법 과 관련 되 는데 물론 대상 의 정렬 과 기본 유형의 정렬 도 다르다.여 기 는 int[]유형의 예 입 니 다.설명 을 하 다.
먼저 두 가지 방법의 성능 을 비교한다.

 public final int UPPER_LIMIT = 0xffffff;
 final int ROUNDS = 10;
 final int INCREMENT = 5;
 final int INIT_SIZE = 1000;

 @Test
 public void sortAndParallelSortTest(){
  
  //          
  for (int capacity = INIT_SIZE; capacity < UPPER_LIMIT ; capacity*= INCREMENT) {
   ArrayList<Integer> list = new ArrayList<>(capacity);
   for (int j = 0; j < capacity; j++) {
    list.add((int) (Math.random()*capacity));
   }
   
   double avgTimeOfParallelSort = 0;
   double avgTimeOfSort = 0;

   for (int j = 0; j <= ROUNDS ; j++) {
    //          
    Collections.shuffle(list);

    Integer[] arr1 = list.toArray(new Integer[capacity]);
    Integer[] arr2 = arr1.clone();
     
    avgTimeOfParallelSort += counter(arr1,true);
    avgTimeOfSort += counter(arr2, false);
   }
   //     
   output(capacity,avgTimeOfParallelSort/ROUNDS,avgTimeOfSort/ROUNDS);
  }
 }

 private void output(int capacity, double v, double v1) {
  System.out.println("=======================       =========");
  System.out.println("Capacity"+capacity);
  System.out.println("ParallelSort"+v);
  System.out.println("Sort"+v1);
  System.out.println("       ："+(v < v1 ? "ParallelSort":"Sort"));
 }

 //        
 private double counter(Integer[] arr1, boolean b) {
  long begin,end;
  begin = System.nanoTime();
  if(b){
   Arrays.parallelSort(arr1);
  }else{
   Arrays.parallelSort(arr1);
  }
  end = System.nanoTime();
  return BigDecimal.valueOf(end-begin,9).doubleValue();
 }

부분의 테스트 결과:
===========================테스트 정렬 의 시간================
Capacity1000
ParallelSort6.284099999999999E-4
Sort5.599599999999999E-4
비교적 빠 른 정렬 은:Sort
===========================테스트 정렬 의 시간================
Capacity5000
ParallelSort0.00163599
Sort0.0018313699999999995
빠 른 정렬 은:ParallelSort
데이터 양 이 비교적 적은 상황 에서 sort()방법 을 사용 하 는 것 이 빠 르 고 한 한도 값 이 지나 면 ParallelSort()라 는 방법 이 성능 이 좋 은 것 을 볼 수 있 습 니 다.이 한도 값 은 얼마 일 까요?
먼저 parallelsert 의 소스 코드 를 살 펴 보 겠 습 니 다.

public static void parallelSort(int[] a) {
  int n = a.length, p, g;
  if (n <= MIN_ARRAY_SORT_GRAN ||
   (p = ForkJoinPool.getCommonPoolParallelism()) == 1)
   DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);
  else
   new ArraysParallelSortHelpers.FJInt.Sorter
    (null, a, new int[n], 0, n, 0,
     ((g = n / (p << 2)) <= MIN_ARRAY_SORT_GRAN) ?
     MIN_ARRAY_SORT_GRAN : g).invoke();
 }

배열 의 길이 가MIN_ARRAY_SORT_GRAN보다 작 거나p = ForkJoinPool.getCommonPoolParallelism()) == 1(단일 스 레 드 에서)일 때 sort()정렬 의 바 텀 을 호출 하여 이 루어 진DualPivotQuicksort.sort(a, 0, n - 1, null, 0, 0);Arrays 의 시작 정 의 는 다음 과 같 습 니 다.

private static final int MIN_ARRAY_SORT_GRAN = 1 << 13; //     8192

두 가 지 를 비교 하면 배열 의 길이 가 비교적 크 거나 다 중 스 레 드 의 경우 병렬 정렬 을 우선 고려 하고 그렇지 않 으 면 직렬 정렬 을 사용 하 는 것 이다.
두 정렬 의 핵심 사상:

sort()방법의 핵심 은 빠 른 배열 과 최적화 후의 병합 정렬 입 니 다.빠 른 정렬 은 주로 어떤 기본 유형의 데이터(int,short,long 등)를 정렬 하 는 것 이 고 병합 정렬 은 대상 유형 을 정렬 하 는 데 사 용 됩 니 다.

parallelsert()는 병렬 정렬-병합 정렬 알고리즘 을 사용 합 니 다.이것 은 배열 을 하위 배열 로 나 누고 이 하위 배열 자체 가 먼저 정렬 한 다음 에 합 친다.

병렬 정렬 과 직렬 정렬 의 밑바닥 이 비교적 복잡 하고 편폭 이 제한 되 어 있 기 때문에 밑바닥 실현 에 대해 자세히 알 고 싶다 면직렬 정렬과병렬 정렬로 이동 할 수 있다.
3.6 toString 방법
기본 용법:

 @Test
 public void toStringTest(){
   int[] array = {1,3,2,5};
  System.out.println(Arrays.toString(array));
 }

결과:
[1, 3, 2, 5]
소스 코드 분석 은 다음 과 같다.

 public static String toString(int[] a) {
  // 1.       
  if (a == null)
   return "null";
  int iMax = a.length - 1;
  if (iMax == -1)
   return "[]";
  
  // 2.  StringBuilder    
  StringBuilder b = new StringBuilder();
  b.append('[');
  for (int i = 0; ; i++) {
   b.append(a[i]);
   if (i == iMax)
    return b.append(']').toString();
   b.append(", ");
  }
 }

구체 적 인 실현 은 이미 소스 코드 의 주석 에서 설명 되 었 다.이 방법 은 기본 데이터 형식 에 있어 서 배열 을 편리 하 게 옮 겨 다 닌 다.
근본 을 캐 고 근원 을 거 슬러 야만 활보 하여 앞으로 나 아 갈 수 있다.
참고 자료
https://www.jb51.net/article/180770.htm
https://www.jb51.net/article/116323.htm
javaSE 의 공식 문서.
자바 에 있 는 Arrays 라 는 도구 류 를 사용 할 수 있 습 니까?