[JAVA] 알고리즘을 최적화 해보자

1. Scanner 입력 대신 BufferedReader를 사용하자

• 왜?

효율면에서 훨씬 굳 (입력값이 많을수록)

BufferedReader는 데이터를 사용자가 요청할 때마다 '매번' 읽어오기 (X)

일정량 사이즈로 '한 번에' 읽어온 후 버퍼에 보관. 사용자가 요구할 때 버퍼에서 읽어오게 한다. (O)

-> 속도 향상, 시간 부하 줄일 수 있다

 

(Scanner의 버퍼 사이즈는 1024 chars VS BufferedReader의 버퍼 사이즈는 8192 chars)

 

얼마나 빠른지 밑에 사진 참고. (출처: 알고스팟)

깨알 지식: BufferedReader 나오고 난 뒤에 Scanner 나옴

• 각각 특징:

Scanner: space를 모두 경계로 인식. 가공하기 쉽다. 효율 낮음

BufferedReader: enter만 경계로 인식. 받은 데이터가 String으로 고정. 입력받은 데이터를 타입 변환/파싱 해야 함. 많은 데이터를 입력받을 경우 효율 좋음

 

• 사용법:

-입력값은 무조건 String 타입이기에 하나하나 타입 변환해줘야 함

-Scanner와 달리 Exception 처리가 자체적으로 되어있지 않기에 따로 Exception 처리해줘야 함

-라인 단위로 입력받기 때문에, 한 줄에 공란을 경계로 여러 값이 입력된 경우라면 파싱이 필수 -> StringTokenizer 사용하면 됨

 

 

(StringTokenizer는 특정 기준으로 읽게 도와주는 역할을 함), 밑에 코드 주석 참고

 

• 코드:

//Scanner 사용법
Scanner scan = new Scanner(System.in);
int x = scan.nextInt();

//BufferedReader 사용법
package till;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    // BufferedReader는 Exception이 처리를 따로 해줘야 하기 때문에 throws를 해주거나 
    // try ~ catch로 예외처리를 해줘야합니다.
    public static void main(String[] args) throws Exception {
        // BufferedReader 객체 생성
        // new InputStreamReader 및 System.in
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // StringTokenizer 객체 선언
        StringTokenizer st = null;

        // String Line이므로 Integer.parseInt를 이용하여 형변환해야함
        int n = Integer.parseInt(br.readLine());//숫자 몇개 입력할래

        // "1 3 5 7" 식으로 공란 포함 String Line일시 StringTokenizer 이용
        int[] arrays = new int[n];
       // st = new StringTokenizer(br.readLine()); //두 번째 파라메터가 없는  br.readLine()의 기본형은 공백을 제거한 것을 추출해줌
        st = new StringTokenizer(br.readLine(),"c");//input 예) 4와 1c2c3c4c을 input 했다면 arrays에는 1, 2, 3, 4가 저장됨
                                                    //이런식으로 StringTokenizer를 통해 내맘대로 input값을 조절?할 수 있음.

        for (int i = 0; i < n; i++) {
            // 배열에다 토큰을 하나씩 불러서 입력해줌
            arrays[i] = Integer.parseInt(st.nextToken());//숫자 n개만큼 입력 후 배열에 저장
        }

        //for each문으로 arrays 출력해보기
        for(int a:arrays){
            System.out.println(a);
        }
    }
}

 

---

 

2. System.out.println을 최대한 줄이고 StringBuilder을 활용하자

 

(출처: https://mygumi.tistory.com/83 [마이구미의 HelloWorld] )

• 왜?

System.out.println가 많을 경우 오버헤드가 쌓여 성능 저하를 초래하기 때문

 

오버헤드란: 어떤 처리를 하기 위해 들어가는 간접적인 처리 시간/메모리 등을 말한다.

ex)

A라는 처리를 단순하게 실행한다면 10초 걸린다.

안전성을 고려하고 부가적인 B라는 처리를 추가한 결과 처리시간이 15초 걸렸다면, 오버헤드는 5초가 된다.

또한 이 처리 B를 개선해 B'라는 처리를 한 결과, 처리시간이 12초가 되었다면, 이 경우 오버헤드가 3초 단축되었다고 말한다.

 

아래 그림을 통해 println이 내부적으로 어떻게 생겼는지 알 수 있다.

 

 

