[Java] Arrays.sort() vs Arrays.stream() 에 대해서.araboza 1편

개요

우리가 보통 개발을 하다보면 Java 8 에 들어가면서 많이 쓰게 되는 API 가 존재한다.

class Solution {
    public int solution(int[][] board, int k) {
        int answer = 0;
        
        for( int i = 0; i < board.length; i++ ) {
            for( int j = 0; j < board[0].length; j++ ) {
                if( i + j <= k )  answer += board[i][j];
            }
        }
        return answer;
    }
}

우리가 일반적으로 코딩을 진행할 때....

 

import java.util.stream.IntStream;

class Solution {
    public static int solution(int[][] board, int k) {
        return IntStream.range(0, board.length).filter(i -> i <= k).map(i -> IntStream.range(0, board[i].length).filter(j -> j <= k - i).map(j -> board[i][j]).sum()).sum();
    }
}

Stream API에 완전 이해를 한 경우 (그래서 이게 무슨 뜻이래요..?)(저도 몰라요...)

 

 

이게 코딩을 진행을 하면 심심치 않게 보이는데. 다들 Stream API 가 성능이 좋지 않다고 한다.

그래서 오늘은 얉게 한번 살펴봐볼까 한다.

 

 

주인공 등장.

import java.util.*;
class Solution2 {
    public int[] solution1(String my_string) {
        String[] temp = my_string.replaceAll("[A-Z|a-z]", "").split("");
        return Arrays.stream(temp).sorted().mapToInt(Integer::new).toArray();
    }
    public int[] solution2(String my_string) {
        String[] temp = my_string.replaceAll("[a-z]", "").split("");
        Arrays.sort(temp);
        int[] answer = new int[temp.length];
        for( int i = 0; i < temp.length; i++) {
            answer[i] = Integer.parseInt(temp[i]);
        }
        return answer;
    }
}

 

Solution2 라는 클래스를 만들었다.

코딩테스트를 하다가 궁금해서 만들고 테스트를 해봤다.

 

각각 solution1 은 stream api를 사용하고 solution2 는 Array.sort를 사용하고

Integer 타입으로 변환만 solution2 가 직접 입력을 하는 것으로 만들었다.

 

 

시동

public class Main {
    public static void main(String[] args) {

        Solution2 solution2 = new Solution2();
        int time = 10000000;
        long start = System.currentTimeMillis();
        for( int i = 0; i < time; i++ ) {
            solution2.solution1("hi12392p2o4i8gj2abcde0");
        }
        long end = System.currentTimeMillis();
        long diff1 = (end - start);
        System.out.println("stream api = " + diff1);

        start = System.currentTimeMillis();
        for( int i = 0; i < time; i++ ) {
            solution2.solution2("hi12392p2o4i8gj2abcde0");
        }
        end = System.currentTimeMillis();
        long diff2 = (end - start);
        System.out.println("Arrays.sort = " + diff2);

        System.out.println(diff1 + " " + diff2);
    }
}

 

빠르게 끝나고 눈에 뛸 정도로 잘 보이는게 10,000,000 번 정도로 1천만번를 기준으로 시행을 했다.

 

 

결과

결과

 

해당 결과를 분석을 해보자.

stream api는 12.167초 걸린 가량

Arrays.sort는 9.257초 밖에 걸리지 않았다.

 

단순 코드 복잡도만 생각을 해보면

Arrays.sort 는 Dual pivot quick sort 를 사용하기 때문에 평균 n * log3n 정도, 최악 n^2 정도 된다.

여기에 solution2 는 Integer 변환을 하면서 n의 시간 복잡도를 더 사용한다.

n * log3n + n 의 시간 복잡도를 가진다.

 

이것보다 더 무거운 stream api는 얼만큼의 시간 복잡도를 가질까

스택오버플로우(stack overflow) 에서 문제를 가진사람이 질문을 올린 것이 있는데,

남이 적은 글을 보면 n * logn 의 시간이 걸린다고 한다.

 

n * log3n = n * logn  지수에서 숫자는 상수배수 차이이기 때문에 사실상 같다고 봐야한다.

하지만 왜 저렇게 시간이 많이 차이가 날까

 

이것은 2편에 계속 적도록 하겠다.