이는 synchronized로 둘러싸여 있는 것을 알 수 있는데 말 그대로 동기화를 뜻한다.

 

동기화란: 하나의 프로세스에는 하나 이상의 스레드가 존재한다.

스레드를 통해 같은 프로세스에서 데이터 공유가 가능하다.

때론 공유 데이터가 작업 중인 스레드가 마칠 때까지 다른 스레드에서 접근하지 못하도록 하기 위한 것이 synchronized(동기화)이다.

 

동기화의 단점인 작업 중인 스레드가 마칠 때까지 다른 스레드들이 대기시간이 발생한다는 것.

즉, System.out.println 또한 동기화가 적용되어 있는 것. 그렇기에 작더라도 오버헤드가 발생되게 되는 것

 

깨알 지식: 프로젝트에서 System.out.println로 로그 남기지 말라는 것이 이 이유 때문이었다

• 특징 설명:

StringBuilder 클래스는 String과 동일하지만 이름처럼 문자열을 보다 쉽게 조작할 수 있는 클래스

StringBuilder는 문자열을 더할 때 새로운 객체를 생성하는 것이 아닌 기존의 데이터를 더하는 방식을 사용하기 때문에 속도도 빠르며 상대적으로 부하가 적다

 

ex)

String x = "abc"; 
String y = "bsf";
x+y;

x+y를 하게 되면 새로운 String을 생성한다.

즉, String 객체와 String 객체를 더하는(+) 행위는 메모리 할당/해제를 발생시키며 더하는 연산이 많아진다면 성능적으로 좋지 않다.

그래서 나온 것이 StringBuilder

• 사용법과 코드:

//System.out.println로만 출력하기
for(int i=0;i<100000000;i++) {
            System.out.prtinln(i);
            }

//StringBuilder 활용하기
StringBuilder sb = new StringBuilder();

        for(int i=0;i<100000000;i++) {
            sb.append(i + "\n");
            }

System.out.println(sb.toString());

 

---

 

3. array와 ArrayList의 특징을 '제대로 알고' 써보자

 

Array	ArrayList
장점: 접근이 빠름	장점: 크기를 계속 늘릴 수 있음. 가변 길이를 활용해야 할 때 좋음
단점: 크기가 애초에 고정되어 있음	단점: 추가/삭제에 시간이 많이 걸림.

• Array와 ArrayList 합쳐서 기이한 구조를 만들어 사용해야 하는 문제도 있다는 점 참고

ArrayList<Integer[]> graph = new ArrayList<>(); 
->세로가 고정되어있고 가로는 가변 길이를 사용하는 저장공간.
quiz1325

//참고 문제: https://mygumi.tistory.com/337

 

---

 

4. java.util 패키지를 되도록 사용하자

 

java.util패키지는 유용한 클래스들을 많이 가지고 있는 패키지

 

ex) 출처: 공식문서 https://docs.oracle.com/javase/8/docs/api/index.html?java/util

 

ㄴ> 정렬 등과 같은 것들은 최대한 이미 만들어져 있는 것들 쓰는 게 좋음.

왜냐, 내가 짠 코드보다 일단 최적화는 입증된 바이고, 그 외의 문제에 신경 쓰는 데 시간을 투자하는 것이 훨씬 효율적.

 

java.util 공부하는 김에 Collection도 같이 공부

• Collection

자바에서 '목록성 데이터를 처리하는 자료구조'를 통칭한다.

자료구조(Data Structure)는 어떤 정보를 담는 것을 의미하여, 하나의 데이터가 아닌 여러 데이터를 담을 때 사용하는 것이다.

배열이 가장 기본적인 자료구조이며, DTO 또한 자료를 담는 하나의 방식이라고 볼 수 있다. (출처: https://tenlie10.tistory.com/10 [게임 개발자 블로그])

[JAVA] DAO, DTO, VO 차이 https://lemontia.tistory.com/591 참고

DTO란

DTO(Data Transfer Object)는 계층 간 데이터 교환을 위한 자바빈즈를 의미합니다.

여기서 말하는 계층 간의 의미는 Controller, View, Business Layer, Persistent Layer 등을 말하며 각 계층간 데이터 교환을 위한 객체를 의미합니다.

DTO는 로직을 가지지 않는 순수한 데이터 객체이고 getter, setter 메소드만 가진 클래스를 의미합니다.

//DTO 클래스 예제
public class PersonDTO { 
    private String name; 
    private int age; 

    public String getName() { return name; } 
    public void setName(String name) { this.name = name; } 
    public int getAge() { return age; } 
    public void setAge(int age) { this.age = age; } 

}

• 배열 이용할 때 for each 활용하자

//for each문으로 arrays 출력해보기
        for(int a:arrays){ //여기서 a는 내 마음대로 지정 가능
            System.out.println(a);
        }

 

---

 

5. array 초기화는 fill을 이용하자

 

• 왜?

아래 코드로 예를 들어 설명함

 

boolean[] isVisited = new boolean[5]; //초기값 0 //배열 생성후 초기화

for(int i=0;i<10;i++){
    //1번 방법
    isVisitid=new boolean[5];
    //2번 방법
    Arrays.fill(isVisited, false);
}

 

첫 번째 줄에서 배열 생성 후 초기화를 해준다.

 

for문에서 1번 방법은:

기본 값으로 초기화하는 방법이다. 하지만 for문이 10번 돌아가므로 새로운 배열 생성하고 초기화하고를 10번 해서 메모리적으로 부하가 갈 수 있다.

 

2번 방법은:

특정 값으로 초기화하는 방법이다. 그러나 이 fill()는 새로 만들어서 초기화하는 게 아니라 이미 생성된 것에 계속해서 똑같이 넣어주는 방식이다. (한 곳에 계속 업데이트한다고 생각하면 될 듯, 누적해서 하나에다가 넣는 것)

-> 메모리 굳

 

//배열을 초기화하기 위해서는 
java.util.Arrays의 
Arrays.fill(배열, 초기화값)을 사용한다.

• Garbage Collector에 대해서도 공부해보자

쉽고 잘 정리된 블로그. (눈높이 교육ㅎ) https://wanzargen.tistory.com/15

 

---

 

6. (공백 없는) 연속된 숫자 input을 이용해야 할 때 split이용은 최대한 피하자

 

(공백 있을 경우는 토크 나이저 사용하면 됨)

• 왜?

공백 없는 연속된 숫자 (ex. 123234)를 가지고 무엇인가를 해야 할 때 다들 split을 생각할 텐데 사실 최적화 측면에서 피해야 하는 문법이다.

String.split()은 사용하기 편하지만 느리기 때문!

 

실제로 (println와 split을 쓴 코드 vs bufferedreader와 br.read-'0'을 쓴 코드)의 속도는 각각

208 vs 128로 속도차가 꽤 났다

• 대신 br.read-'0'를 쓰자

저 0은 숫자 0이 아닌 아스키코드 0을 말한다. (아스키코드 0을 숫자로 변환하면 48 임)

저 아스키코드 0을 빼는 이유는,

-> read() 메서드는 값을 읽어올 때 int형으로 읽어오는 것이 아니기 때문

 

예를 들어) input.txt에 저장된 1이라는 숫자를 read()를 통해 읽어오면 int형 숫자 1을 읽어오는 것이 아닌,

txt형식으로 저장된 ASCII 형식의 문자 값 '1'을 읽어오는 것이므로 결국 int값으론 49를 읽어오는 것이 됩니다.

 

이를 해결하려면

ASCII 값에서 뻴셈을 이용한 뒤 엔터 값을 읽어오거나
int a = br.read() - 48; 
int a = br.read() -'0';//윗 줄과 같은 말임
br.readLine(); 

public class Main {

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        while(num --> 0){
            System.out.println(br.read()-'0');
        }

    }
}

---

stringbuilder출처:

https://mygumi.tistory.com/83

https://hardlearner.tistory.com/288

1번 출처

https://mygumi.tistory.com/43 [마이구미의 HelloWorld]

https://code0xff.tistory.com/5

2번 출처

https://mygumi.tistory.com/83?category=648758

https://hardlearner.tistory.com/288

https://domamaonetwelve.tistory.com/entry/%EC%9E%90%EB%B0%94-%EC%9E%85%EB%A0%A5-Systeminread

4번 출처

https://tenlie10.tistory.com/10

https://lemontia.tistory.com/591

http://www.incodom.kr/Java/java.util.Collections